Das deutsche Python-Forum

Hallo,

ich bin momentan an den Datentypen dran. Hat jemand zufällig "ordentliche" Übungen zu Listen/Tuples/Dictionaries?
Können ruhig auch etwas umfangreicher sein und andere Dinge, die man bis dahin können sollte, beinhalten.

Dann kann ich das ganze noch etwas vertiefen
Danke!

Grüße
mkeil

Ich finde immer ganz lustig, die Methoden von Builtins nachzubauen, z.B.

• `list_extend(l, l2)` (natürlich ohne Verwendung von `list.extend`)
• `list_count(l, x)` (gleichermaßen)
• `list_index(l, x)` (...)
• `list_reverse` (einmal in-place und einmal durch Erzeugung einer neuen Liste)
• `list_sort([cmp])`
• `list_insert(l, x)` -> neue liste
• `list_pop(l, i)` -> neue liste
• `dict_fromkeys(keys)` -> neues dict

Oder du baust dir z.B. ein eigenes `set` unter Verwendung eines `dicts` zum Speichern der Einträge. Oder du baust dir ein `dict` unter Verwendung irgendwelcher anderen Datenstrukturen. usf.

Viel Spaß und zeig' her, falls was sinnvolles rauskommt :)

Danke für die Idee - finde ich nicht schlecht
Erklärungen dazu gibts ja auf http://docs.python.org/tutorial/datastructures.html.

Werde ich mal probieren.

Grüße
mkeil

Sooo, erster Versuch zu "reverse in eine neue Liste":
Ist der Ansatz in Ordnung? Gibt es auch einen Weg, dort ohne insert zu arbeiten?
"temp" hat keine Elemente, deswegen knallt es wenn ich versuche an Stelle x etwas einzufügen.

Ps.: ist es in Ordnung wenn ich die kleinen Aufgaben hier rein stelle? Oder soll ich sie in das Showcase Forum verschieben?
Ist ja noch nichts wildes.

Grüße
mkeil

mkeil hat geschrieben:Ist der Ansatz in Ordnung? Gibt es auch einen Weg, dort ohne insert zu arbeiten?
"temp" hat keine Elemente, deswegen knallt es wenn ich versuche an Stelle x etwas einzufügen.

Ja klar, du kannst entweder von Hinten zählen und append benutzen und/oder die zweite Liste vorher erzeugen (z.B. mit new_list = [None]*len(old_list)), was sowieso zu empfehlen ist, da schneller.

Oder so...

@ms4py: Ist halt O(scary)

Wäre das hier geschummelt?

ms4py hat geschrieben:Oder so...

Code: Alles auswählen

test = ["test1","test2","test3","test4"]
temp = []

for item in test:
    temp.insert(0, item)

Viel besser

@BlackJack: Deinen Code blicke ich noch nicht so
Was macht der genau?

Grüße
mkeil

@mkeil: Bei dem Code von ms4py musst Du Dir aber unbedingt klarmachen warum der von der Laufzeit her sehr ungünstig ist. Das würde ich nur in Ausnahmefällen als Lösung in Betracht ziehen, aber nicht als allgemeine Methode um eine umgekehrte Liste zu erzeugen.

Mein Code benutzt einfach das ganz normale "slicing" auf Listen mit den passenden Werten für Start, Ende, und Schrittweite.

BlackJack hat geschrieben:Mein Code benutzt einfach das ganz normale "slicing" auf Listen mit den passenden Werten für Start, Ende, und Schrittweite.

Das ist ja aber total der Hack!1!! So war mein Spiel nicht konzipiert :-P

@Dauerbaustelle: Deswegen fragte ich ja, ob es geschummelt wäre. Ich nehme an die `reversed()`-Funktion ist auch tabu!?

BlackJack hat geschrieben:@Dauerbaustelle: Deswegen fragte ich ja, ob es geschummelt wäre. :-) Ich nehme an die `reversed()`-Funktion ist auch tabu!? ;-)

Ich ging jetzt mal davon aus, dass du dir des bewusst warst und nur rumtrollen wolltest :) Das Ziel ist es ja nicht, einen Workaround um die Aufgabenstellung zu finden :P

Und was sagt der "Aufgabensteller" zu meiner Lösung?

Und wieso ist der Code von ms4py zur Laufzeit ungünstig?

Grüße
mkeil

@Dauerbaustelle: Ist [::-1] wirklich ein Workaround? Es geht ja darum die Datentypen kennen zu lernen, und das ist eine Eigenschaft von Listen, die interessant zu wissen ist.

@mkeil: Listen sind intern als dynamische Arrays implementiert. Bei jedem `insert()` müssen mindestens alle danach folgenden Elemente um einen Platz nach hinten kopiert werden, damit an der Einfügestelle ein Platz frei wird. Beim Einfügen an Platz 0 sind das also alle bereits in der Liste enthaltenen Elemente. Bei 100 Elementen sind das knapp 5000 Aktionen, bei 1000 Elementen schon fast eine halbe Million Operationen:

Versuch das mal ohne `.insert`, weil das ganz unterirdische Laufzeit hat (siehe gleich). Darii hat doch ganz gute Tipps gegeben.

Zu `insert`: Das hat eine Laufzeit von O(n) (n = Anzahl der Elemente in der Liste), heißt, dass die Dauer einer `insert`-Operation proportional zur Anzahl der Elemente ansteigt.

Hierzu eine kurze Erklärung wie `insert` funktioniert: Ist die Liste zum Beispiel [3, 5, 7] und du fügst etwas am Anfang ein, dann wird die Liste im Speicher zuerst um eines vergrößert und dann werden alle Elemente eins nach hinten verschoben. Danach wird das neue Elemente dann eingefügt. Könnte man sich etwa so vorstellen:
Wie man sieht braucht das Verschieben so viele Schritte wie Elemente in der Liste (hier 3), "läuft" also in Zeit "n" ab. In O-Notation: O(n)

Bei kleinen Listen macht das noch nicht wirklich was aus, wenn deine Liste jetzt aber 1.000 oder 100.000 Einträge hat wird jede Insert-Operation inakzeptabel langsam.

Jetzt zu ms4py `reverse`-Implementation mit `insert` am Beispiel von`reverse([1, 2, 3, 4, 5])`:
Wäre die Liste n lang, bräuchte man 0 + 1 + 2 + ... + n-1 Zeit. Für 10 Elemente bräuchte man dann 45 Zeit, für 100 schon 4950 und für 1000 499500 und das geht so weiter. (Mag mal jemand ne Regressionsfunktion erstellen? :-)

Bessere wäre eine Laufzeit von O(n), wo das umdrehen also immer nur so lange dauert wie Elemente in der Liste und die Dauer nicht wie hier exponentiell steigt.

BlackJack hat geschrieben:Bei 100 Elementen sind das knapp 5000 Aktionen, ...

Warum? Was beweist sum() in diesem Zusammenhang. Geht es hier nicht vielmehr um len()?

Der Post an sich beweist nichts, sondern rechnet nur. Dauerbaustelle's 2. Code Block zeigt _was_ gerechnet wird.[1] Und das faellt eben mit `sum(range(n))` zusammen.

[1] Und zwar die kosten beim Einfügen von `n` Elementen.

Dauerbaustelle hat geschrieben:Bessere wäre eine Laufzeit von O(n), wo das umdrehen also immer nur so lange dauert wie Elemente in der Liste und die Dauer nicht wie hier exponentiell steigt.

Bei mir ist n*(n+1)/2 immer noch quadratisch

Und was geschieht bei [0] + [1, 2, 3]?

Dasselbe wie bei [1, 2, 3].insert(0, 0)?

Oder werden beim 1. Beispiel lediglich 2 Speicherbereiche miteinander verbunden, falls so etwas überhaupt geht...