эффективный алгоритм для проверки _ который_ устанавливает конкретное число принадлежит

Question

Если у меня большой набор непрерывных диапазонов (например, [0..5], [10..20], [7..13], [- 1..37]) и я могу расположить эти наборы в любой мне нравится структура данных, Какой самый эффективный способ проверить , к которому устанавливает конкретный номер test_number?

Я думал о хранении наборов в сбалансированном двоичном дереве на основе малого количества набора (и каждый узел будет иметь все наборы, которые имеют одинаковое наименьшее число своего набора). Это позволит вам эффективно сократить количество наборов в зависимости от того, меньше ли test_number, который вы тестируете с наборами, меньше самого низкого номера набора, а затем сократить этот узел и все узлы справа от этого узла (что иметь в своем диапазоне меньшее число, которое больше номера_теста). Я думаю, что это должно было бы сократить в среднем около 25% наборов, но тогда мне нужно было бы линейно просмотреть все остальные узлы в двоичном дереве, чтобы определить, принадлежал ли test_number этим наборам. (Я мог бы дополнительно оптимизировать, сортируя списки наборов в любом узле по наибольшему числу в наборе, что позволило бы мне выполнять бинарный поиск в определенном списке, чтобы определить, какой набор, если таковые имеются, содержит номер_тестера. К сожалению, большинство наборы, с которыми я буду иметь дело, не имеют перекрывающихся границ множества.)

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

Answer 1

Ваша интуиция относительно актуальности вашей проблемы для графики верна. Подумайте о создании и запросе дерева сегментов . Это особенно хорошо подходит для запроса подсчета, который вы хотите. См. Также описание в разделе Вычислительная геометрия .

.

Answer 2

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

                Set1
              /  |  \
             /   |   \
            /    |    \
         Set2  Set3   Set4

Быстро и легко определить, есть ли совпадение в наборах, поскольку вам нужно только сравнить минимальное и максимальное значения, чтобы упорядочить их. В приведенном выше простом случае Set2 [max] Set1 [max], а также Set1 и Set3 имеют некоторое перекрытие. Это ускорит ваш поиск, потому что, если номер, который вы ищете, находится в Set1, он не будет в Set2 или Set4, и вам не нужно их проверять.

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

Answer 3

Думаю, я бы организовал их так же, как индексирует страницы Mediawiki - как сортировка сегментов . Я не знаю, что это самый эффективный алгоритм из всех существующих, но он должен быть быстрым, и его довольно легко реализовать (даже я справился с этим, и в том числе в SQL !!).

По сути, алгоритм сортировки

For Each SetOfNumbers
   For Each NumberInSet
      Put SetOfNumbers into Bin(NumberInSet)

Затем для запроса, вы можете просто посчитать количество элементов в корзине (MyNumber)

Этот подход будет хорошо работать, когда ваши SetOfNumbers редко меняются, хотя, если они меняются регулярно, обычно не так уж сложно обновлять корзины. Его главный недостаток в том, что он торгует пространством и временем начальной сортировки для очень быстрых запросов.

Обратите внимание, что в алгоритме я расширил диапазоны в SetsOfNumbers - перечисляя каждое число в данном диапазоне.