[PYTHON] Performance van raw_input en integer conversie

[Snake_Y_]

Wanneer ik onderstaand stukje code uitvoer op een bestand van plusminus 31 MB
krijg ik volgende timings:

time cat input.txt | python tweakers.py
11962
real	0m13.152s
user	0m10.582s
sys	0m2.508s

Na wat profiling blijkt dat dit stukje code 99% van de tijd bezig is met de 'readInput'-functie.
In deze functie wordt 50-50 van de tijd 'verspeeld' met de raw_input() en de int()-conversie

Zijn er andere, en betere manieren om input te lezen en/of de input naar een integer te converteren?
En dit met de standaard python libs.

Le code:

Python:

import  string

lst = []                
n = 0
div = 0

def readInput():
    global lst,n,div
    strTmp = string.split(raw_input(),' ')
    n = int(strTmp[0])      # number of lines in file - param 1 from first line
    div = int(strTmp[1])    # read dividor -  param 2 from first line
    lst = [0] * n           # initiase array (fixed size)
    for i in range(n):
        lst[i] = int(raw_input())   # convert input to integer
    return 

def calc():
    global lst,n,div
    output_number = 0
    for i in range(n):
       if (lst[i] % div == 0):
           output_number += 1 
    print output_number 
    return 
    
if __name__ == '__main__':
    readInput()
    calc()
    pass

PS: Python 2.5.2

[Fiander]

Hoe ziet het input bestand er uit ?

Ik kan me voorstellen dat waneer je 100.000 regels hebt, waarvoor telkens raw_input() opnieuw gestart moet worden, het mischien beter zou zijn om de array ( die je toch al hebt. ) te hergebruiken ?

ik ken phyton niet , maar iets als dit dus.

global lst,n,div
strTmp = string.split(raw_input(),' ')
n = int(strTmp[0]) # number of lines in file - param 1 from first line
div = int(strTmp[1]) # read dividor - param 2 from first line
lst = [0] * n # initiase array (fixed size)
for i in range(n):
lst[i] = int(strTmp[n-2] ) # convert input to integer ( -2 omdat de eerste twee regels initiators zijn )
return

[eghie]

Gewoon uit bestand lezen, ipv een PIPE te gebruiken is een stuk sneller.

Fiander, wat jij zegt, gaat niet werken. raw_input() leest gewoon elke keer een nieuwe regel uit. In jouw geval gaat hij op zijn bek en gaat hij geen regels verder lezen, dan de 1e regel.

Daarnaast, zit je toch altijd aan een bepaald percentage van de tijd met inlezen. 99% van de tijd met die raw_input() bezig zijn, is opzich niet zo heel erg. Vergeet niet dat het percentages zijn. Opzich vind ik de totale tijd nou ook niet echt heel bijzonder hoog ofzo.

[Snake_Y_]

Dit is eigenlijk een opdracht uit een code competition (codechef - practice section).
Het inlezen van het bestand gebeurt met de cat-functie...
De bedoeling is om een groot bestand in een korte tijd in te lezen en te verwerken.
Met dit stukje code verwerk ik het bestand niet binnen de opgelegde limieten.

Met python verlies is een hoop tijd met juist het inlezen en converteren.
In andere programmeertalen zou je ervoor kunnen kiezen om de input als een stream in te lezen om zo
sneller de input te kunnen inlezen...

als ik volgende doe, dan gaat dit toch redelijk snel

time cat input.txt > /dev/null

real	0m0.043s
user	0m0.006s
sys	0m0.034s

ps: input file bestaat uit 4.000.000 lijnen

[user109731]

Hier vind je een aantal manieren.

De snelste is volgens mij dit:

Python:

import sys

lines = sys.stdin.xreadlines()
for line in lines:
  #...

Dit werkt overigens niet onder Python 3, daar is "for line in sys.stdin" wellicht sneller.

edit: is het gebruik van cat verplicht? Het kan nl. sneller met

python script.py < input.txt

Nog sneller is gewoon in Python dat bestand openen...

[Voor 20% gewijzigd door user109731 op 02-04-2009 00:18]

[eghie]

JanDM schreef op woensdag 01 april 2009 @ 23:55:
Hier vind je een aantal manieren.

De snelste is volgens mij dit:

Python:

import sys

lines = sys.stdin.xreadlines()
for line in lines:
  #...

Dit werkt overigens niet onder Python 3, daar is "for line in sys.stdin" wellicht sneller.

edit: is het gebruik van cat verplicht? Het kan nl. sneller met

python script.py < input.txt

Nog sneller is gewoon in Python dat bestand openen...

xreadlines() is sinds 2.3 al deprecated. Dus, die "for line in sys.stdin" is sowieso aan te raden.

[user109731]

eghie schreef op donderdag 02 april 2009 @ 09:49:
[...]
xreadlines() is sinds 2.3 al deprecated. Dus, die "for line in sys.stdin" is sowieso aan te raden.

Ja dat weet ik, vandaar mijn opmerking over Python 3. Ik heb het laatst getest en toen was xreadlines toch sneller, maar ik kan het nu niet meer reproduceren. Dan is "for line in sys.stdin" idd beter.

Python 3.0.1 is trouwens veel trager hierin, ik ga eens een bugreport opzoeken of insturen.
edit: ook direct uit het bestand lezen is langzamer (0,3 seconden voor 2.6 vs. 18 seconden in 3), lijkt me een aardige regressie...
edit 2: IRC-ers zeggen dat het een bekend probleem is in Python 3, IO is herschreven in C voor 3.1. Gebruik van versie 3 raden ze zelfs af

[Voor 21% gewijzigd door user109731 op 02-04-2009 10:21]

[Snake_Y_]

Dank voor de reacties, ik ga die vanavond eens testen...

Bestaat er een snellere manier om string te converteren naar int? Of kan dit enkel gedaan worden met de int()-functie?

[djc]

Snake_Y_ schreef op donderdag 02 april 2009 @ 10:56:
Dank voor de reacties, ik ga die vanavond eens testen...

Bestaat er een snellere manier om string te converteren naar int? Of kan dit enkel gedaan worden met de int()-functie?

Ik denk niet dat int() je bottleneck is. Waarschijnlijk gaat het zonder raw_input() een stuk sneller.

[Soultaker]

Ik zou eerst eens vergelijken met de domste manier:

Python:

import sys
lst = []
for line in sys.stdin:
    lst += map(int, line.split())

Je leest dan wel de hele lijst in het geheugen, wat misschien niet nodig is, maar doet een bestand van 5MB in 2 seconden ofzo, wat prima is voor een scripttaal i.m.o.

(De for line in file... instructie werk al sinds Python 2.4 ofzo en is korter en duidelijk dan readlines, xreadlines, raw_input of whatever, dus dat lijkt me het beste om mee te beginnen.)

Overigens kan raw_input() best traag zijn omdat het bedoeld is om van de console te lezen, dus wellicht worden allemaal fancy console settings gebruikt of I/O geflusht.

Snake_Y_ schreef op donderdag 02 april 2009 @ 10:56:
Bestaat er een snellere manier om string te converteren naar int? Of kan dit enkel gedaan worden met de int()-functie?

Ga er maar vanuit dat int("123") de efficiëntste manier is; deze constructie wordt zo vaak gebruikt dat ik me niet kan voorstellen dat dit onnodig traag is.

[Voor 21% gewijzigd door Soultaker op 02-04-2009 11:02]

[supakeen]

JanDM schreef op donderdag 02 april 2009 @ 10:13:
[...]

Ja dat weet ik, vandaar mijn opmerking over Python 3. Ik heb het laatst getest en toen was xreadlines toch sneller, maar ik kan het nu niet meer reproduceren. Dan is "for line in sys.stdin" idd beter.

Python 3.0.1 is trouwens veel trager hierin, ik ga eens een bugreport opzoeken of insturen.
edit: ook direct uit het bestand lezen is langzamer (0,3 seconden voor 2.6 vs. 18 seconden in 3), lijkt me een aardige regressie...
edit 2: IRC-ers zeggen dat het een bekend probleem is in Python 3, IO is herschreven in C voor 3.1. Gebruik van versie 3 raden ze zelfs af

Python 3 is nog niet klaar voor productie omgevingen. Aangeraden wordt om je huidige applicatie door te ontwikkelen in 2.5, nieuw te starten in Python 2.6 wat een overgangsversie is naar 3 (geeft warnings voor dingen die niet meer werken in 3).

3 is pas volwassen genoeg zodra de alle veelgebruikte modules ook geport zijn. De IO is inderdaad helemaal herschreven en daardoor in 3 een stuk sneller geworden (maar nog niet op niveau van 2.5 AFAIK). Ook is Google een project gestart om CPython (de standaard implementatie) te gaan overzetten naar een LLVM met volledige compatibility waardoor er een kans is dat Python bij afronding van dat project 2-5x meer gaat performen (dat is het doel wat Google zich stelt).

Voor de vraag van de topic starter, je moet dit niet doen via raw_input(), die gebruik je alleen voor input vanaf de command line. Je moet zoals inderdaad in dit topic wordt aangeraden van stdin lezen of het bestand vanuit python zelf openen.

Voor het doorlopen van het bestand dat je naar stdin stuurt zou je een generator comprehension i.c.m een list comprehension kunnen gebruiken als in:

code:

#!/usr/bin/env python
import sys

lst = ([int(i) for i in line.split()] for line in sys.stdin)

Zodat je de lijst niet helemaal in het geheugen hoeft te lezen maar hem per regel kan verwerken.

Als je wel de hele lijst wel in geheugen wil hebben is dit je oplossing:

code:

#!/usr/bin/env python
import sys

lst = [[int(i) for i in line.split()] for line in sys.stdin]

Het generator object kun je alleen benaderen door eroverheen te loopen:

code:

#!/usr/bin/env python
import sys

lst = ([int(i) for i in line.split()] for line in sys.stdin)

for l in lst:
  print lst

Meer over generators hier.

(Veel mensen vinden dit minder leesbaar (wel op 1 regel , ik vind het praktischer)

[Voor 24% gewijzigd door supakeen op 02-04-2009 12:32]

[Snake_Y_]

Na enkele optimalisaties kom ik tot volgende tijden

real	0m5.021s
user	0m4.684s
sys	0m0.284s

Deze zijn een factor 2,5 sneller dan mijn eerste hersenspinsel, en waren snel genoeg om de opdracht binnen de vooropgestelde tijd te volbrengen...

De grootste snelheidswinst verkreeg ik door input in te lezen als string in een fixed array (list), en de conversie te doen met de map-functie.

En hier de code:

Python:

import sys

lst = []                
n = 0
div = 0

def readInput():
    global lst,n
    lst = [0] * n
    i = 0
    for line in sys.stdin:
        lst[i] = line
        i += 1
    lst = map(int,lst)
    return 

def calc():
    global lst,n,div
    output_number = 0
    for i in lst:
       if (i % div == 0):
           output_number += 1 
    print output_number 
    return 
    
if __name__ == '__main__':
    tStr = raw_input().split()
    n    = int(tStr[0])
    div  = int(tStr[1])
    readInput()
    calc()
    pass

[Bryan Tong Minh]

ikanobori schreef op donderdag 02 april 2009 @ 12:16:
[...]

(Veel mensen vinden dit minder leesbaar (wel op 1 regel , ik vind het praktischer)

Ik vermoed dat het hele programma in twee code regels kan:

Python:

#!/usr/bin/python
import sys

n, div = [int(i) for i in raw_input().split(' ', 1)]
print sum((int(i) % div) == 0 for i in sys.stdin)

Waar je naast generators van gebruikt maakt is het feit dat (True == 1)

[Snake_Y_]

@Bryan

Knap dat je dit progje kunt herleiden tot 2 lijntjes, en het is nog eens sneller ook!
'k Heb blijkbaar nog veel te leren over Python

real	0m4.735s
user	0m4.539s
sys	0m0.114s

[Chip.]

offtopic:
Hoe kom je aan die real, user, sys tijden?

[RayNbow]

Wouser schreef op zondag 05 april 2009 @ 22:43:

offtopic:
Hoe kom je aan die real, user, sys tijden?

Het time commando in de bash shell (zie de TS).