Nieuws:

We zijn er weer.

Na lange tijd van afwezigheid zijn we er weer  :laugh:
We hebben alle wachtwoorden gereset, je oude wachtwoord werkt niet meer.Je moet via het "wachtwoord vergeten"-linkje je wachtwoord resetten. Je krijgt hiervoor een mailtje op het adres dat je bij ons geregistreerd hebt.

De komende tijd zijn we nog druk bezig om de rest van de site op te bouwen, dus het kan zijn dat sommige onderdelen (tijdelijk) niet werken.

Welkom, Gast. Alsjeblieft inloggen of registreren.
Heb je de activerings-mail niet ontvangen?

Auteur Topic: Python: rekenen met lijst van getallen  (gelezen 4177 keer)

Offline MKe

  • Lid
  • Steunpunt: Nee
Python: rekenen met lijst van getallen
« Gepost op: 2013/02/07, 12:05:53 »
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:
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?
« Laatst bewerkt op: 2013/02/07, 12:50:08 door MKe »
Mijn blokkendoos blog: http://mke21.wordpress.com/

Offline erik1984

  • Lid
    • erik1984
  • Steunpunt: Nee
Re: Python: rekenen met lijst van getallen
« Reactie #1 Gepost op: 2013/02/07, 12:25:06 »
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.
« Laatst bewerkt op: 2013/02/07, 12:27:49 door erik1984 »

Offline FreeTheBee

  • Lid
  • Steunpunt: Nee
Re: Python: rekenen met lijst van getallen
« Reactie #2 Gepost op: 2013/02/07, 13:13:49 »
Of het sneller is zou je moeten testen, maar je zou numpy arrays kunnen gebruiken.

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.])

Offline MKe

  • Lid
  • Steunpunt: Nee
Re: Python: rekenen met lijst van getallen
« Reactie #3 Gepost op: 2013/02/07, 15:49:36 »
Bedankt. Ik ben eens gaan benchmarken. Onderstaande codes in scriptjes gezet en met time gestart.

Methode 1:
#!/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):
#!/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.

Offline FreeTheBee

  • Lid
  • Steunpunt: Nee
Re: Python: rekenen met lijst van getallen
« Reactie #4 Gepost op: 2013/02/07, 16:28:58 »
Bij mij is de loop anderhalf keer zo snel. Wanneer ik echter,
indices = range(300000,800000)
vervang door,
indices = np.arange(300000,800000)
loopt numpy ongeveer 7x zo snel als de loop.

Offline MKe

  • Lid
  • Steunpunt: Nee
Re: Python: rekenen met lijst van getallen
« Reactie #5 Gepost op: 2013/02/07, 16:32:10 »
Bij mij is de loop anderhalf keer zo snel. Wanneer ik echter,
indices = range(300000,800000)
vervang door,
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.

Offline erik1984

  • Lid
    • erik1984
  • Steunpunt: Nee
Re: Python: rekenen met lijst van getallen
« Reactie #6 Gepost op: 2013/02/07, 16:46:12 »
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).

Offline FreeTheBee

  • Lid
  • Steunpunt: Nee
Re: Python: rekenen met lijst van getallen
« Reactie #7 Gepost op: 2013/02/07, 16:57:06 »
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.

Offline SeySayux

  • Lid
    • SeySayux.net
  • Steunpunt: Nee
Re: Python: rekenen met lijst van getallen
« Reactie #8 Gepost op: 2013/02/07, 17:28:41 »
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
I use a Unix-based system, that means I'll get laid as often as I have to reboot.
LibSylph
SeySayux.net

Offline MKe

  • Lid
  • Steunpunt: Nee
Re: Python: rekenen met lijst van getallen
« Reactie #9 Gepost op: 2013/02/07, 17:43:28 »
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.


Offline erik1984

  • Lid
    • erik1984
  • Steunpunt: Nee
Re: Python: rekenen met lijst van getallen
« Reactie #11 Gepost op: 2013/02/08, 12:45:41 »
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.
« Laatst bewerkt op: 2013/02/08, 12:57:25 door erik1984 »

Offline FreeTheBee

  • Lid
  • Steunpunt: Nee
Re: Python: rekenen met lijst van getallen
« Reactie #12 Gepost op: 2013/02/12, 14:00:20 »
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.


Offline MKe

  • Lid
  • Steunpunt: Nee
Re: Python: rekenen met lijst van getallen
« Reactie #13 Gepost op: 2013/02/12, 16:09:55 »
Hmmm, blijkbaar is die JIT compiler nuttig bij dit soort dingen.