Python: rekenen met lijst van getallen

[MKe]

Hoi,

Een leuk python probleempje.
Wat is een efficiente manier om bij een serie items in een list van integers 1 op te tellen?

Dus stel ik heb de list: a=[1,1,1,1,1,1,1,1,1,1,1,1]
ik heb een list van indices: indices = [2,5,8]
dus bij item 2, 5 en 8 moet 1 opgeteld worden, dus resultaat:print a:
[1,1,2,1,1,2,1,1,2,1,1,1]

De volgende (naive?) methode werkt:

Code: [Selecteer]

a=[1,1,1,1,1,1,1,1,1,1,1,1]
indices = [2,5,8]
for i in indices:
    a[i]+=1
Nu is het hier simpel, maar ik heb lijsten van miljoenen items. Kan dit efficienter, dus vooral sneller? Of is dit de beste methode?

[erik1984]

Op het eerste gezicht lijkt dit mij de beste oplossing qua complexiteit, zeker als het rijtje indices (veel) kleiner is dan het rijtje integers. Sowieso heeft de verzameling indices ten hoogste dezeflde grootte als de verzameling integers toch? (len(indices) <= len(a)) Denk dat het dan verder ook niet anders kan dan zo, alle indices zullen moeten worden gelezen.

Andere methodes die me te binnen schieten (zoas een 'masker'-array optellen bij a) zouden inhouden dat je de hele rij integers moet lezen en dat is meer werk.

[FreeTheBee]

Of het sneller is zou je moeten testen, maar je zou numpy arrays kunnen gebruiken.

Code: [Selecteer]

In [1]: import numpy as np

In [2]: x = np.ones(10)

In [3]: x
Out[3]: array([ 1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.])

In [4]: i = [2, 5, 8]

In [5]: x[i] += 1

In [6]: x
Out[6]: array([ 1.,  1.,  2.,  1.,  1.,  2.,  1.,  1.,  2.,  1.])


[MKe]

Bedankt. Ik ben eens gaan benchmarken. Onderstaande codes in scriptjes gezet en met time gestart.

Methode 1:

Code: [Selecteer]

#!/usr/bin/env python

iteraties = 1000
a = [1]*1000000
indices = range(300000,800000)
for y in xrange(iteraties):
  for i in indices:
    a[i]+=1

real    0m58.761s
user    0m58.692s
sys     0m0.008s

Methode 2 (numpy):

Code: [Selecteer]

#!/usr/bin/env python
import numpy as np

iteraties = 1000

a = np.ones(1000000)
indices = range(300000,800000)

for y in xrange(iteraties):
    a[indices] += 1
real    1m45.374s
user    1m41.914s
sys     0m3.344s

Het lijkt er dus op dat numpy pakweg 2x langzamer is.

[FreeTheBee]

Bij mij is de loop anderhalf keer zo snel. Wanneer ik echter,

Code: [Selecteer]

indices = range(300000,800000)
vervang door,

Code: [Selecteer]

indices = np.arange(300000,800000)
loopt numpy ongeveer 7x zo snel als de loop.

[MKe]

Bij mij is de loop anderhalf keer zo snel. Wanneer ik echter,

Code: [Selecteer]

indices = range(300000,800000)
vervang door,

Code: [Selecteer]

indices = np.arange(300000,800000)
loopt numpy ongeveer 7x zo snel als de loop.

Yup hier ook:
real    0m6.075s
user    0m6.052s
sys     0m0.012s

Lijkt idd wel erg goed te werken. En erg snel.

[erik1984]

Blij dat het werkt. Maar dat is dus een verbetering op low-level implementatieniveau (Gebruikte numpy niet C onder water? ), dacht dat je op zoek was naar verbeteringen in het algoritme zelf (complexiteit).

[FreeTheBee]

Numpy gebruikt idd soms C  achter de schermen en maakt ook gebruik van LAPACK (Fortran bibliotheken).

Het verschil in snelheid tussen arange en range had ik eerlijk gezegd niet verwacht. Ik moet daar dus beter rekening mee gaan houden.

[SeySayux]

Dit heeft een tijdscomplexiteit van O(n) (met n het aantal indices), daar kom je dus al nooit onder uit. Maar het is wel volledig paralleliseerbaar. Dus je kan, met n verwerkers, het reduceren tot O(1).

Ten eerste, om zoveel mogelijk rauwe snelheid als mogelijk te krijgen, zou je het in C kunnen doen. Aangezien het niet een te moeilijk programma is, is dat zeker haalbaar. Ten tweede kan je dus gaan paralleliseren. Hier heb je verschillende opties voor:

• SIMD-instructies: dit zijn enkele instructies die je één operatie over meerdere stukken data kan laten uitvoeren, in een klokcyclus.
• Multithreading: Moeilijker. Zoveel als je cores hebt (of met Hyperthreading, 2 keer zoveel) threads aanmaken, gaat dus ook zoveel keer sneller. Samen met SIMD kan je al wat winst maken
• OpenCL: laat de GPU het werk doen. Nogal omslachtig, een GPU kan ook niet alle generische berekeningen doen.

- SeySayux

[MKe]

Multthreading heeft by python geen nut vanwege deglobal intepreter lock. Multiprocess kan wel, maar dan heb je de overhead van interpreters. In C vatten zal denk ik nog de beste methode zijn, maar blijkbaar heeft numpy dit al voor ons gedaan. Mijn ervaring met gpu is in Cuda. Gpu' zijn over het algemeen slecht in integer en matrix berekeningen. Verder is de i/o beperkend, mijn data is gb's groot, dus zal niet optimaal zijn.
Maar eigelijk was ik op zoek naar een python oplossing.

[Vistaus]

Python multithreading kan prima hoor.
http://www.tutorialspoint.com/python/python_multithreading.htm
http://stackoverflow.com/questions/2846653/python-multithreading-for-dummies
http://docs.python.org/2/library/threading.html#module-threading

[erik1984]

Python multithreading kan prima hoor.
http://www.tutorialspoint.com/python/python_multithreading.htm
http://stackoverflow.com/questions/2846653/python-multithreading-for-dummies
http://docs.python.org/2/library/threading.html#module-threading

Uiteraard kan Python dat. MKE zegt ook niet dat het niet kan, maar het levert in dit geval geen snelheidswinst op door de GIL. Uitleg: de threads zullen allemaal moeten wachten tot de grote rij integers is vrijgegeven voor bewerking. Anders zouden er rare conflicten kunnen ontstaan. In de praktijk zullen ze dan toch na elkaar hun bewerkingen doen en er is nog een kleine overhead van het threaden zelf.

[FreeTheBee]

Ik zat net te denken wat pypy nog kan uithalen qua snelheid. Wanneer ik de loop versie in pypy draai gaat ie ongeveer 2x zo snel als de numpy variant. De numpy versie wordt niet verder versneld, door pypy, maar ondersteuning hiervoor is dan ook nog niet volledig.

[MKe]

Hmmm, blijkbaar is die JIT compiler nuttig bij dit soort dingen.