Listenwerte mit anderen Listenwerten abgleichen

[sfgheady]

Hey Zusammen,
ich bin neu hier und auch zugleich neu mit Python.
Ich übersetze momentan ein in R geschriebenes Script in Python und habe nicht wirklich eine Idee, wie ich schnell und Elegant folgendes Problem löse:

Ich habe eine Liste mit 2 Millionen 5-stelligen Tupeln. Ich möchte einen Int Wert aus diesem Tupel mit 5 anderen Listen abgleichen. Jeder Wert aus den 5 anderen Listen ist eindeutig und jenachdem in welcher Liste der Int-Wert aus dem Tupel liegt, möchte ich ein weiteres Element an das 5-stellige Tupel hinzufügen.
Im Prinzip mache ich aus einer Liste mit 5-stelligen Tupeln eine Liste mit 6-stelligen Tupeln.

Z.b.

X ist ein beliebiges 5-stelliges Tupel (dieser Form (1 , 2 , 3 , 4 , 5) aus meiner Liste.
Ich nehme mir den Wert an Stelle X[2]=3.
X[2] will ich jetzt in den anderen 5 Listen durchsuchen. Die anderen 5 Listen haben unterschiedliche Längen, aber sind alle vom selben Typ.
Ich finde z.b. den Wert X[2] in der 4. Liste, somit füge ich dem Tupel X ein neues Element hinzu:

X = (1 , 2 , 3 , 4 , 5 , 'Gefunden in der 4. Liste')

Meine Frage bezieht sich eher auf das Iterieren, da ich ungerne eine Laufzeit von O(5n) für jedes Tupel in kauf nehmen möchte.

Das ganze soll jetzt 2 Millionen mal passieren, daher wollte ich euch fragen, wie man das ganze Elegant und von der Laufzeit so gut es geht umsetzen kann.

wäre euch sehr dankbar

[Hyperion]

Also erst einmal: Tupel sind unveränderlich. Du kannst also einem Tupel kein Element hinzufügen! Evtl. willst Du also eher Listen statt Tupel verwenden? Ansonsten musst Du die Tupel neu aufbauen.

Wenn die Werte in den fünf Listen eindeutig sind, so kannst Du stattdessen daraus ``sets`` machen. Das Überprüfen, ob ein Wert in diesen ist, verringert sich dann von O(n) auf O(1) - nicht schlecht, oder?

Damit bleibt dann nur noch der einmalige Durchlauf durch die Ausgangsmenge mit O(n).

Edit: Für die Lesbarkeit könnte für Dich noch ``operator.itemgetter`` sein - je nach Bedeutung der Indizes in Deinen Tupeln kann das der leserlicher sein, einen gut benannten Zugriffsmechanismus zu haben statt ``x[2]``

[BlackJack]

@sfgheady: Du könntest Dir eine Abbildung von allen Elementen in den 5 Listen auf die Nummer(n) der Liste(n) erstellen und so schnell bestimmen aus welche(r|n) Liste(n) ein Element kommt. Ungetestet:

Code: Alles auswählen

    item2list_numbers = defaultdict(list)
    for i, a_list in enumerate(five_lists):
        for item in a_list:
            item2list_numbers[item].append(i)

    for x in two_million_tuples:
        item = x[2]
        print 'Item {0} gefunden in Liste(n) {1}'.format(
            item, item2list_numbers[item]
        )

Mit `collections.defaultdict`.

Und offensichtlich habe ich das Problem anders verstanden als Hyperion, denn ich sehe nicht wo man `set()` benutzen könnte.

[Hyperion]

@BlackJack: Ich dachte an Mengen aufgrund dieser Aussage:

Ich habe eine Liste mit 2 Millionen 5-stelligen Tupeln. Ich möchte einen Int Wert aus diesem Tupel mit 5 anderen Listen abgleichen. Jeder Wert aus den 5 anderen Listen ist eindeutig und jenachdem in welcher Liste der Int-Wert aus dem Tupel liegt, möchte ich ein weiteres Element an das 5-stellige Tupel hinzufügen.

[Sirius3]

Wenn die Zahlen in einem eingeschränkten Bereich liegen, z.B. 0..n, kann man das mit numpy in schnell und kurz schreiben:

Code: Alles auswählen

import numpy
two_million_values = numpy.asarray(two_million_values, dtype=int)
max_n = max(max(l) for l in five_lists)
value2listnumber = numpy.zeros(max_n+1, dtype=int)
for idx, l in enumerate(five_lists):
    value2listnumber[l] = idx

list_numbers = value2listnumber[two_million_values[:,2]]
two_million_values_extended = numpy.hstack([two_million_values, list_numbers])

[MagBen]

Ich habe eine Liste mit 2 Millionen 5-stelligen Tupeln.

Bei dieser Datenmenge würde ich Dir zu einer Datenbank raten. Wenn die zu durchsuchenden Listen vorher sortiert werden können, dann geht das ganze auch sehr performant mit Numpy http://docs.scipy.org/doc/numpy/referen ... .sort.html

Ich finde z.b. den Wert X[2] in der 4. Liste, somit füge ich dem Tupel X ein neues Element hinzu:
X = (1 , 2 , 3 , 4 , 5 , 'Gefunden in der 4. Liste')

Würde ich so nicht machen. Verändere nicht die Liste mit den 5-stelligen Tupeln, sondern packe Deine Suchergebnisse in eine neue dynamisch anwachsende Liste. So hast Du 6 große Listen/Tabellen/Arrays die unveränderlich sind (und damit einfacher durchsucht werden können) und nur eine dynamische Liste mit den Ergebnissen.

[MagBen]

Das Überprüfen, ob ein Wert in diesen ist, verringert sich dann von O(n) auf O(1) - nicht schlecht, oder?

Das wäre nicht nur "nicht schlecht", sondern phänomenal. Beliebig große Datenmengen ließen sich in konstanter Zeit durchsuchen lassen. Stand der Technik ist aber wohl eher O(log(n))

[EyDu]

Das Überprüfen, ob ein Wert in diesen ist, verringert sich dann von O(n) auf O(1) - nicht schlecht, oder?

Das wäre nicht nur "nicht schlecht", sondern phänomenal. Beliebig große Datenmengen ließen sich in konstanter Zeit durchsuchen lassen. Stand der Technik ist aber wohl eher O(log(n))

Die in-Operation auf Mengen ist unter Python so umgesetzt, dass sie im Schnitt mit O(1) läuft. Im Worst-Case kann das ganze auf O(n) zusammenbrechen. Siehe hier.

[Hyperion]

Stand der Technik ist aber wohl eher O(log(n))

Äh ... nö! Es kommt auf die Implementierung an. Sets und Dictionaries (und verwandte Collections) setzen in Python auf Hashing. Damit ist das Finden eines Schlüssels in *konstanter* Zeit möglich, unabhängig von der Größe der Datenmenge. Hier aber noch mal als pures Faktum

Und man kann ja auch ein wenig experimentieren, hier mal mit iypthon:

Code: Alles auswählen

In [13]: small = {1, 2, 3}

In [14]: %timeit 3 in small
10000000 loops, best of 3: 76 ns per loop

In [15]: big = set(range(10000000))

In [16]: %timeit 9999999 in big
10000000 loops, best of 3: 111 ns per loop

In [17]: big_list = list(range(10000000))

In [18]: %timeit 9999999 in big_list
1 loops, best of 3: 311 ms per loop

Wie man sieht, liegen zwischen dem Set mit 3 und dem mit 10 Mio Elementen nur wenige Nanosekunden Unterschied; aufgrund des Faktors 3Mio bezüglich des Größenunterschieds wage ich zu bezweifeln, dass man den Anstieg noch logarithmisch erklären könnte Im Gegensatz dazu kostet das stumpfe lineare Suchen natürlich deutlich mehr. Man könnte über ``bisect`` jetzt natürlich mal schauen, was das binäre Suchen so brächte...

[BlackJack]

@Hyperion: Die Aussage die Dich an Mengen hat denken lassen, bedeutet soweit ich das verstanden habe eher dass mein `defaultdict` überflüssig ist, weil die Schnittmenge der 5 Listen leer ist, also ein Element eindeutig einer der 5 Listen zugeordnet werden kann und nicht in Mehreren vorkommen kann. Mein Quelltext wird dann zu:

Code: Alles auswählen

    item2list_number = dict()
    for i, a_list in enumerate(five_lists):
        for item in a_list:
            assert item not in item2list_number
            item2list_number[item] = i

    for x in two_million_tuples:
        item = x[2]
        print 'Item {0} gefunden in Liste {1}.'.format(
            item, item2list_number[item]
        )

[Hyperion]

@BlackJack: Aber bedeutet das nicht, dass man aus den fünf Listen einfach Mengen machen kann? Wenn es nur um das Vorhandensein geht, spielen ja Duplikate und Reihenfolge keine Rolle...

[Sirius3]

@Hyperion: es gibt ja um die Zuordnung, in welcher der 5 Listen der Wert ist.

[BlackJack]

@Hyperion: Könnte man machen. Ist also die Frage welcher Ansatz schneller ist. Ich tippe auf meinen, denn linear 5 Mengen zu testen in welcher das Element ist, dauert länger als in einem Wörterbuch diese Information *sofort* nachzuschlagen. Und das dann 2 Millionen mal. Das würde nur kippen wenn das erstellen des Wörterbuchs den Vorteil wieder auffrisst.

[Hyperion]

@BlackJack: Da hast Du vermutlich recht. Da das ganze ein wenig arg künstlich konstruiert daher kommt, würde mich mal der tatsächliche Kontext interessieren. Also woher kommen diese Daten? Werden dieses evtl. schon suboptimal aufgebaut? Evtl. lösen wir hier ein XY-Problem - gleichwohl das auch interessant war

[sfgheady]

Hallo Zusammen!
dankesehr für eure sehr sehr sehr hilfreichen Antworten.

Woher die Daten kommen und wie diese berechnet werden, kann ich leider nicht sagen (Ich hoffe Ihr habt Verständnis diesbezüglich).
Das einzige was ich drehen kann ist die Art und Weise, wie ich die Daten, in meinem Fall die 2 Millionen 5er - Tupel, ablege. Das 5er Tupel ist nun eine Liste

Bei der Zusammensetzung der Liste hole ich mir für jedes Element aus dem Tupel die Daten aus verschiedenen Quellen, das habe ich aber soweit gut zusammen bekommen. Es dauert ca 1 Minute um diese Liste zu erstellen, da die Daten noch auf verschiedene Arten gefiltert werden.

Meine Überlegung war, diese Liste mit Tupeln zu füllen, welche bei der Ausführung des Skripts dann mit weiteren Elementen gefüllt wird, sodass das Tupel zum Schluss 15 Elemente beinhaltet, dabei ist die Frage, wie Python mit so großen Datenmengen umgehen kann und ob es sinnvoll ist diese in einer Liste abzulegen oder ob es Sinn macht die Liste aufzuteilen.

Das Suchen nach dem richtigen Element in einer der weiteren Listen ist nur eines von vielen Problemen. Nachdem das weitere Element in das Tupel bzw. dann Liste aus 6 Elementen hinzugefügt wurde, wird eine Berechnung auf all diesen Tupeln gestartet und fügen dann, wie oben schon beschrieben, weitere Elemente in das Tupel ein.

Im Verlauf des Programms verändert sich nur die Anzahl Elemente der Tupel, nicht die Anzahl der Tupel.
Die Tupel sind nicht abhängig von einander, daher könnte man Libraries in betracht ziehen für eine parallele Verarbeitung.

Ich hoffe Ihr kommt nicht mit dem Listen durcheinander Falls etwas unklar ist, erläutere ich es gerne nochmal. Code kann ich leider nicht posten, aber ich bin schon als dabei eure Ideen zu implementieren.
Ich kenne die Möglichkeiten von Python noch nicht wirklich und würde es gerne mit euch zusammen so umsetzen, dass ich zufrieden bin mit der Laufzeit.
In R benötige ich knapp 5 Minuten, um korrekte Ergebnisse zu erhalten und verwenden zu können.