Parameter vs. Dict vs. List

[Seeker]

Hi!

Wie transferiert man Informationen am Besten von einem Ort zum anderen?
Das bei 100 Parametern ohne dict o. ä. alles völlig unüberblickbar wäre, ist schon, klar, aber wie ist es bei z.B. 5-6 Parametern?

Ich habe ein Progrämmchen geschrieben, wo man dem Rechner eine range gibt, woraus er eine beliebige Zahl wählt, und diese dann versucht zu erraten. Da ich nichts Besseres zu tun hatte, habe ich dieses Programm in einen kleinen (nicht ganz ernst zu nehmenden) Versuch umgewandelt.

In meinem Versuch habe ich drei Versionen benutzt: Einmal die Hauptvariablen als Parameter, einmal in einem dict und einmal in einer Liste.

Dazu habe ich alle drei je drei mal in unterschiedlicher Reihenfolge je 1000 mal eine Zahl zwischen 1 und 101 erraten lassen.

Selbstverständlich ist dies kein aussagekräftiger Versuch, da das Programm nicht spezifisch auf die Fragestellung ausgerichtet ist, und per Zufall gewisse Durchläufe natürlich längsämer sein könnten (bei 3000 je sollte der Fehler jedoch ziemlich klein sein).
Aber ich fands doch ein klein wenig interessant und habe deshalb die Resultate gepostet .

Nach jedem "Erraten" hat es z.T. eine message geprinted, wenn er besonders wenig/viele Versuche gebraucht hat. (um zu sehen, ob dieses nicht konstante Rückgreifen einen gröberen Einfluss hätte - hat es, aber bei allen etwa gleich).

Meine Resultate:
Durchschnittszeiten für 1000 "erraten + ev.message":
Parameter: 1.04431 s
Liste: 1.26478 s
Dictionary: 1.20193 s

Parameter scheinen da die Oberhand zu haben. Allerdings muss ich hinzufügen, dass das dict dafür in den Resultaten sehr konstant war und es war dafür durchschnittlich schneller beim aufrufen der Werte für die 'messages'.

lg Seeker


PS: Bei Interesse noch den Code in der Parameter-Version (ich habe bei den 'messages' noch die Variablen upper - und lower_bounds eingefügt, waren beim Test noch fest):
http://paste.pocoo.org/show/141833/

[problembär]

Da ich nichts Besseres zu tun hatte

Und nun meinst Du, ich hätte auch nichts Besseres zu tun, als das, was Du da aus Langeweile gemacht hast, nachzuvollziehen .

Gruß

[BlackJack]

@Seeker: Ich weiss nicht ob ich die Frage so recht verstehe. Hast Du bei dem gezeigten Programm Varianten geschrieben, bei denen die Funktionen nur ein Argument bekommen, nämlich ein Dictionary oder eine Liste mit all den Werten, die im gezeigten Beispiel als einzelne Argumente übergeben werden? Falls ja, hat die Frage IMHO absolut nichts mit Laufzeit zu tun, sondern mit Lesbarkeit. Soll heissen man versteckt nicht ohne Not mehrere Argumente in einer Datenstruktur. Selbst wenn das schneller wäre.

Zum Quelltext: Um Operatoren sollte man Leerzeichen setzen. Insbesondere sollte das auf beiden Seiten gleichmässig passieren und nicht wie beim ``%`` links ja und rechts nein. Genau so etwas führt vermehrt zu Missverständnissen, dass ``%`` irgendwie eine besondere Syntax sei, oder so.

In der Funktion `guess()` gibt es einen lokalen Namen `guess`, das ist verwirrend. Mir ist nicht so ganz klar, was da gemessen werden soll!? Bei den ganzen Messungen misst Du auch immer Textausgaben mit, das ist keine gute Idee, weil dass das Ergebnis extrem verzerren kann, je nachdem wo der Text ausgegeben wird, was für ein Terminal verwendet wird, ob die Gafikkarte 2D beschleunigt oder nicht, oder ob da vielleicht sogar OpenGL verwendet wird und so weiter. Ausserdem sollte man aufpassen, dass man die Operationen zum Verwalten der Messungen nicht mit misst. Was sollen die beiden ``if``\s? Die machen IMHO nur Sinn, wenn `lower_bound` den Wert 0 hat, sonst steht `count` doch gar nicht in der richtigen Beziehung zu den anderen Werten!? Dann wären aber nicht alle Teile der Bedingungen sinnvoll.

Die ``while``-Schleifen in `guess()` und die Letzte in `main()` sollten besser ``for``-Schleifen sein. Bei beiden weiss man vor Schleifeneintritt wie oft sie durchlaufen werden, bzw. wie oft das maximal passieren kann.

Die erste hätte ich so formuliert (ungetestet):

Code: Alles auswählen

    for count in xrange(len(possible_numbers)):
        if possible_numbers.pop(randrange(len(possible_numbers))) == number:
            break

Und die Zweite so:

Code: Alles auswählen

    for dummy in xrange(iteration_count):
        guess(statistics, times, lower_bound, upper_bound)

Du solltest Abstand von `input()` nehmen. Da können noch ganz andere Sachen als ein `NameError` passieren -- die Eingabe wird als Python-Quelltext interpretiert! Zur Eingabe von Zeichenketten verwendet man `raw_input()`.

Warum `t1` bis `t4`? Insbesondere warum in `main()` nicht auch `t1` und `t2`? Oder *verständliche* Namen. Jeweils `start_time` und `runtime` zum Beispiel.

[Seeker]

Danke für die Antwort =).

Hast Du bei dem gezeigten Programm Varianten geschrieben, bei denen die Funktionen nur ein Argument bekommen, nämlich ein Dictionary oder eine Liste mit all den Werten, die im gezeigten Beispiel als einzelne Argumente übergeben werden? Falls ja, hat die Frage IMHO absolut nichts mit Laufzeit zu tun, sondern mit Lesbarkeit.

Ganz genau. Wie schon beschrieben ist mir das mit der Lesbarkeit klar... Bei so 5-6 Argumenten ist Lesbarkeit halt auch individuell. Ich selber finde einfache Parameter sehr übersichtlich (bis vielleicht 8 ). Listen sind in diesem Beispiel natürlich schlecht übersichtlich, da man überall nur list[0], list[1] usw. hat und nicht genau weiss, was was ist. Dict ist zwar klar... aber ein wenig mühsam, weil halt jedes mal noch der name des dict, die klammern und "" drankommen. Finde ich wieder weniger übersichtlich.
Aber wie schon gesagt, dies kommt ganz auf die Anwendung an.

Mein Ziel war es, eventuell zu sehen, welche Art von "Verlinkung" zwischen den Teilen des Programms am Besten ist. Ich werde vermutlich python u.a. für mathematische Probleme benutzen. Bei solchen sind sehr hohe Iterationszahlen nicht selten, und dann kommt es auf die Geschwindigkeit halt schon an =).

Naja, es war nicht meine Idee, den Quelltext perfekt zu machen. t1-t4 sind so, weil ich t3 und t4 erst nachträglich hinzugefügt habe. Im Übrigen ist noch ein unnötiges (bzw. fehl am Platz) print drin.
Ganz ursprünglich musste der Benutzer raten. Dann habe ich den automatischen "Ratmechanismus" eingefügt und die wiederkehrenden Zahlen vermieden. Schliesslich habe ich einfach noch die verschiedenen Zeiten, Ausgaben, den Loop und die Möglichkeit, sowohl range wie auch Anzahl Durchgänge zu bestimmen, hinzugefügt.

hm.. ok, das mit dem guess ist vielleicht verwirrend, daran hab ich gar nicht gedacht. (Beim 'manuellen' Spiel war eben guess() 'main()' genannt... und beim Umwandeln habe ich die Doppelbesetzung nicht bemerkt)

Und das mit dem beinhalteten Text in der Berechung habe ich oben auch bemerkt =).

Die machen IMHO nur Sinn, wenn `lower_bound` den Wert 0 hat, sonst steht `count` doch gar nicht in der richtigen Beziehung zu den anderen Werten

Ich folge da nicht ganz... der count beginnt ja mit 1 (erster Durchgang).

Die ``while``-Schleifen in `guess()` und die Letzte in `main()` sollten besser ``for``-Schleifen sein. Bei beiden weiss man vor Schleifeneintritt wie oft sie durchlaufen werden, bzw. wie oft das maximal passieren kann.

Danke für den Tipp. Bin jetzt grad schon ein bisschen müde, aber ich probier das morgen mal aus

[BlackJack]

@Seeker: Was sollen die ``if``-Abfragen denn bewirken/bedeuten? Wenn die Grenzen 0 und 10 sind, dann bekomme ich ein "Lob", wenn ich es in maximal zwei Versuchen geschafft habe, und der Computer "macht sich lustig" wenn ich mehr als 8 Versuche brauche. Wenn die Grenzen 3 und 13 sind, ist die Menge der zu ratenden Zahlen genau so gross, aber ich bekomme das "Lob" *nicht* wenn ich beim ersten oder zweiten mal richtig liege, sondern nur, wenn ich 3-4 mal raten muss. Und die "Lolz"-Ausgabe kann dann gar nicht kommen, weil `count` nie über 10 kommen kann, weil es ja nur 10 Möglichkeiten gibt. Wozu soll das gut sein!?

[Seeker]

Ah, klar, jetzt weiss ich, was du meinst. Natürlich, stimmt. Ich habe bis jetzt immer bei lower_bound = 1 angefangen, deshalb ist es mir nie eingefallen. (der count beginnt ja bei 1 und hört spätestens bei (upper_bound-1) auf).

Code: Alles auswählen

    for count in xrange(len(possible_numbers)):
        if possible_numbers.pop(randrange(len(possible_numbers))) == number:
            break

Beim for... in... finde ich es eigentlich direkter, wenn man einfach True benutzt, anstatt für jeden Durchlauf eine neue xrange() zu berechnen, nicht? Klar gehts auch, aber weshalb nicht einfach das while True: benutzen?

@problembär:
Hat ja niemand behauptet, dass dus nochvollziehen musst...

Neue Version:
Veränderungen:
guess() zu game() umgetauft. Die Ausgabe jeder Zeit ist weg, die Zeit berechnet nun wirklich nur das Raten, ohne das "Lob".
Das eine 'while' habe ich belassen, aber die beiden loops doch verändert.
Die Ausgabe des "Lobs" ist nun auf die variable Range angepasst. Der upper_bound ist jetzt auch ein bisschen 'alltäglicher', d.h. inbegriffen (damit wenn man die Zahlen von 1-20 will man nicht 21 als upper_bound geben muss). Sonst noch ein paar Details repariert.

http://paste.pocoo.org/show/141862/

[snafu]

Und welchen Sinn hat das jetzt? In Python nehme ich den Datentypen, der am besten zu meinem Vorhaben passt. Bei wenigen Werten können das sicher Konstanten auf Modulebene sein. Wenn es mehr wird, nehme ich aber trotzdem ein Wörterbuch, ganz gleich ob beim Lookup 200ms Unterschied zu globalen Namen sind. Wenn dies das Zünglein an der Waage ist, sollte man IMHO überlegen, ob Python die richtige Sprache zur Implementierung der Datenstruktur ist. Auslagerungsmöglichkeiten in C oder in externe Datenbanken sind ja vorhanden. Je nachdem, was man vor hat.

[Seeker]

@snafu:
Ja, klar. Python ist momentan meine erste und einzige (abgesehen von Q-Basic ) Programmiersprache, deshalb ist es schwer für mich, zu sagen, welche Programmiersprache in welchem Fall nun besser wäre.
An der Uni benutzen sie oft so oder so wissenschaftsspezifische Programme wie MatLab.
Der Gedanke war einfach, dass wenn ich weiss, wie lange Python für die jeweiligen Varianten braucht, dann kann ich zukünftig besser darauf eingehen. So unter dem Motto. "Ich habe gerade Zeit.. und schaden kanns nicht "
Es gibt ja oft Bespiele, wo mehrere Wege möglich sind... und zur Zeit weiss ich meist nicht, welcher Weg 'besser' ist. Die Zeit (abgsehen von der Übersichtlichkeit) ist halt ein simples Kriterium, welches auch ich als Anfänger nutzen kann.
Und wie schon gesagt, es war kein wissenschaftliches Experiment, und nebenbei habe ich nicht vor, in nächster Zukunft irgendwelche 200-stelligen Primzahlen zu untersuchen .

[BlackJack]

@Seeker: Was ist denn an ``while True:`` und dem manuellen hochzählen von `count` einfacher als an der ``for``-Schleife!? Bei der ``for``-Schleife wird dem Leser zum Beispiel auch ohne den Inhalt anzuschauen schon klar, dass das keine Endlosschleife ist. Bei ``while`` muss man sich erst einmal klar darüber werden, dass das ``break`` auch auf jeden Fall in endlicher Zeit mal erreicht wird. Und da Du ja Zeitmessungen machst: Es könnte durchaus sein, dass die ``for``-Schleife schneller ist.

Ich weiss nicht auf welcher Ebene "Durchlauf" nun gemeint war, aber bei Schleifen wird der Ausdruck nach dem ``in`` genau *einmal* am Anfang der Schleife ausgewertet. Und für jede Iteration im Hauptprogramm ein `xrange` Objekt zu erstellen ist auch nicht besonders aufwendig.

[Seeker]

@Blackjack:
ok, danke =). Naja, ich hatte mir einfach überlegt, dass das Programm beim "while" ja nur überprüfen, ob while noch "True" ist, während es bei for, in/xrange/len() etc. doch allerlei (wenn auch kleiner) Dinge berechnen muss. Und bei sehr grossen ranges könnte dies das Programm ev. doch beträchtlich verlangsamen. Aber ich probiers mal aus =).
Deine Variante mit dem 'abtrennen' von zufälligen Indizes ist übrigens bedeutend schneller =). Ich habe heute eine Zahl zwischen 1 und 10^6 gesucht. Während die Indizes-Version nach ca. 15 min die Zahl gefunden hatte, hat meine ursprüngliche Version (mit der Liste, wo die Zahlen konkret ausgewählt und gelöscht werden) nichts geliefert (bzw. habs nach einiger Zeit abgebrochen).

[BlackJack]

@Seeker: Was müssen denn da für Dinge berechnet werden? Einmal `len()`, das war's doch im Grunde schon. `count` initialisieren und hochzählen macht man in beiden Fällen. Intern im `xrange` Objekt geht das wahrscheinlich sogar schneller als in Python Bytecode für das explizite ``count += 1``.

[Seeker]

@Blackjack:
Das count += 1 muss ich aber so oder so belassen, da ich ja am Schluss angebe, wie viele Male im Durchschnitt geraten wurde.

Das 'count' bei der for... if... Schleife ist ja jedesmal 0, oder? len() wird einfach jede "Runde" um 1 kleiner, bis 0 das einzig vorhandene Glied ist, zu welchem Zeitpunkt die Schleife dann beendet wird.

Ich probiere das Programm am Besten einfach mal in beiden Varianten aus...

*EDIT*:
Also... Resultate:
Ich habe drei Versionen. Einerseits meine while-Schleife, dann deine for ... in ... Schleife, und dann noch diese modifizierte for... in... Schleife:

Code: Alles auswählen

    length = (possible_numbers + 1)
    for pick in xrange(length-count):
        if possible_numbers.pop(randrange(len(possible_numbers))) == number:
            break
        count += 1

Ich habe alle drei je 100 Zahlen zw. 1 und 100'000 finden lassen. Bei solch kleinen Experimenten sind die Resultate halt nicht ganz genau, aber es lassen sich auf jeden Fall keine grösseren Geschwindigkeitsunterschiede feststellen (wenn ich wählen müsste, dann wäre deine for... in ... Schleife die Gewinnerin):

while: Durchschnitt: 50'670 mal geraten, 3,612 Sekunden pro Zahl
for ... in ... #1: Durchschnitt: 53'816 mal geraten, 3,722 Sekunden pro Zahl
for ... in ... #2: Durchschnitt: 46'230 mal geraten, 3,409 Sekunden pro Zahl

Nächster Versuch:
Eine Zahl zwischen 1 und 10^6 finden.
Lustigerweise waren alle schnell fertig. Die while-Schleife braucht am meisten guesses mit 190'000, beide anderen waren unter 100'000.
Geschwindigkeitsmässig keine klaren Unterschiede, 'while' war vielleicht leicht langsamer.
Allerdings muss ich hinzufügen, dass IDLE bei der Ausführung der for... in... Schleife 2 mal abgestürzt ist!! Der Grund ist schwer zu beurteilen... aber ein bisschen merkwürdig ist es schon.

Naja, für mich ist das ganze abgeschlossen. Geschwindigkeitsmässig besteht kein grosser Unterschied, wenn, dann ist die for... in... Schleife leicht schneller. Bei grossen Zahlen überfordert die for... in... Schleife allerdings z.T. IDLE, weshalb alles abstürzt. =)

[BlackJack]

@Seeker: Nein, das ``count += 1`` musst Du nicht belassen. Jedenfalls nicht *in* der Schleife. Das wird von der ``for``-Schleife schon an die richtigen Werte gebunden und vor allem nicht immer an 0. Wie kommst Du denn auf diese komische Idee!? Und das mit `len()` verstehst Du wohl auch falsch. Ich habe es doch geschrieben: Der Ausdruck hinter dem ``in`` wird *genau einmal* ausgewertet. Da werden `len()` und `xrange()` *einmal* vor dem dem ersten Schleifendurchlauf aufgerufen und *nicht* bei *jedem* Schleifendurchlauf.

Bei der Schleife in Deinem letzten Beitrag wird `pick` anscheinend nicht verwendet und `count` völlig unnötig mitgezählt.

Die Messungen sind ein wenig sinnlos, weil Du da zuviel Zufall drin hast. Wenn Du vergleichen willst, dann sollten alle mit den selben Zufallsfolgen arbeiten. Und insbesondere sollten bei der ``while``-Schleife nicht so deutlich mehr Rateversuche benötigt werden, sonst vergleichst Du da anscheinend nicht die Geschwindigkeit zwischen ``while`` und ``for`` sondern auch algorithmisch unterschiedliche Ansätze.

Ich kann nicht so recht glauben, dass ``for`` oder IDLE schuld sind, ich vermute mal eher Du hast irgendwo `range()` mit grossen Zahlen verwendet und das hat Dir einfach den Hauptspeicher gesprengt. Du hast da weiter oben etwas von 10^9 geschrieben. Dafür bräuchte man alleine für reine 32-Bit-Integer schon 3,7 Gigabyte an Speicher.

[Seeker]

@BlackJack:
Hoppla... das hatte ich überlesen =/. Ich dachte immer, dass bei jedem Schritt das for... in... wieder berechnet werden muss. Jetzt verstehe ich auch, weshalb du for 'count' in... genommen hattest.
Dann ist der ganze Test auch wirklich eher sinnlos, da die Zahl das Statement nur ein einziges Mal durchläuft... da dürfte der Zeitunterschied (wenn vorhanden) weit hinter der 5. Nachkommastelle liegen.
Naja, dann wär das ja geklärt =).

Ich habe nur xrange noch so eingestellt, dass count wirklich bei 1 beginnt. (ich hätte auch am Schluss einfach count = count + 1 machen können... aber so gefällts mir ^^)

Code: Alles auswählen

for count in xrange(1,len(possible_numbers)+1):
        if possible_numbers.pop(randrange(len(possible_numbers))) == number:
            break

Und sry, das oben war ein Schreibfehler, es waren (wie beim erneuten Versuch) 'nur' 10^6.
Ich könnte es irgendwann mal zum Spass über 10^7 laufen lassen, sehen ob was rauskommt... wird halt ne Weile dauern, schätzungsweise ca. 3 Stunden ^^ (falls es nicht in der Zwischenzeit abstürzt... mein laptop ist nicht das neuste Modell).

Die Messungen sind ein wenig sinnlos, weil Du da zuviel Zufall drin hast. Wenn Du vergleichen willst, dann sollten alle mit den selben Zufallsfolgen arbeiten.

Schon klar... habs auch oft erwähnt. Bei mehreren Tausend Durchgängen sollte der Zufall ausgeglichen sein. Allerdings wollte ich nicht den ganzen Tag mit diesem kleinen Test verbringen, deshalb nur 100 Versuche.

Und insbesondere sollten bei der ``while``-Schleife nicht so deutlich mehr Rateversuche benötigt werden, sonst vergleichst Du da anscheinend nicht die Geschwindigkeit zwischen ``while`` und ``for`` sondern auch algorithmisch unterschiedliche Ansätze.

Wie meinst du das? Die Rateversuche sind ja zufällig. Der Algorithmus war bei allen der gleiche.

[BlackJack]

@Seeker: Wenn der grundlegende Algorithmus gleich bleibt, dann sollten über viele Versuche gemittelt auch ähnliche Zahlen an benötigten Rateversuchen herauskommen. 190000 vs. <100000 ist da schon eine ziemlich grosse Abweichung.

[Seeker]

@Blackjack:
Beim Raten der Zahl zwischen 1 und 1000000 habe ich je nur einen Durchlauf gemacht. Schon wenn ich je 10 Durchläufe hätte machen wollen, hätte es wahrscheinlich über 3 Stunden gedauert. (Ohne Abstürze einzuberechnen)

[EyDu]

Abstürze ?! Das hört sich jetzt nicht nach einer vertraulichen Messung an.

[Seeker]

Hehe . Das mit den Abstürzen war ein wenig ironisch gemeint.

Ich habe heute das Programm einmal mit der commandline (statt IDLE) laufen lassen. Habe eine Zahl zwischen 1 und 10'000'000 gesucht. Nach ca. 5 Stunden habe ich abgebrochen ^^. Aber abgestürzt ist es nicht .

Vielleicht würde ein neuerer PC was liefern... bei meinem ist die Grenze auf jeden Fall bei 1'000'000 =).

[BlackJack]

@Seeker: Da wird auch kein schnellerer Rechner helfen, der Algorithmus hat einfach eine quadratische Laufzeit. Ich stehe mit der Wahrscheinlichkeitsrechnung so ein bisschen auf dem Kriegsfuss, darum erzähle ich jetzt wahrscheinlich Stuss, aber wenn der Zufallsindex im Mittel in der Mitte der Liste mit den Möglichkeiten liegt, und man im Mittel die Hälfte der am Anfang zur Verfügung stehenden Möglichkeiten Versuche benötigt um einen Treffer zu landen, dann sind das 1.249.999.975.000.000 Elemente die im Mittel kopiert werden müssen. Angenommen ein Element kopieren dauert eine Nanosekunde, dann läuft das Programm im Mittel ca. 14½ Tage. Und Du gibst schon nach 5 Stunden auf.

Falls es um das Bestimmen von `count` geht, könnte man das auch so in linearer Laufzeit machen:

Code: Alles auswählen

def test(needle, n):
    possibilities = range(n)
    random.shuffle(possibilities)
    return possibilities.index(needle) + 1

[Seeker]

wenn der Zufallsindex im Mittel in der Mitte der Liste mit den Möglichkeiten liegt, und man im Mittel die Hälfte der am Anfang zur Verfügung stehenden Möglichkeiten Versuche benötigt um einen Treffer zu landen, dann sind das 1.249.999.975.000.000 Elemente die im Mittel kopiert werden müssen

14 Tage?? Meine Güte... xD

also... ich bin mir nicht ganz sicher ob ich das richtig aufgefasst habe ^^, aber heisst dies, dass bei random() jeder index durchgegangen wird bis er gestoppt wird??...
Der Wahrscheinlichkeitsteil wär noch ok... aber Permutationen & Co. hab ich noch nicht in mein Herz geschlosse =D. Obwohl... ohne gehts leider ned ^^.
Und... sind mit Elementen Zahlen/Objekte oder 0 und 1 gemeint?

Falls es um das Bestimmen von `count` geht, könnte man das auch so in linearer Laufzeit machen:

Ich folge nicht ganz... also "count" funktioniert jetzt ja ganz gut...
Mein Verständnis der Zeilen:
1. test(Zahl aus der zukünftigen range? =/, Zahl)
2. Liste der Möglichkeiten (0 bis n-1)
3. Liste wird geshuffelt
4. kleinstmöglicher Index der gesuchten value (needle) in der Liste +1

Was genau soll das bewirken?