Effiziente Tupel-Listenvergleiche

Question

Ich stoße bei diesem Problem auf eine Mauer und ich frage mich, ob mir ein paar frische Gehirne helfen könnten.

ich eine große Liste von vier Elementen Tupeln im Format haben:

(ID-Nummer, Typ, Start-Index, End Index)

Zuvor im Code, habe ich durch Tausende von Blöcken gesucht Text für zwei bestimmte Arten von Teilstrings. Diese Tupel speichern, in welchem ​​großen Teil des Textes der Teilstring gefunden wurde, welcher der beiden Arten von Teilstrings er ist, und den Start- und Endindex dieses Teilstrings.

Das letzte Ziel besteht darin, diese Liste zu durchsuchen, um alle Instanzen zu finden, in denen ein Teilstring vom Typ 1 vor einem Teilstring vom Typ 2 in einem Textblock mit derselben ID vorkommt. Dann möchte ich diese Objekte im Format speichern (ID, Typ 1, Start, Ende, Typ2, Start, Ende).

Ich habe versucht, mit einer Reihe von Sachen herumzualbern, die sehr ineffizient war. Ich habe die Liste nach ID und dann Start Index sortiert, und wenn ich verschiedene Möglichkeiten versucht habe, die Artikel von der Liste für Vergleiche zu knacken. Ich muss mir vorstellen, dass es eine elegantere Lösung gibt. Irgendwelche brillanten Leute da draußen möchten meinem müden Gehirn helfen ???

Vielen Dank im Voraus

Answer 1

Lösung:

result = [(l1 + l2[1:]) 
      for l1 in list1 
      for l2 in list2 
      if (l1[0] == l2[0] and l1[3] < l2[2]) 
      ] 

... mit Testcode:

list1 = [(1, 'Type1', 20, 30,), 
     (2, 'Type1', 20, 30,), 
     (3, 'Type1', 20, 30,), 
     (4, 'Type1', 20, 30,), 
     (5, 'Type1', 20, 30,), 
     (6, 'Type1', 20, 30,), # does not have Type2 

     (8, 'Type1', 20, 30,), # multiple 
     (8, 'Type1', 25, 35,), # multiple 
     (8, 'Type1', 50, 55,), # multiple 
     ] 

list2 = [(1, 'Type2', 40, 50,), # after 
     (2, 'Type2', 10, 15,), # before 
     (3, 'Type2', 25, 28,), # inside 
     (4, 'Type2', 25, 35,), # inside-after 
     (4, 'Type2', 15, 25,), # inside-before 
     (7, 'Type2', 20, 30,), # does not have Type1 

     (8, 'Type2', 40, 50,), # multiple 
     (8, 'Type2', 60, 70,), # multiple 
     (8, 'Type2', 80, 90,), # multiple 
     ] 

result = [(l1 + l2[1:]) 
      for l1 in list1 
      for l2 in list2 
      if (l1[0] == l2[0] and l1[3] < l2[2]) 
      ] 

print '\n'.join(str(r) for r in result) 

Es ist nicht klar, welches Ergebnis würden Sie gerne, wenn es mehr, dann ist ein Vorkommen von Type1 und Type2 innerhalb derselben Text-ID. Bitte angeben.

Answer 2

Ich weiß nicht, wie viele Arten Sie haben. Aber wenn wir davon ausgehen, dass Sie nur 1 und 2 eingeben, dann klingt das nach einem ähnlichen Problem wie bei der Zusammenführung. Wenn Sie eine Merge-Sortierung durchführen, führen Sie einen einzelnen Durchlauf durch die Liste durch.

Nehmen Sie zwei Indizes, einen für Typ 1 und einen für Typ 2 (I1, I2). Sortieren Sie die Liste nach ID, start1. Starten Sie I1 als erste Instanz von Typ1 und I2 als Null. Wenn I1.id < I2.Id dann I1 erhöhen. Wenn I2.id < I1.id dann I2 erhöhen. Wenn I1.id = I2.id, dann überprüfe iStart.

I1 kann nur auf einem Datensatz vom Typ 1 stoppen und I2 kann nur in einem Datensatz vom Typ 2 stoppen. Erhöhen Sie den Index, bis er auf einem geeigneten Datensatz landet.

Sie können einige Annahmen machen, um dies schneller zu machen. Wenn Sie einen erfolgreichen Block finden, können Sie I1 zum nächsten Block verschieben. Wann immer I2 < I1, können Sie I2 bei I1 + 1 starten (WOOPS VERGEWISSERN SIE, DASS SIE DAS NICHT MACHEN, WEIL SIE DEN FAILURE CASE VERPASSEN WÜRDEN!) Immer wenn Sie einen offensichtlichen Fehlerfall feststellen, bewegen Sie I1 und I2 zum nächsten Block recs natürlich).

Answer 3

Ich habe kürzlich so etwas gemacht. Ich verstehe dein Problem vielleicht nicht, aber hier geht es.

würde ich ein Wörterbuch verwenden:

from collections import defaultdict: 
masterdictType1=defaultDict(dict) 
masterdictType2=defaultdict(dict) 


for item in myList: 
    if item[1]=Type1 
     if item[0] not in masterdictType1: 
      masterdictType1[item[0]]['begin']=item[2] # start index 
      masterdictType1[item[0]]['end']=item[-1] # end index 
    if item[1]=Type2 
     if item[0] not in masterdictType2: 
      masterdictType2[item[0]]['begin']=item[2] # start index 
      masterdictType2[item[0]]['end']=item[-1] # end index 

joinedDict=defaultdict(dict) 

for id in masterdictType1: 
    if id in masterdictType2: 
     if masterdictType1[id]['begin']<masterdictType2[id]['begin']: 
      joinedDict[id]['Type1Begin']=masterdictType1[id]['begin'] 
      joinedDict[id]['Type1End']=masterdictType1[id]['end'] 
      joinedDict[id]['Type2Begin']=masterdictType2[id]['begin'] 
      joinedDict[id]['Type2End']=masterdictType2[id]['end'] 

Dies gibt Ihnen Ausführlichkeit und gibt Ihnen etwas, das dauerhaft ist, da Sie das Wörterbuch leicht Beize kann.

Answer 4

Angenommen, es gibt viele Einträge für jede ID, würde ich (Pseudo-Code)

 
    for each ID: 
     for each type2 substring of that ID: 
      store it in an ordered list, sorted by start point 
     for each type1 substring of that ID: 
      calculate the end point (or whatever) 
      look it up in the ordered list 
      if there's anything to the right, you have a hit 

Also, wenn Sie haben die Kontrolle über die Anfangs sortieren, dann anstelle von (ID, Start), die Sie wollen sie sortiert nach ID, dann nach Typ (2 vor 1). Dann sortieren Sie innerhalb des Typs nach Startpunkt für Typ2 und den Offset, den Sie für Typ1 vergleichen. Ich bin mir nicht sicher, ob du mit "A vor B" meinst "A beginnt vor B beginnt" oder "A endet vor B beginnt", sondern tue, was immer angemessen ist.

Dann können Sie den gesamten Vorgang ausführen, indem Sie die Liste einmal durchlaufen. Sie müssen keinen Index von Typ2s erstellen, da sie bereits in Ordnung sind. Da auch die Typ1s sortiert sind, können Sie jede Suche mit einer linearen oder binären Suche ausgehend vom Ergebnis der vorherigen Suche durchführen. Verwenden Sie eine lineare Suche, wenn es viele typ1s gibt, verglichen mit typ2 (also liegen die Ergebnisse nahe beieinander), und eine binäre Suche, wenn es viele typ2s gibt, verglichen mit typ1 (die Ergebnisse sind also spärlich). Oder bleiben Sie einfach bei der linearen Suche, da es einfacher ist - diese Suche ist die innere Schleife, aber ihre Leistung ist möglicherweise nicht kritisch.

Wenn Sie nicht die Kontrolle über die Art haben, dann weiß ich nicht, ob es schneller ist, die Liste der Typ2-Teilstrings für jede ID zu erstellen, wie Sie gehen; oder um die gesamte Liste zu sortieren, bevor Sie in die erforderliche Reihenfolge starten; oder einfach mit dem zu arbeiten, was Sie haben, indem Sie ein "lookup" schreiben, das die type1-Einträge beim Durchsuchen der type2s ignoriert (die bereits nach Bedarf sortiert sind). Testen Sie es oder tun Sie einfach alles, was zu einem klareren Code führt. Auch ohne Umsortierung können Sie die Merge-Style-Optimierung weiterhin verwenden, es sei denn, "nach Startindex sortiert" ist die falsche Sache für die Type1s.

Answer 5

Könnte ich überprüfen, von vor, haben Sie sofort vor (dh bedeuten. t1_a, t2_b, t2_c, t2_d sollte nur das Paar geben (t1_a, t2_b), oder haben Sie alle Paare wollen, wo ein Typ1 Wert überall vor einem Typ2 tritt ein in der gleiche Block. (dh (t1_a, t2_b), (t1_a, t2_c), (t1_a, t2_d) für das vorherige Beispiel).

In jedem Fall sollten Sie in der Lage sein, dies mit einem einzigen Durchlauf über Ihre Liste zu tun (vorausgesetzt, dass von ID sortiert, dann Index starten).

Hier ist eine Lösung ing die zweite Option (jedes Paar):

import itertools, operator 

def find_t1_t2(seq): 
    """Find every pair of type1, type2 values where the type1 occurs 
    before the type2 within a block with the same id. 

    Assumes sequence is ordered by id, then start location. 
    Generates a sequence of tuples of the type1,type2 entries. 
    """ 
    for group, items in itertools.groupby(seq, operator.itemgetter(0)): 
     type1s=[] 
     for item in items: 
      if item[1] == TYPE1: 
       type1s.append(item) 
      elif item[1] == TYPE2: 
       for t1 in type1s: 
        yield t1 + item[1:] 

Wenn es vor nur unmittelbar ist, ist es noch einfacher: nur halten Spur des vorherigen Element und das Tupel ergeben, wenn es Typ2 Typ1 und die aktuelle ist.

Hier ist ein Beispiel für die Nutzung und die Ergebnisse zurückgegeben:

l=[[1, TYPE1, 10, 15], 
    [1, TYPE2, 20, 25], # match with first 
    [1, TYPE2, 30, 35], # match with first (2 total matches) 

    [2, TYPE2, 10, 15], # No match 
    [2, TYPE1, 20, 25], 
    [2, TYPE1, 30, 35], 
    [2, TYPE2, 40, 45], # Match with previous 2 type1s. 
    [2, TYPE1, 50, 55], 
    [2, TYPE2, 60, 65], # Match with 3 previous type1 entries (5 total) 
    ] 

for x in find_t1_t2(l): 
    print x 

Das gibt:

[1, 'type1', 10, 15, 'type2', 20, 25] 
[1, 'type1', 10, 15, 'type2', 30, 35] 
[2, 'type1', 20, 25, 'type2', 40, 45] 
[2, 'type1', 30, 35, 'type2', 40, 45] 
[2, 'type1', 20, 25, 'type2', 60, 65] 
[2, 'type1', 30, 35, 'type2', 60, 65] 
[2, 'type1', 50, 55, 'type2', 60, 65]