Übungen zu Datentypen

[mkeil]

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

[Dauerbaustelle]

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 :)

[mkeil]

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

[mkeil]

Sooo, erster Versuch zu "reverse in eine neue Liste":

Code: Alles auswählen

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

for i in range(0,len(test)):
	temp.insert(i,test[(len(test)-1)-i])

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

[Darii]

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.

[ms4py]

Oder so...

Code: Alles auswählen

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

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

[Dauerbaustelle]

@ms4py: Ist halt O(scary)

[BlackJack]

Wäre das hier geschummelt?

Code: Alles auswählen

In [610]: test = ["test1","test2","test3","test4"]

In [611]: test[::-1]
Out[611]: ['test4', 'test3', 'test2', 'test1']

[mkeil]

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

[BlackJack]

@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.

[Dauerbaustelle]

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

[BlackJack]

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

[Dauerbaustelle]

@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

[mkeil]

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

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

Grüße
mkeil

[BlackJack]

@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:

Code: Alles auswählen

In [669]: sum(xrange(0, 100))
Out[669]: 4950

In [670]: sum(xrange(0, 1000))
Out[670]: 499500

[Dauerbaustelle]

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:

Code: Alles auswählen

[3, 5, 7]
Vergrößern:
[3, 5, 7, leer]
Verschieben:
[3, 5, leer, 7]
[3, leer, 5, 7]
[leer, 3, 5, 7]
Einfügen:
[11, 3, 5, 7]

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])`:

Code: Alles auswählen

reversed = [] # mit einer leeren Ergebnisliste beginnend
jetzt geht man von hinten nach vorn die umzudrehende Liste durch:
  reversed.insert(0, 5) kostet 0 Zeit
  reversed.insert(0, 4) kostet 1 Zeit
  reversed.insert(0, 3) kostet 2 Zeit
  reversed.insert(0, 2) kostet 3 Zeit
  reversed.insert(0, 1) kostet 4 Zeit

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.

[mutetella]

Bei 100 Elementen sind das knapp 5000 Aktionen, ...

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

[cofi]

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.

[EyDu]

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

[mutetella]

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