Vergleich mehrerer redundanter Listen

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.
Antworten
Tobsen345
User
Beiträge: 2
Registriert: Dienstag 19. Oktober 2010, 15:05

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.
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Hallo und willkommen im Forum!

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

Sebastian
Das Leben ist wie ein Tennisball.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

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.
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

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})
Benutzeravatar
DrFaust
User
Beiträge: 21
Registriert: Freitag 15. Oktober 2010, 23:10

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 :oops: ...

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

Ciao

Nils
Benutzeravatar
cofi
Python-Forum Veteran
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

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 ;)
Benutzeravatar
DrFaust
User
Beiträge: 21
Registriert: Freitag 15. Oktober 2010, 23:10

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

@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.
Benutzeravatar
DrFaust
User
Beiträge: 21
Registriert: Freitag 15. Oktober 2010, 23:10

:? 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...
Benutzeravatar
DrFaust
User
Beiträge: 21
Registriert: Freitag 15. Oktober 2010, 23:10

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...
Benutzeravatar
cofi
Python-Forum Veteran
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

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.
BlackJack

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)
Benutzeravatar
cofi
Python-Forum Veteran
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

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
BlackJack

@cofi: IMHO keine Geschmackssache weil ein Wert unnötig gesetzt wird, der sofort mit einem anderen Wert überschrieben wird.
Tobsen345
User
Beiträge: 2
Registriert: Dienstag 19. Oktober 2010, 15:05

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
Antworten