Wie sind Pythons Such- und Sortieralgorithmen implementiert?

[Dingels]

Schönen guten Abend,

für eine Hausaufgabe muss ich eine Reihe von Such- und Sortieralgorithmen verwenden. Zu diesem Zweck würde ich gern wissen, wie die schon in der Standardbibliothek vorhandenen Algorithmen implementiert sind? Welche Algorithmen nutzen z.B. Sequenzoperationen wie sort(), sorted(), index(), count() etc.? Wisst ihr das oder kann man das irgendwo nachlesen? Denn es macht wenig Sinn, einen Algorithmus neu zu implementieren, wenn er tatsächlich schon längst vorhanden ist.

Könnt ihr mir da helfen? Herzlichen Dank im Voraus.

[Hyperion]

In der Doku zu `sorted` finde ich den Link hierzu: http://wiki.python.org/moin/HowTo/Sorting/

Und dort wiederum wird auf Timesort verwiesen. Allerdings weiß ich nicht, ob das exklusiv ist oder gar veraltet.

Ich würde mir da durchaus mal den Quellcode von CPython angucken, um zu schauen, ob da im Code Hinweise zum Algorithmus gegeben werden.

[Dingels]

Danke für den Link, Hyperion. Das hilft mir schon mal weiter. Laut Wikipedia ist der Timsort-Algorithmus seit Version 2.3 Standard. Ich hab mir gerade mal den Source Code für Version 2.7 heruntergeladen, aber ich hab keine Ahnung, wo ich da jetzt anfangen soll zu suchen. :K Zumal ich auch nicht so geübt darin bin, C-Code zu lesen. Aber vielleicht weiß ja noch jemand anders Rat.

[cofi]

Der Sorieralgorithmus ist mit Timsort ein adaptiver Mergesort, er hat auch Einzug in OpenJDK gefunden.
`count`, `index` können nur lineare Suche anwenden, weil ueber die Daten keine Informationen verfuegbar sind, z.B. dass sie sortiert waeren.

[Dingels]

Danke, cofi, interessant. Was ist außerdem mit re.findall() ?

Oder, anders gefragt: Bieten sich also genug Möglichkeiten, bessere Suchalgorithmen in Python zu implementieren, die dann hoffentlich bei großen Textmengen auch performanter sind als die aus der Standardbibliothek? In meinem speziellen Fall geht es vor allem um Suffix Arrays.

[DasIch]

Besser ist relativ, für übliche Use Cases wirst du keinen besseren Algorithmus finden es mag aber bestimmte Fälle geben in denen andere Algorithmen besser sind.

Allerdings ist es absolut sinnlos sich damit zu befassen es sei den du hast Mesergebnisse die ein Problem aufzeigen.

[cofi]

Ich hatte jetzt Listen im Hinterkopf, was Strings/Texte angeht muss man ein paar Sachen unterscheiden, z.B. RE und "normale" Strings.
Was RE angeht, wird die Sache u.U. sehr komplex - je nach RE - da kenn ich mich leider zu wenig aus, aber man koennte sich mal bei Gnu grep umschaun.
Was Strings angeht gibt es Knuth-Morris-Pratt[1] und Boyer-Moore[2]

Aber DasIch hat schon recht, dass man v.a. messen muss. Interessanter wirds sogar eventuell dort, wo man Informationen ueber die Daten hat und dann Annahmen im Code machen kann. Das faellt fuer die Standardlibrary ziemlich komplett flach.

Mit suffix arrays hab ich noch nicht gearbeitet, aber ich kann mir gut vorstellen, dass man es effizienter implementieren kann aber, siehe oben, keine Relevanz fuer die Standardlibrary hat.

[1] http://en.wikipedia.org/wiki/Knuth-morris-pratt
[2] http://en.wikipedia.org/wiki/Boyer-Moore

[Dingels]

Verstehe. Es geht nämlich um Folgendes: Ich studiere Computerlinguistik und in einer Vorlesung geht es derzeit um Suchalgorithmen für Strings, allen voran Suffix Trees und Suffix Arrays. Anstelle einer Klausur sollen wir uns ein Softwareprojekt ausdenken, was mit den Themen der Vorlesung zu tun hat.

Meine Idee ist es jetzt, in einem großen deutschen Textkorpus nach Komposita zu suchen und diese in ihre Bestandteile aufzutrennen (z.B. Donauschifffahrt --> Donau + Schiff + Fahrt). Das ist z.B. für maschinelle Übersetzung wichtig. Ein Ansatz dafür wäre zu untersuchen, ob einzelne Wörter als Bestandteile anderer Wörter im Korpus vorkommen, d.h. ich müsste viel Zeit mit dem Suchen von Substrings verbringen. In dem Projekt könnte ich dann z.B. auch untersuchen, ob diese Vorgehensweise mit Hilfe von Suffix Arrays effizienter gelöst werden kann oder ob es keinen Vorteil gegenüber Pythons eigenen Suchalgorithmen gibt.

Was meint ihr? Ist diese Idee es wert, untersucht zu werden?

[Leonidas]

Ja, warum nicht. Spielereien mit Datenstrukturen sind immer lohnend, selbst wenn es am schluss nicht effizienter ist, hat man immer noch was gelernt. Und darum geht es wohl auch in deriner Aufgabe.