Optimierung von Histogrammerstellung

[Peak_me]

hallo!

Da ihr mir so gut geholfen habt, mein anderes Programm zu beschleunigen, wende ich mich voller Hoffnung erneut mit einem Optimierungsproblem an euch.

Black Jack hatte mich bei meinem anderen Programm nach einem Histogramm meiner Daten gefragt; bis dahin wusste ich nicht was das ist.
Ich hab dann ein wenig mit Zufallszahlen und Histogrammen rungespielt und die Verteilungen davon sind ja höchst interessant.
Doch je größer die zu untersuchende Menge wird, je länger dauert die Untersuchung auch.

Ich hab mal eine Datei mit 5 Millionen Zufallswerten erstellt, von denen jeder einen ASCII-Wert von 33 bis 126 (Tastaturbereich) annehmen kann.
http://rapidshare.com/files/456425392/a.txt

Ihr könnt euch aber auch ne eigene erstellen, ich habs so gemacht:

Code: Alles auswählen

datei=open(pfad, "w")
zufall=''
for i in range(5000000):
	zufall+=chr(randint(33,126))
datei.write(str(zufall))
datei.close

Jetzt will ich davon ein Histogramm erstellen, welches in einer Liste mit 94 Elementen abgelegt werden soll.
Das erste Element repräsentiert, wie oft das ASCII-33-Zeichen vorgekommen ist,
das zweite Element repräsentiert, wie oft das ASCII-34-Zeichen vorgekommen ist...

Ich habe das so gelöst:

Code: Alles auswählen

liste=94*[0]
for i in zufall:
	liste[ord(i)-33]+=1)

benötigte Zeit für die oben erwähnte Datei: 2,12 s

Da ich nicht weiß, wie ord() programmiert ist, habe ich es auch mal so probiert:

Code: Alles auswählen

for i in zufall:
	if i == "!":
		liste[0]+=1
	[...die anderen Möglichkeiten]
	if i == "~":
		liste[93]+=1

Da dauert es aber 40 Sekunden, also ist es 20-Mal langsamer als ord().


Vielleicht habt ihr noch andere Ideen,
Gruß,
Paul

[Hyperion]

Ich vermute mal, dass das mit einem defaultdict schneller gehen sollte. Natürlich ist ein Integer-Index für ein dict suboptimal; andererseits repräsentiert das ja ein Zeichen, welches man stattdessen als Schlüssel nehmen könnte

Ungetestet

Code: Alles auswählen

from collections import defaultdict

histo = defaultdict(int)
for value in zufall:
    histo[value] += 1

[Peak_me]

*augenreib*

Code: Alles auswählen

from collections import defaultdict
histo = defaultdict(int)
for value in zufall:
    histo[value] += 1

funktioniert einwandfrei, das Ergebnis ist übersichtlicher und das Verfahren ist ca. 50% schneller als ord().

[BlackJack]

@Peak_me: Apropos Geschwindigkeit: Das ``zufall +=`` beim Erzeugen der Daten ist keine gute Idee! Zeichenketten sind unveränderbar, das heisst wenn Du das machst, wird eine neue Zeichenkette erstellt, in welche die Inhalte der beiden alten Zeichenketten hintereinander kopiert werden. Das heisst wenn ``zufall`` ein Zeichen (=Byte) enthält, wird eine neue Zeichenkette mit Länge zwei erstellt und das alte ``zufall`` dort hin kopiert und das neue Zeichen ans Ende. Beim nächsten Durchlauf werden dann schon drei Zeichen kopiert, dann vier, fünf, usw. bis beim vorletzten Schleifendurchlauf (5 Millionen - 1) Zeichen kopiert werden und beim letzten dann 5 Millionen.

Du hast einfach nur Glück gehabt, das neuere CPython-Implementierungen da einen kleinen Trick zum Optimieren verwenden, denn sonst wäre Dir an der Laufzeit sicher aufgefallen dass da eigentlich ca. 12½ *Terabyte* Daten im Speicher bewegt werden müssten, nur im 5 MB Zufallsdaten zu erzeugen. Auf diese Optimierung sollte man sich aber nicht verlassen. Üblicherweise sammelt man die Daten in einer Liste und fügt die am Ende dann mit ``''.join(daten)`` zusammen.