Liste aufräumen

[chwin]

Hallo

ich komme irgendwie nicht weiter.
Ich habe eine riesige Liste mit Strings.
Diese Liste kann gerne mal 500k Einträge haben

Code: Alles auswählen

["abc_random", "pqr_random", "abcdfr_random", "abcdfg_random", "pqrjhg_random", "defgh_random", "zkl_random", "abcdefghi_random"]

Die Strings können als hierarchisch betrachtet werden.
Für die Auswahl ist nur der Teil vor dem Unterstrich nötig. Es sind keine wirklichen Zufallsdaten haben aber für die Auswahl keine Bedeutung
Diese "random" Werte benötige ich erst im zweiten Schritt. Im ersten Auswahlschritt gehts nur um den vorderen Teil.


Am Ende soll eine Liste dabei rauskomen die aussieht wie:

Code: Alles auswählen

["abc_random", "pqr_random", "defgh_random", "zkl_random"]

Das soll heissen, dass "abcdfr" nicht benötigt wird, weil "abc" diesen sozusagen mit abdeckt.

Wie kann ich das machen? Gibt es dazu evtl schon ein modul?
Hat sowas einen Namen?

RAM und CPU sollten nicht das Problem sein.

Achja, die Strings bestehen nur aus [a-z0-9]


Hat hier einer eine Idee wie man das angeht?


Gruß und vielen Dank
Christian

[Sirius3]

@chwin: was hast Du Dir schon für Gedanken gemacht? Wie würdest Du das Problem von Hand lösen?

[BlackJack]

@chwin: Ist die Reihenfolge der Beispieldaten realistisch? Also kommen kürzere Präfixe grundsätzlich vor ihren längeren Varianten in der Liste vor?

[chwin]

@Sirius3
Ja, ich habe mir Gedanken gemacht. Meine erste Idee war zwei verschachtelte Schleifen zu bauen
In der äußeren Schleife das erste Element (vorderen Teil bis zum Unterstrich) zu nehmen und dann in der inneren mit allen Elementen mit str.startswith vergleichen.
Dabei würde ich dann halt alle die Matchen wegwerfen.

Das kommt mir aber sehr ineffektiv vor, besonders wegen der Größe der Liste.

Ich bin kein richtiger Programmierer, sondern eher sowas wie ein Admin. Ich kann Programmieren um mir das Leben zu vereinfachen. Wirklich effiktive algorhithmen entwickeln habe ich nie richtig gelernt.

@BlackJack
Nein Die Reihenfolge kann beliebig sein.
Wie gesagt, die Listen haben typischerweise so 300k bis 500k Elemente.

[BlackJack]

@chwin: Wie sieht es mit der Ergebnisreihenfolge aus? Spielt die eine Rolle? Denn ansonsten könnte man die Ursprungsliste einfach erst einmal alphabetisch sortieren, damit die Varianten mit dem kürzesten Präfix als erstes kommen und die passenden auszusortierenden direkt folgen. Da sollte es dann nicht mehr schwer sein einen einfachen Algorithmus zu schreiben der das dann macht.

[chwin]

Die Reihenfolge der Ergebnisliste ist vollkommen egal.
An Sortieren hatte ich auch schon gedacht.
Aber die Elemente bestehen ja aus zwei Teilen.

Die "hierarchische" erste Hälfte und die Zufällige zweite Hälfte.
Die zweite Hälfe ist immer 128 Zeichen lang.

Das Sortieren dürfte aber nur die erste Hälfte berücksichtigen.

[BlackJack]

@chwin: Das ist doch völlig egal wie der Teil nach dem '_' aussieht. Der hat doch erst dann Gewicht beim sortieren wenn der vordere Teil gleich ist. Und ob dann ein zufälliges beziehungsweise von der Ausgangsreihenfolge abhängiges Ergebnis bei so einem Vergleich heraus kommt, oder ob der hintere Teil dann auch herangezogen wird, macht doch keinen Unterschied wenn die Ergebnisreihenfolge egal ist. Sofern überhaupt gleiche vordere Teile vorkommen können. Falls das nicht passieren kann, ist das komplett egal was hinten steht, denn dann entscheidet ja immer der vodere Teil schon über die Reihenfolge.

Edit: Da es für die weitere Verarbeitung ja sowieso getrennt werden muss, kann man aber natürlich in einem ersten Schritt auch erst einmal die Daten in die beiden Bestandteile aufteilen.

[Sirius3]

@chwin: da hast Du Glück, weil "_" < "a" ist, und somit der kürzeste Prefix als erstes einsortiert wird. Wenn man Deinen Algorithmus dann umsetzt, kommt ungefähr das raus:

Code: Alles auswählen

def filter_prefix(iterable):
    latest = '?'
    for value in sorted(iterable):
        if not value.startswith(latest):
            yield value
            latest = value.split('_', 1)[0]

values = ["abc_random", "pqr_random", "abcdfr_random", "abcdfg_random", "pqrjhg_random", "defgh_random", "zkl_random", "abcdefghi_random"]
result = list(filter_prefix(values))

[Sirius3]

oder natürlich mit Hilfe eines Baums, ohne sortieren:

Code: Alles auswählen

def insert(tree, key, value):
    leaf = tree
    for v in key:
        if v in leaf:
            leaf = leaf[v]
        else:
            if None in leaf:
                # shorter prefix exists
                return
            leaf[v] = leaf = {}
    leaf.clear()
    leaf[None] = value

def collect(tree):
    result = []
    stack = [tree]
    while stack:
        leaf = stack.pop()
        if None in leaf:
            result.append(leaf[None])
        else:
            stack.extend(leaf.values())
    return result

values = ["abc_random", "pqr_random", "abcdfr_random", "abcdfg_random", "pqrjhg_random", "defgh_random", "zkl_random", "abcdefghi_random"]
tree = {}
for v in values:
    insert(tree, v.split('_')[0], v)
result = collect(tree)

[chwin]

Danke BlackJack, danke Sirius3

Die Lösung von BlackJack kann ich noch nachvollziehen mit meinem Verständnis.
Bei Deiner Lösung Sirius3 steige ich leider Gedanklich aus.

Ich werde die kommenden Tage mal versuchen den Baumansatz zu verstehen.
Auf jeden Fall werde beide mal ausprobieren.

Gibt es irgendwelche offensichtlich Vor- oder Nachteile bei bei den beiden Lösungen?

[kbr]

@chwin: Vor- und Nachteile wären Speicherverbrauch und Laufzeitverhalten. Hier wird sich die Baumlösung umso günstiger verhalten, je besser die Daten mit kurzen Prefixen zuerst vorsortiert sind. Wenn Du diese vorsortierst, hast Du allerdings schon einen Teil der Arbeit des funktionalen Ansatzes geleistet. Testen mit einem Profiler kann hier weiter helfen.
Für mich gibt es zudem noch ein drittes Kriterium (gerne an erster Stelle, solange die beiden anderen nicht dagegen sprechen): die Eleganz der Implementierung. Hier wäre der funktionale Ansatz mein Favorit.

[chwin]

Hallo

ich wollte mich nur nochmal zurückmelden.
Ich habe mich für die Variante vom Sirius3 entschieden.
Ganz einfach weil ich diese verstehe und nachvollziehen kann.

Das Laufzeitverhalten war bei beiden ähnlich. Es kommt aber auf die Ausgangsdaten an.
Beide Lösungen waren mal schneller mal langsamer. Da ich aber auf die Ausgangsdaten keinen Einfluss habe ist es auch egal.


noch mal vielen Dank

gruss
Christian