Python: füge Bereiche zu einer Liste von Bereichen hinzu, während ich darüber iteriere

Question

Ich stoße auf ein Problem und wünsche, dass mir jemand einen Tipp geben könnte, um es zu überwinden.

Ich habe eine 2D-Python-Liste (83 Zeilen und 3 Spalten). Die ersten beiden Spalten sind die Start- und Endpositionen für ein Intervall. Die 3. Spalte ist ein Ziffernindex (zB 9.68). Die Liste ist nach der 3. Spalte umgekehrt sortiert. Ich möchte alle nicht überlappenden Intervall mit dem höchsten Index erhalten. Hier

ist ein Beispiel für die sortierte Liste:

504 789 9.68 
503 784 9.14 
505 791 8.78 
499 798 8.73 
1024 1257 7.52 
1027 1305 7.33 
507 847 5.86 

Hier ist, was ich versucht:

# Define a function that test if 2 intervals overlap 
def overlap(start1, end1, start2, end2): 
     return not (end1 < start2 or end2 < start1) 

best_list = [] # Create a list that will store the best intervals 
best_list.append([sort[0][0],sort[0][1]]) # Append the first interval of the sorted list 
# Loop through the sorted list 
for line in sort: 
    local_start, local_end = line.rsplit("\s",1)[0].split() 
    for i in range(len(best_list)): 
     best_start = best_list[i][0] 
     best_end = best_list[i][1] 
     test = overlap(int(best_start), int(best_end), int(local_start), int(local_end)) 
     if test is False: 
      best_list.append([local_start, local_end]) 

Und ich bekomme:

best_list = [(504, 789),(1024, 1257),(1027, 1305)] 

Aber ich will:

best_list = [(504, 789),(1024, 1257)] 

Danke!

Answer 1

Nun, ich habe eine Frage zu Ihrem Code. Da sort Zeichenketten enthält dann diese Zeile append([sort[0][0],sort[0][1]]) tut was Sie erwarten?

Wie auch immer, Ihr Problem besteht darin, dass, wenn mehrere Elemente in Ihrer Liste vorhanden sind, es genügt, dass nur einer von ihnen den Überlappungstest zur Liste hinzufügt (nicht was Sie wollen). Z.B. Wenn beide (504, 789),(1024, 1257) vorhanden sind, wird (1027, 1305) in die Liste eingefügt, weil es den Test bestanden hat, wenn es mit (504, 789) verglichen wird.

So machte ich ein paar Änderungen und jetzt scheint es wie erwartet zu funktionieren:

best_list = [] # Create a list that will store the best intervals 
best_list.append(sort[0].rsplit(" ", 1)[0].split()) # Append the first interval of the sorted list 
# Loop through the sorted list 
for line in sort: 
    local_start, local_end = line.rsplit("\s", 1)[0].split() 
    flag = False # <- flag to check the overall overlapping 
    for i in range(len(best_list)): 
     best_start = best_list[i][0] 
     best_end = best_list[i][1] 
     test = overlap(int(best_start), int(best_end), int(local_start), int(local_end)) 
     print(test) 
     if test: 
      flag = False 
      break 
     flag = True 
    if flag: 
     best_list.append([local_start, local_end]) 

Die Hauptidee ist für jedes Element zu überprüfen und, wenn sie alle überlappenden Tests geht dann fügen Sie es (letzte Zeile mein Codecode). Nicht bevor.

Answer 2

Angenommen, Sie Ihre csv analysieren und haben bereits eine Liste mit [(start, stop, index), ....] als [(int, int, float), ...] dann können Sie sie mit folgendem sortieren:

from operator import itemgetter 
data = sorted(data, key=itemgetter(2), reverse=True) 

Dies bedeutet, dass Sie sortieren nach dritten Position und das Ergebnis in umgekehrter Reihenfolge Rückkehr aus max bis min.

def nonoverlap(data): 
    result = [data[0]] 
    for cand in data[1:]: 
     start, stop, _ = cand 
     current_span = range(start, stop+1) 
     for item in result: 
      i, j, _ = item 
      span = range(i, j+1) 
      if (start in span) or (stop in span): 
       break 
      elif (i in current_span) or (j in current_span): 
       break 
     else: 
      result.append(cand) 
    return result 

Dann mit der obigen Funktion erhalten Sie das gewünschte Ergebnis. Für das bereitgestellte Snippet erhalten Sie [(504, 789, 9.68), (1024, 1257, 7.52)]. Ich benutze hier die Tatsache, dass Sie 1 in range(0, 10) verwenden können, die True zurückgeben wird. Während dies eine naive Implementierung ist, können Sie es als Ausgangspunkt verwenden. Wenn Sie nur starten möchten, starten Sie und stoppt ersetzen Sie die Rückleitung mit return [i[:2] for i in result].

Hinweis: Auch ich möchte hinzufügen, dass Ihr Code einen logischen Fehler hat. Sie treffen nach jedem Vergleich eine Entscheidung, müssen jedoch eine Entscheidung treffen, nachdem Sie alle bereits vorhandenen Elemente best_list miteinander verglichen haben. Das ist, warum (504, 789) und (1027, 1305) Ihren Test besteht, aber sollte nicht. Ich wünschte, diese Notiz würde dir helfen.