Das deutsche Python-Forum

Code: Alles auswählen

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

Code: Alles auswählen

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

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

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])

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])

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")