эффективный способ объединения последовательных элементов списка на основе условия

Question

с учетом списка кортежей, в которых значения сортируются, каков наиболее эффективный способ слияния последовательных элементов, если разница между элементами меньше значения x

в следующем списке, если x=100, затем (287, 790) и (855, 945) будут объединены в (287,945), затем (287,945) объединятся с (955, 2205) в (287,2205) и так далее

[(287, 790),
 (855, 945),
 (955, 2205),
 (2230, 2264),
 (2362, 2729),
 (3906, 4473)]

, и это будет вывод в этом случае:

[(287, 2729),
 (3906, 4473)]

Answer 1

Если вы объединяете это только один раз (это означает, что вы не пытаетесь создать несколько разных результирующих кортежей из одного исходного кортежа), лучшее, что вы можете сделать, это будет решение O(n) или, по сути, для l oop.

x = 100
to_merge = [(287, 790),
 (855, 945),
 (955, 2205),
 (2230, 2264),
 (2362, 2729),
 (3906, 4473)]

def merge(lst, x):
    if not lst or len(lst) <= 1:
        return lst
    new_lst = []
    start, end = lst[0]
    for start1, end1 in lst[1:]:
        if start1 - end < x:
            end = end1
        else:
            new_lst.append((start, end))
            start, end = start1, end1
    new_lst.append((start, end))
    return new_lst

print(merge(to_merge, x))

Если бы вам пришлось проделать это несколько раз с одним и тем же исходным списком, то вы могли бы найти более эффективным использование метода программирования Dynami c.

Answer 2

orig_list = [
 (287, 790),
 (855, 945),
 (955, 2205),
 (2230, 2264),
 (2362, 2729),
 (3906, 4473)]
merged_list = []
# iterate through original list
orig_iter = iter(orig_list)
# pop the first element and keep track of it as the "last tuple visited"
last_tuple = next(orig_iter)
for next_tuple in orig_iter:
    # if tuples are too close, merge them
    if (next_tuple[0] - last_tuple[1]) < 100:
        last_tuple = (last_tuple[0], next_tuple[1])
    # otherwise, push the last_tuple to the new list and replace it
    else:
        merged_list.append(last_tuple)
        last_tuple = next_tuple
# when we're done traversing the list, push whatever's remaining onto the end
merged_list.append(last_tuple)

print(merged_list)
# [(287, 2729), (3906, 4473)]

Обратите внимание, что (287, 2205) объединяется с (2230, 2264), так как разница меньше 100. Я подозреваю, что это была опечатка в исходном вопросе.

Answer 3

x = 100
data = [
        (287, 790),
        (855, 945),
        (955, 2205),
        (2230, 2264),
        (2362, 2729),
        (3906, 4473)
]

def merger(x, data):
    merged = [data[0],]
    the_others = [data[i] for i in range(1, len(data)) if (data[i][0]-data[i-1][1])>x]
    merged.extend(the_others)
    return merged

print(merger(x, data))

Answer 4

Это похоже на ответ MZ , но с использованием вложенного списка вместо списка кортежей, чтобы упростить слияние:

def merge(intervals, difference):
    merged = []
    prev_end = float('-inf')  # Initial loop value
    for start, end in intervals:
        if start-prev_end < difference:
            # Merge, i.e. set the new top end value
            merged[-1][1] = end
        else:
            # The current interval becomes the top
            merged.append([start, end])
        prev_end = end  # For next loop
    return merged


some_list = [
    (287, 790),
    (855, 945),
    (955, 2205),
    (2230, 2264),
    (2362, 2729),
    (3906, 4473)]
print(merge(some_list, 100))  # -> [[287, 2729], [3906, 4473]]

Преобразование результата в список кортежей также O (n).