Liste mit Bereichen nach Überlappungen filtern

[Fire Spike]

Hallo Leute

Ich habe eine Liste wie z.B.

Code: Alles auswählen

 [[0,2], [2,3], [6,8], [8, 15], [9, 13], [9,11]]

Ich möchte alle Bereiche herauslöschen die sich mit einem anderen überlappen.
Es sollte aber immer mindestens noch ein Bereich übrig bleiben.
Der Bereich sollte der grösste sein. Ich hoffe das Beispiel macht es euch klar:

Code: Alles auswählen

[[0,2],[8,15]]

Das ist was ich im Moment habe (funktioniert nicht korrekt):

Code: Alles auswählen

def remove_overlapping(ranges):
    result = []
    for i in range(len(ranges) -1):
        if ranges[i][1] > ranges[i+1][0]:
            result.append([ranges[i][0], ranges[i][1]])

    return result

Wie könnte ich das umsetzen?
Vielen Dank für die Hilfe

[Sirius3]

Und was ist mit [2,3] oder [6,8]?
Sollen die aneinanderstoßenden Bereiche vereinigt werden?
Also soll das Ergebnis eigentlich [[0,3], [6,15]] sein?

[Fire Spike]

[2,3] kollidiert mit [0,2] und [0,2] wird ausgewählt da es länger als [2,3] ist.
[6,8] mit [8,15]
Und nein, es soll nicht vereinigt werden. Was dann wieder auf mein Beispiel herauslaufen würde.

[ThomasL]

Schau mal, ob das hier deinen Anforderungen entspricht.

Code: Alles auswählen

data = [[0,2], [2,3], [6,8], [8, 15], [9, 13], [9,11]]

ranges = {index: set(range(start, end + 1)) for index, (start, end) in enumerate(data)}

indices = list(ranges.keys())
keep = set(indices)
for i in range(len(indices) - 1):
    for j in range(i + 1, len(indices)):
        a, b = ranges[indices[i]], ranges[indices[j]]
        if len(a.intersection(b)) > 0:
            if len(a) >= len(b):
                keep.discard(indices[j])
            else:
                keep.discard(indices[i])

ranges = {key: value for key, value in ranges.items() if key in keep}

for index in ranges:
    print(data[index])

[Fire Spike]

@ThomasL
Danke für deinen Code. Der funktioniert genau so wie ich es mir vorgestellt habe.
Da ich sehr viele Daten habe und es dementsprechend viel Zeit benötigt, siehst du noch Möglichkeiten den Code zu Optimieren?

[Sirius3]

Bei sehr vielen Daten benutzt man numpy.diff mit numpy.where.

[ThomasL]

Freut mich das der Code so bei dir läuft.

Klar, da könnte man noch optimieren.
Wie groß ist denn deine Liste mit Bereichen und wie groß können die jeweiligen Bereiche werden?

[Fire Spike]

Die Liste hat eine Grösse von mindestens 10000 Bereichen. Die Grösse eines Bereiches ist sehr variabel. Von eins bis auch mehrere Tausend. Der Inhalt der Bereiche ist allerdings selten grösser wie 10.

[ThomasL]

Habe mal ein wenig rumgespielt und das hier ist dabei rausgekommen.
Anstatt mit Mengenoperationen zu arbeiten, einfach direkte Vergleiche der Bereiche beschleunigt das ganze um mehr als 100%

Bei n Bereichen (n=10000 bei dir) müssen ja n²/2 Vergleiche durchgeführt werden, das dauert also.

Bei 60000 Bereichen dauert das ganze bei mir immerhin 10,5 Minuten.

Code: Alles auswählen

ranges = [[0,2], [2,3], [6,8], [8, 15], [9, 13], [9,11]]

ranges = ranges * 1000 # 6000 Bereiche - 18 Mio Vergleiche
# Laufzeit 5.96 s ± 16.5 ms per loop

# ranges = ranges * 10000 # 60000 Bereiche - 1800 Mio Vergleiche
# Laufzeit 10min 31s ± 9.71 s per loop

keep = set(list(range(len(ranges))))
lengths = [ende - start + 1 for start, ende in ranges]

for i in range(len(ranges) - 1):
    a_start, a_ende = ranges[i]
    for j in range(i + 1, len(ranges)):
        b_start, b_ende = ranges[j]
        if not (a_ende < b_start or b_ende < a_start):
            if lengths[i] >= lengths[j]:
                keep.discard(j)
            else:
                keep.discard(i)
                
for index in range(len(ranges)):
    if index in keep:
        print(ranges[index])

[ThomasL]

So, ich dachte mir, dass ist doch mal etwas, bei dem man mit Multiprocessing noch mehr raus holen kann. Rausgekommen ist das hier.
Bei den von dir angegebenen 10000 Bereichen, verkürzt sich die 1 CPU Laufzeit von 16,5 sek bei 100 Prozessen auf unter 0,3 sek.
Bei 60000 Bereichen von solo 600 sek auf unter 2 sek.
Ich denke damit kannst du arbeiten, oder?

Code: Alles auswählen

import multiprocessing
import time

def check(sub_ranges):
    keep = set(list(range(len(sub_ranges))))
    lengths = [ende - start + 1 for start, ende in sub_ranges]

    for i in range(len(sub_ranges) - 1):
        a_start, a_ende = sub_ranges[i]
        for j in range(i + 1, len(sub_ranges)):
            b_start, b_ende = sub_ranges[j]
            if not (a_ende < b_start or b_ende < a_start):
                if lengths[i] >= lengths[j]:
                    keep.discard(j)
                else:
                    keep.discard(i)

    return [sub_ranges[index] for index in keep]


def check_all(ranges):
    with multiprocessing.Pool() as pool:
        return [result
                for results in pool.map(check, ranges)
                for result in results]

if __name__ == "__main__":
    tasks = 100
    ranges = [[0,2], [2,3], [6,8], [8, 15], [9, 13], [9,11], [7, 10], [9, 14], [7, 9], [-1, 0]] * (1000 // tasks)
    sp_ranges = ranges * tasks
    mp_ranges = [ranges] * tasks
    
    start_time = time.time()
    print('Final result', check(sp_ranges))
    duration = time.time() - start_time
    print(f"Solo Duration {duration} seconds")
    
    start_time = time.time()
    print('Final result', check(check_all(mp_ranges)))
    duration = time.time() - start_time
    print(f"MP Duration {duration} seconds")

10000 Bereiche, 10 Prozesse
Solo Duration 16.32785940170288 seconds
MP Duration 0.7143480777740479 seconds

10000 Bereiche, 20 Prozesse
Solo Duration 16.62518858909607 seconds
MP Duration 0.4435901641845703 seconds

10000 Bereiche, 40 Prozesse
Solo Duration 16.318793058395386 seconds
MP Duration 0.340346097946167 seconds

10000 Bereiche, 100 Prozesse
Solo Duration 16.29350256919861 seconds
MP Duration 0.28729987144470215 seconds

60000 Bereiche, 30 Prozesse
Solo Duration 601.739506483078 seconds
MP Duration 4.643344402313232 seconds

60000 Bereiche, 60 Prozesse
Solo Duration 601.739506483078 seconds
MP Duration 2.509606122970581 seconds

60000 Bereiche, 100 Prozesse
Solo Duration 601.739506483078 seconds
MP Duration 1.6860344409942627 seconds