объединить интервалы без использования циклов и классического кода Python - PullRequest
Новая
       6

объединить интервалы без использования циклов и классического кода Python

0 голосов
/ 22 февраля 2019

Моя проблема заключается в объединении интервалов, где у меня есть перекрывающийся пример: 

input: 
[(4,8),(6,10),(11,12),(15,20),(20,25)] 
output: 
[(4, 10),(11,12), (15, 25)]
input: 
([(4,8),(6,10),(11,12),(15,20)])
output: 
[(4, 10),(11,12), (15, 20)]

Я сделал это с классическим кодом Python (используя циклы, если условия), НО я хочу сделать это с библиотеками Python (пандыняшка ..) в нескольких строках есть предложения?Заранее спасибо

Ответы [ 2 ]

0 голосов
/ 22 февраля 2019

Предполагая, что ваши входные кортежи отсортированы, как в примерах, что-то вроде этого делает работу: 

p = [(4, 8), (6, 10), (11, 12), (15, 20), (20, 25)] 

ind = np.where(np.diff(np.array(p).flatten()) <= 0)[0]
np.delete(p, [ind, ind+1]).reshape(-1, 2)

output: 

array([[ 4, 10],
       [11, 12],
       [15, 25]])

Затем вы можете преобразовать его в [(4, 10), (11, 12), (15, 25)] используя, например, list(map(tuple, ...)).

Редактировать : вышеприведенное работает, только если каждый кортеж (x_i, y_i) таков, что x_i <= x_{i+1} и y_i <= y_{i+1} для всех я, как висходные примеры.

Чтобы заставить его работать с единственным условием x_i <= y_i для всех i, необходимо предварительно обработать список: 

# Example from comments (modified by subtracting the min value and removing duplicates)
p = [(0, 90), (72, 81), (87, 108), (459, 606)]

p = list(zip(sorted([tup[0] for tup in p]), sorted([tup[1] for tup in p])))

ind = np.where(np.diff(np.array(p).flatten()) <= 0)[0]
ind = ind[ind % 2 == 1]  # this is needed for cases when x_i = y_i
np.delete(p, [ind, ind+1]).reshape(-1, 2)

Вывод: 

array([[  0, 108],
       [459, 606]])
0 голосов
/ 22 февраля 2019

Я не уверен, что это обязательно лучший вариант, так как он требует O(max_interval_value * num_intervals) времени и памяти, но это простая реализация с NumPy: 

import numpy as np

def simplify_intervals(intervals):
    # Make intervals into an array
    intervals = np.asarray(intervals)
    # Make array for zero to the greatest interval end (plus bounds values
    r = np.arange(intervals[:, 1].max() + 3)[:, np.newaxis]
    # Check what elements of the array are within each interval
    m = (r >= intervals[:, 0] + 1) & (r <= intervals[:, 1] + 1)
    # Collapse belonging test for each value
    ind = m.any(1).astype(np.int8)
    # Find where the belonging test changes
    d = np.diff(ind)
    # Find interval bounds
    start = np.where(d > 0)[0]
    end = np.where(d < 0)[0] - 1
    # Make final intervals array
    return np.stack((start, end), axis=1)

print(simplify_intervals([(4, 8), (6, 10), (11, 12), (15, 20), (20, 25)]))
# [[ 4 12]
#  [15 25]]
print(simplify_intervals(([(4,8),(6,10),(11,12),(15,20)])))
# [[ 4 12]
#  [15 20]]

Примечание: это предполагает положительные значения интервала,Он может быть адаптирован для поддержки отрицательных диапазонов и фактически немного оптимизирован, чтобы рассматривать только значения от наименьшего к наибольшему.

РЕДАКТИРОВАТЬ:

Если вы хотите использовать этот метод для большихчисло интервалов или границ, вместо этого вы можете воспользоваться Numba: 

import numpy as np
import numba as nb

@nb.njit
def simplify_intervals_nb(intervals):
    n = 0
    for _, end in intervals:
        n = max(n, end)
    r = np.arange(n + 3)
    m = np.zeros(n + 3, dtype=np.bool_)
    for start, end in intervals:
        m |= (r >= start + 1) & (r <= end + 1)
    ind = m.astype(np.int8)
    # Find where the belonging test changes
    d = np.diff(ind)
    # Find interval bounds
    start = np.where(d > 0)[0]
    end = np.where(d < 0)[0] - 1
    # Make final intervals array
    return np.stack((start, end), axis=1)

Быстрый тест в IPython: 

import random

random.seed(100)
start = [random.randint(0, 10000) for _ in range(300)]
end = start = [s + random.randint(0, 3000) for s in start]
intervals = list(zip(start, end))
print(np.all(simplify_intervals(intervals) == simplify_intervals_nb(intervals)))
# True
%timeit simplify_intervals(intervals)
# 15.2 ms ± 179 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit simplify_intervals_nb(intervals)
# 9.54 ms ± 146 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
...