Warum haben Tupel keine .index(x)-Methode?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
nkoehring
User
Beiträge: 543
Registriert: Mittwoch 7. Februar 2007, 17:37
Wohnort: naehe Halle/Saale
Kontaktdaten:

Donnerstag 17. Januar 2008, 01:27

@Birkenfeld: Kannst du denn mal kurz und knapp (mit C-Kenntnissen als Voraussetzung) erlaeutern, wie sich Tupel und Lists noch so im Speicher unterscheiden, außer eben das die Liste veraenderbar ist und das Tupel nicht?

Also ich stelle mir das ungefaehr so vor:
Ein Tuple entsteht, indem einfach die zusammenaddierte Bytegroesse des Tuple-Inhalts alloziiert und das entstandene Objekt nicht mehr angefasst wird. Eine Liste brauch unmengen an Zusatzfunktionen. Sie muss sich staendig neualloziieren und ihren Inhalt veraendern koennen. Das muss ein Tuple nicht.

Aber aendert das etwas an der Geschwindigkeit? Schließlich ist der Abruf eines einzelnen Objektes innerhalb eines Tuples oder einer Liste doch das gleiche. Mache ich also mit einer Liste das gleiche wie mit einem Tuple, sollte es doch speicher- und geschwindigkeitstechnisch keinen Unterschied machen (außer eben bei der erwaehnten Sache mit der Ueberalloziierung, bei großen Listen)... liege ich da richtig?

@Goswin: Ich glaube nicht das es effizienter ist, ein zusaetzliches Dictionary zu bemuehen. Ein einfaches durchlaufen durch eine Liste um ein Objekt darin zu finden, sollte recht schnell gehen... auch bei hunderttausenden Objekten.
Das Dictionary hingegen wuerde riesengroß werden. Ein unnoetiger Klotz den ein bisschen mehr Prozessorlast ohne weiteres ueberfluessig macht.


Gruß
NKoehring
[url=http://www.python-forum.de/post-86552.html]~ Wahnsinn ist auch nur eine andere Form der Intelligenz ~[/url]
hackerkey://v4sw6CYUShw5pr7Uck3ma3/4u7LNw2/3TXGm5l6+GSOarch/i2e6+t2b9GOen7g5RAPa2XsMr2
EyDu
User
Beiträge: 4871
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Donnerstag 17. Januar 2008, 01:37

nkoehring hat geschrieben: Ein einfaches durchlaufen durch eine Liste um ein Objekt darin zu finden, sollte recht schnell gehen... auch bei hunderttausenden Objekten.
Das Dictionary hingegen wuerde riesengroß werden. Ein unnoetiger Klotz den ein bisschen mehr Prozessorlast ohne weiteres ueberfluessig macht.
Da liegst du aber vollkommen daneben ;-) Das Finden eines Elements in einer Liste liegt in O(n), da Suchen in einem Dictionary bei vernünftigen Hashwerten in O(log n) und das macht sich bei vielen (hundert)tausend Anfragen deutlich in der Laufzeit bemerkbar.
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5555
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Oberhofen im Inntal (Tirol)
Kontaktdaten:

Donnerstag 17. Januar 2008, 07:52

nkoehring hat geschrieben:Ich glaube nicht das es effizienter ist, ein zusaetzliches Dictionary zu bemuehen.
Hallo NKoehring!

Innerhalb eines Dictionaries kann **unglaublich schnell** nach einem Schlüssel gesucht werden. Wenn ich den Index eines Eintrags einer Liste nicht weiß, dann muss diese Liste von oben nach unten durchlaufen werden. Das ist im Gegensatz zur Verwendung eines Dictionaries **unglaublich langsam**. :-)

mfg
Gerold
:-)
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Benutzeravatar
nkoehring
User
Beiträge: 543
Registriert: Mittwoch 7. Februar 2007, 17:37
Wohnort: naehe Halle/Saale
Kontaktdaten:

Donnerstag 17. Januar 2008, 10:37

Ja da habt ihr natuerlich beide recht... Irgendwie hab ich da wohl bloedsinnig gedacht, als ich das schrieb.

Aber dann sollte er das Tuple wegwerfen und ganz auf ein Dict umstellen... ich kann mir jedenfalls nicht vorstellen, warum es sinnvoll sein sollte *beides* mit sich zu fuehren.
[url=http://www.python-forum.de/post-86552.html]~ Wahnsinn ist auch nur eine andere Form der Intelligenz ~[/url]
hackerkey://v4sw6CYUShw5pr7Uck3ma3/4u7LNw2/3TXGm5l6+GSOarch/i2e6+t2b9GOen7g5RAPa2XsMr2
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Donnerstag 17. Januar 2008, 19:33

nkoehring hat geschrieben:@Birkenfeld: Kannst du denn mal kurz und knapp (mit C-Kenntnissen als Voraussetzung) erlaeutern, wie sich Tupel und Lists noch so im Speicher unterscheiden, außer eben das die Liste veraenderbar ist und das Tupel nicht?
Wie gesagt, nur durch die Überallozierung.
Also ich stelle mir das ungefaehr so vor:
Ein Tuple entsteht, indem einfach die zusammenaddierte Bytegroesse des Tuple-Inhalts alloziiert
Pro Objekt ist das ein Pointer.
und das entstandene Objekt nicht mehr angefasst wird. Eine Liste brauch unmengen an Zusatzfunktionen. Sie muss sich staendig neualloziieren und ihren Inhalt veraendern koennen. Das muss ein Tuple nicht.
Diese neu allozierenden Funktionen rufst du ja nicht auf, wenn du eine nichtveränderliche Liste hast. Die Funktionen an sich belegen ja keinen Platz pro Liste.
Aber aendert das etwas an der Geschwindigkeit? Schließlich ist der Abruf eines einzelnen Objektes innerhalb eines Tuples oder einer Liste doch das gleiche. Mache ich also mit einer Liste das gleiche wie mit einem Tuple, sollte es doch speicher- und geschwindigkeitstechnisch keinen Unterschied machen (außer eben bei der erwaehnten Sache mit der Ueberalloziierung, bei großen Listen)... liege ich da richtig?
Ganz genau.
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Donnerstag 17. Januar 2008, 20:23

Ansonsten haben Tuples noch einen festen Hash und einige Optimierungen. Wenn ich mich nicht täusche sind alle leeren Tuples das gleiche Objekt und für Tuples unter einer bestimmten Größe wird glaub ich auch das letzte befreite Tuple nicht dealloct damit das nächste malloc wegfällt. Und dann sind noch ein paar Bytes Unterschied im struct.
TUFKAB – the user formerly known as blackbird
Benutzeravatar
Goswin
User
Beiträge: 361
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen

Donnerstag 24. Januar 2008, 12:21

Die folgende Tabelle zeigt meine Vorstellungen vom (bei Datenstrukturen mit n>>1 Items asymtotischen) Zeitaufwand für einige Operationen an den wichtigsten Python-Datenstrukturen. Bei List und Tuple sind key und place natürlich dasselbe. Strings stelle ich mir genauso wie Tuples vor. Anscheinend ist List fast nur für die append(val)-Operation interessant.

Ich programmiere unter Berücksichtigung dieser Annahmen, und freue mich natürlich darüber, wenn falsche Annahmen berichtigt werden. Ohne zu wissen, wie diese Datenstrukturen und deren Methoden implementiert sind, kann natürlich niemand sichere Aussagen über ihren Zeitaufwand machen.

Code: Alles auswählen

#  OPERATION           DICT          LIST          TUPLE
#
# val[key]            O(log n)      O(n)          O(log n)
# val[place]          O(n)          O(n)          O(log n)
# insert(key,val)     O(log n)      O(n)          O(n)
# insert(place,val)   O(n)          O(n)          O(n)
# change(key,val)     O(log n)      O(n)          O(log n)
# change(place,val)   O(n)          O(n)          O(log n)
# append(val)         O(n)          O(log n)      O(n)
(Einige Operationen wie change() sind nicht unbedingt in die Sprache eingebaut, ich meine damit umgangssprachlich, was geschehen soll)
Zuletzt geändert von Goswin am Donnerstag 24. Januar 2008, 15:53, insgesamt 1-mal geändert.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Donnerstag 24. Januar 2008, 13:11

Besonders aussagekräftig finde ich die Laufzeiten von Tupeln bei ``insert(key,val)``, ``insert(place,val)``, ``change(key,val)``, ``change(place,val)`` und ``append(val)``.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
mkesper
User
Beiträge: 919
Registriert: Montag 20. November 2006, 15:48
Wohnort: formerly known as mkallas
Kontaktdaten:

Donnerstag 24. Januar 2008, 13:12

Goswin hat geschrieben:Ohne zu wissen, wie diese Datenstrukturen und deren Methoden implementiert sind, kann natürlich niemand sichere Aussagen über ihren Zeitaufwand machen.
Ausprobieren? ;)
BlackJack

Donnerstag 24. Januar 2008, 13:15

@Goswin: Könntest Du vielleicht nochmal angeben was Du da genau in der Tabelle zeigst!? Jeweils `n` Operationen? Oder eine Operation bei der die Datenstruktur schon `n` Elemente enthält? Etwas völlig anderes!?

Und Erklärungen zu einigen Operationen wären nicht schlecht. Vielleicht versteht man umgangssprachlich ja etwas anderes unter den Namen als Du damit jetzt gerade meinst. Zum Beispiel haben weder `dict` noch `tuple` eine `append()`-Methode, für was sind denn da die Angaben in der Tabelle!?

Zugriff in Dictionaries über Schlüssel ist (beim Hinzufügen amortisiert) O(1), da eine Hashtabelle als Implementierung zu Grunde liegt. Test auf "enthalten sein" (``in``-Operator) ist auch O(1).

Zugriff auf Listen und Tupel über Index ist O(1). Suchen/Test auf "enthalten sein" eines Elements ist O(n). `append()` auf Listen ist entweder O(1) oder O(n) mit `n` der Anzahl der Elemente in der Liste. Bei vielen `append()`-Operationen ist die Zeit amortisiert O(1) pro Operation, wegen der "Über-Allokation" wenn der Platz im alten Array nicht mehr ausreicht.
Benutzeravatar
Goswin
User
Beiträge: 361
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen

Donnerstag 24. Januar 2008, 14:31

@ Blackjack:
Mit n meine ich eine Datenstruktur, die bereits n Elemente enthält. Aufgrund deiner Bemerkung sehe ich nun, daß man auch den asymptotischen Aufwand bezüglich der Anzahl m von ausgeführten Operationen betrachten kann, was sicher interessant ist.

Um alle Operationen, auch die nicht eingebauten, miteinander vergleichen zu können, setze ich folgendes voraus:
  • (1) Meine "Keys" sollen implizit geordnet werden können, so dass es also auch in einem Dictionary sinnvoll ist, Keys miteinander zu vergleichen. Unter place verstehe ich die Ordnungszahl der implizit oder tatsächlich geordneten Keys.
    (2) Bei Lists und Tuples sollen die "Keys" nicht nur implizit sondern auch tatsächlich nach Speicherplatz geordnet sein. In diesen Fällen erhalten sie einen Zahlenwert und werden dann üblicherweise nicht mehr Keys, sondern Indices genannt.
Bei jedem Softwarebau muss ich ja von den Operationen ausgehen, die ich mit meinen vorhandenen Daten machen möchte. Erst danach entscheide ich mich für eine Python-Datenstruktur, und wenn diese Struktur eine der Operationen nicht eingebaut hat, muss ich sie halt hinzuprogrammieren.
Benutzeravatar
Goswin
User
Beiträge: 361
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen

Donnerstag 24. Januar 2008, 14:56

Zusatz:

Einige der Zeitaufwände, die ich als O(log n) beschreibe könnte man auch als O(1) beschreiben, je nachdem, wie "locker" oder "puristisch" man eingestellt ist (das heißt, je nachdem, ob man als Indices nur Integers oder auch Arbitrary_Long_Integers nehmen darf).

Absolut erstaunlich für mich ist, dass ein Zugriff auf eine Python-list, die ich mir als Verlinkung von Objekten vorstelle, laut Blackjack einen Aufwand von nur O(log n) oder weniger haben soll. Ich kann auf die Schnelle gar nicht sehen, wie so etwas implementiert wird.
BlackJack

Donnerstag 24. Januar 2008, 14:59

Auf den Schlüsseln muss aber keine Ordnung bestehen um sie in Dictionaries zu verwenden. Als Folge von der Implementierung als Hash-Tabelle sind Dictionaries ungeordnet, ein Zugriff auf das `place`\te Element macht keinen Sinn.

Mit Deiner Tabelle kann ich immer noch nichts anfangen. Da kommt nicht einmal O(1) vor, was bedeuten würde in Python gibt's gar keine effizienten Datenstrukturen, und recht häufig O(log n) was auf Baumstrukturen schliessen lässt, die es bei den Standardtypen nicht gibt, und die insbesondere bei Tupeln ziemlich unsinnig wären.

Du solltest Dich mit Leereinträgen in so einer Tabelle anfreunden. Auch das nicht-vorhanden-sein einer Operation ist ein Auswahlkriterium für oder gegen eine Datenstruktur.
Zuletzt geändert von BlackJack am Donnerstag 24. Januar 2008, 15:09, insgesamt 1-mal geändert.
BlackJack

Donnerstag 24. Januar 2008, 15:08

Zum Zusatz: Listen sind als Arrays + "Füllstand" implementiert. Immer wenn bei `append()` nicht mehr genügend Platz ist, wird ein grösseres Array angefordert, wobei die Grösse relativ von der Grösse des alten Arrays abhängt. Deshalb ist `append()` oft O(1), manchmal aber auch O(n). Durch diese "Über-Allokation" hat man bei unendlich vielen `append()`\s eine mittlere Laufzeit von O(1) pro Operation. Das Zugriffe per Index O(1) Zeit kosten, sollte bei Arrays einleuchten. Und ja: man kann nur Zahlen im `int`-Bereich als Index verwenden. Da das schon den Adressraum eines Prozesses sprengt, macht mehr auch keinen Sinn.

In Java heisst so etwas `java.util.ArrayList`.
Benutzeravatar
Goswin
User
Beiträge: 361
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen

Donnerstag 24. Januar 2008, 15:42

@Blackjack: Vielen Dank für deine Information über die Implementation von Listen :D. Ich halte es für sehr wichtig, so etwas bei der Programmierung in Betracht zu ziehen, habe es aber in meinem Pythonbüchern bisher nicht gefunden.
Antworten