Das deutsche Python-Forum

Hallo liebes Pythonforum,

ich versuche derzeit ein kleines Programm zu entwickeln, mit dem ich mehrere Listen miteinander vergleichen kann. Ich habe 6 Listen die Strings enthalten (Aminosäuresequenzen). Diese Listen sind zum Teil redundant. Ich möchte nun herausfinden, wieviele Aminosäuresequenzen nur in einer Liste enthalten(also nicht redundant) sind bzw. wieviele nur in 2, 3, 4, 5 oder in allen Listen redundant sind.
Meine bisherigen Versuche habe ich mit sets und intersection durchgeführt:

Beispiel:

Code: Alles auswählen

liste1 = ['AAA', 'KKK', 'LKL', 'KLA']
liste2 = ['LPN', 'AAA', 'KLA, 'NNN']
set1 = set(liste1)
set2 = set(liste2)

set3=set1.intersection(set2)
print len(set3)

Für den Vergleich von 2 Listen erscheint mir meine Herangehensweise geeignet. Für den Vergleich von 6 Listen ist sie allerdings nicht geeignet. Vielleicht habt ihr eine Idee, wie man mein Problem lösen kann.

Hallo und willkommen im Forum!

Der "Trick" sind eigentlich Schleifen, Rekursion und vielleicht noch das itertools-Modul.

Sebastian

Tobsen345 hat geschrieben: Für den Vergleich von 2 Listen erscheint mir meine Herangehensweise geeignet. Für den Vergleich von 6 Listen ist sie allerdings nicht geeignet.

Wieso? Du kannst doch beliebig viele Sets schneiden (wobei Du eher difference() suchst?) ...

Code: Alles auswählen

In [24]: seqs = []

In [26]: seqs.append(set(("KKK", "AAA")))

In [27]: seqs.append(set(("AAA",)))

In [28]: seqs.append(set(("AAA", "LKL")))

In [29]: seqs
Out[29]: [set(['AAA', 'KKK']), set(['AAA']), set(['AAA', 'LKL'])]

In [33]: seqs[0].difference(*seqs[1:])
Out[33]: set(['KKK'])

Ansonsten hat EyDu natürlich weitere Hinweise gegeben.

Hyperion hat geschrieben:
Tobsen345 hat geschrieben: Für den Vergleich von 2 Listen erscheint mir meine Herangehensweise geeignet. Für den Vergleich von 6 Listen ist sie allerdings nicht geeignet.
Wieso? Du kannst doch beliebig viele Sets schneiden (wobei Du eher difference() suchst?) ...
Code: Alles auswählen
In [24]: seqs = []

In [26]: seqs.append(set(("KKK", "AAA")))

In [27]: seqs.append(set(("AAA",)))

In [28]: seqs.append(set(("AAA", "LKL")))

In [29]: seqs
Out[29]: [set(['AAA', 'KKK']), set(['AAA']), set(['AAA', 'LKL'])]

In [33]: seqs[0].difference(*seqs[1:])
Out[33]: set(['KKK'])

Naja, wenn er von den Elementen von 6 Listen wissen will, in wie vielen Listen die jeweils drin sind, müsste er bei dieser Vorgehensweise z.B. auch vier Listen schneiden, und schauen welches dieser Elemente in keiner der anderen zwei Listen sind. Und das für jede mögliche Auswahl von 4 Listen. Ist das nicht ein bisschen kompliziert? (Und Laufzeit O(n!) oder schlimmer...)

Ich empfehle den Einzeiler

Code: Alles auswählen

>>> sequence_lists = [set(['AAA', 'KKK']), set(['AAA']), set(['AAA', 'LKL'])]
>>> collections.Counter(itertools.chain(*sequence_lists))
Counter({'AAA': 3, 'LKL': 1, 'KKK': 1})

Ich wäre da jetzt vielleicht noch dümmer dran gegangen: Warum nicht aus den sechs verschiedenen Listen eine große machen. Falls Dopplungen in einer Liste vorkommen können und diese nicht mitgezählt werden sollen vorher ein set draus machen. Etwa:

Code: Alles auswählen

from functools import partial

#Function to compar strings
def filter_func(x,y):
    return True if x == y else False

complete_list = list1 + list2 + list3 + list4+ list5 + list6 # hier ggf vorher mit set drüber prügeln
result = {}
for my_string in set(complete_list):
    result[my_string] = len(filter(partial(filter_func,my_string),complete_list))

Ich hoffe, ich verwende die partial hier richtig. Habe das auch gerade erst kennen gelernt

...

Die vorherige Lösung ist sicher eleganter. Aber ich stecke leider nicht ganz so tief in den collections-methoden drin.

Ciao

Nils

Code: Alles auswählen

def filter_func(x,y):
    return True if x == y else False

laesst sich als

Code: Alles auswählen

def filter_func(x,y):
    return x == y

schreiben oder man verwendet gleich `operator.eq`

Der Kommentar ist btw irrefuehrend, weil `filter_func` generisch ist.

Die Verwendung von `partial` passt aber

Opps, keine Ahnung was du mit 'generisch' meinst, aber dass ich die Funktion unnötig kompliziert geschrieben habe ist völlig richtig.

@DrFaust: Generisch heisst, dass die Funktion nicht nur mit Zeichenketten funktioniert, sondern generell mit allen Objekten die vergleichbar sind.

Der Algorithmus selbst ist allerdings nicht so toll, da er quadratische Laufzeit hat. Wenn man den Inhalt von `collections` nicht kennt, oder nicht komplett verfügbar hat, kann man das trotzdem effizienter programmieren, so dass man nur einmal linear durch alle Elemente durchgehen muss.

Kommt man denn nennenswert unter O(n²)? Wenn fünf der sechs Listen jetzt nicht gerade nur ein oder zwei Elemente enthalten (und die sechste riesig lang ist), sondern alle Listen zumindest ungefähr (gerne auch um ganzzahlige konstante Faktoren) gleich lang sind, muss ich für jeden String einmal alle fünf anderen Listen, d.h. ~5/6 der Elemente durchgehen. Ich komme noch etwas runter, wenn ich schon bearbeiteten Elemente entferne. Aber das ändert an der worst case Laufzeit gar nix, nur der average case wird etwas besser. Ich sehe einfach nicht, wie man viel weiter runter kommen soll...

Ja natürlich, ich könnte eine Adaption von Bucketsort versuchen al'a

Code: Alles auswählen

for item in complete_list:
    if item in result:
        result[item] +=1
    else:
        result[item]=1

Laufzeit O(n).Manchmal denke ich wirklich unnötig kompliziert...

Ich denke darauf wollte Blackjack raus: `collections.defaultdict`

Code: Alles auswählen

import collections
dist = collections.defaultdict(int)
for s in seqs:
    dist[s] += 1

oder alternativ:

Code: Alles auswählen

dist = dict()
for s in seqs:
    dist.setdefault(s, 1)
    dist[s] += 1

Edit: Fix.

Die Alternative hätte ich eher mit `get()` geschrieben:

Code: Alles auswählen

dist = dict()
for s in seqs:
    dist[s] = dist.get(s, 0) + 1

`setdefault()` ist IMHO praktischer bei veränderbaren Defaultwerten, weil der Wert nicht nur eingetragen sondern auch zurückgegeben wird, bzw. der eingetragene Wert, falls es schon einen gibt. Mal ein konstruiertes Beispiel: Man möchte eine Abbildung von Vornamen auf Listen von Personen mit dem jeweiligen Vornamen erstellen (ohne `collections.defaultdict` zu benutzen):

Code: Alles auswählen

name2persons = dict()
for person in persons:
    name2persons.setdefault(person.name, []).append(person)

BlackJack hat geschrieben:`setdefault()` ist IMHO praktischer bei veränderbaren Defaultwerten, weil der Wert nicht nur eingetragen sondern auch zurückgegeben wird, bzw. der eingetragene Wert, falls es schon einen gibt.

Wobei man den dann auch hier nutzen kann, aber das ist natuerlich Geschmackssache.

Code: Alles auswählen

dist = dict()
for s in seqs:
    dist[s] = dist.setdefault(s, 1) + 1

@cofi: IMHO keine Geschmackssache weil ein Wert unnötig gesetzt wird, der sofort mit einem anderen Wert überschrieben wird.

Vielen Dank für die zahlreiche Hilfe!
Auch wenn ich kaum etwas von dem verstehe, was ihr da schreibt, hat mir der Einzeiler von bords0 sehr weitergeholfen. Falls ich es schaffe ein funktionierendes Skript fertigzustellen, lasse ich es euch wissen. Zum Thema Laufzeit: Die Listen umfassen jeweils >10000 Elemente. Ob das ein Problem darstellt wird sich zeigen.

Viele Grüße, Tobsen

Das deutsche Python-Forum

Vergleich mehrerer redundanter Listen

Vergleich mehrerer redundanter Listen

Re: Vergleich mehrerer redundanter Listen

Re: Vergleich mehrerer redundanter Listen

Re: Vergleich mehrerer redundanter Listen

Re: Vergleich mehrerer redundanter Listen

Re: Vergleich mehrerer redundanter Listen

Re: Vergleich mehrerer redundanter Listen

Re: Vergleich mehrerer redundanter Listen

Re: Vergleich mehrerer redundanter Listen

Re: Vergleich mehrerer redundanter Listen

Re: Vergleich mehrerer redundanter Listen

Re: Vergleich mehrerer redundanter Listen

Re: Vergleich mehrerer redundanter Listen

Re: Vergleich mehrerer redundanter Listen

Re: Vergleich mehrerer redundanter Listen