Получить самый глубокий охват сайта из списка непрерывного диапазона

Question

Как выглядит доза непрерывного действия ?

Непрерывный интервал представлен кортежем, (start, end).

Например, (2, 8) относится к области, начинающейся с 2 и заканчивающейся 8.

Что означает самый глубокий охват ?

Для списка диапазонов, например, [(0, 4), (2, 8), (5, 10), (6, 9)], результат накопления будет:

│ 0......4
│    2...........8
│          5.........10
│            6.....9
└────────────────────────
 0 1 2 3 4 5 6 7 8 9 10 ...

Самый глубокий охват диапазона равен (6, 8), что составляет 3.

В этом случае ожидаемый доход должен составлять (6,8)

Мое решение

Я не знаю, как представить непрерывный диапазон, таким образом,Я разбиваю каждый непрерывный промежуток на список чисел и пытаюсь найти наиболее распространенный из встречного результата.

from collections import Couter
import numpy as np

density = Counter()
for start, end in SPAN_LIST:
    density.update(
        np.round(np.arange(start, end, 0.01)), 2)
    )
most_dense_site, most_dense_count = density.most_common()[0]

Результат может быть неточным, а скорость очень большая для большого списка (около миллиардов элементов).Я знаю, что если я увеличу точность, результат будет более точным, но он также будет тратить больше памяти.

Я хотел бы знать, как ускорить процесс и сделать результат более точнымв лучшую сторону?

Answer 1

Разработка в разделе комментариев:

Решение состоит в том, чтобы пройти все начальные и конечные диапазоны, смешанные вместе, чтобы «пройти» через эти точки. Мы будем рассматривать их как события и будем отслеживать, сколько диапазонов мы в настоящее время посещаем. Событие, вызванное началом диапазона, увеличит количество посещенных диапазонов. Событие, вызванное концом диапазона, приведет к уменьшению количества посещенных диапазонов.

(В приведенном ниже коде предполагается, что диапазоны полуоткрыты, включая начало, но не конец.)

Детская площадка: https://ideone.com/fOAOXr

def deepest_coverage(span_list):
    if not span_list:
        raise ValueError("The given list must be non-empty")

    events = []
    for start, end in span_list:
        events.append((start, 1))
        events.append((end, -1))

    events.sort()

    ret = None
    most_visited = currently_visited = 0
    for i in range(len(events)):
        currently_visited += events[i][1]
        if currently_visited > most_visited:
            most_visited = currently_visited
            ret = events[i][0], events[i+1][0]

    return ret


print(deepest_coverage([(0, 4), (2, 8), (5, 10), (6, 9)]))

Выход:

(6, 8)

---

Ресурсы:

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

Answer 2

Я пишу это решение с алгоритмом стреловидности в Python.

1. Распределение по спискам и сглаживание по списку позиций, а также идентификация начальной и конечной точек и запись по баллам.

2. Смежные начальная и конечная точки объединены для повышения производительности и исправления ошибки неправильной позиции.

3. Цикл списка позиций и запись самого глубокого диапазона с его счетом.

from collections import defaultdict

def get_deepest_coverage(span_list):
    """Get the span with the deepest coverage."""
    pos_dict = defaultdict(int)
    for start, end in span_list:
        pos_dict[start] += 1
        pos_dict[end] -= 1
    pos_list = sorted((k, v) for k, v in pos_dict.items() if v)

    deepest_start = deepest_end = None
    deepest_count = current_count = 0
    for index, (pos, score) in enumerate(pos_list):
        current_count += score
        if current_count > deepest_count:
            deepest_count = current_count
            deepest_start, deepest_end = pos, pos_list[index + 1][0]

    return deepest_start, deepest_end, deepest_count


print(get_deepest_coverage([(2, 8), (5, 7), (7, 20)]))

Спасибо @miloszlakomy за все материалы. И хорошее решение.

(Я беру целый день, чтобы написать этот фрагмент, и обнаружил, что @miloszlakomy опубликовал ответ здесь.)

---

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