эффективный алгоритм для тестирования _which_ определяет конкретный номер, принадлежит
Вы можете установить ограничитель только на один символ, поэтому вы не можете использовать квадратные скобки таким образом. Вам нужно будет использовать один символ, такой как «, чтобы он знал, чтобы игнорировать запятые между delmieters.
3 ответа
Ваша интуиция об уместности Вашей проблемы к графике корректна. Рассмотрите создание и запросы дерева сегмента. Это особенно хорошо подходит для запроса подсчета, который Вы хотите. См. также его описание в Вычислительной Геометрии.
Я думаю, создавая древовидную структуру, значительно ускорит вещи (если у Вас есть достаточно наборов и чисел, чтобы проверить, что это стоит начальной стоимости). Вместо двоичного дерева это должно быть троичное дерево. Каждый узел должен был уехать, середина и правильные узлы, где левый узел содержит набор, который является строго меньше, чем набор узлов, право строго больше, и середина имеет перекрытие.
Set1
/ | \
/ | \
/ | \
Set2 Set3 Set4
Это быстро и легко сказать, существует ли перекрытие в наборах, так как только необходимо сравнить минуту и макс. значения, чтобы заказать им. В простом случае выше, Set2 [макс.] <Set1 [минута], Set4 [минута]> Set1 [макс.], и Set1 и Set3 имеют некоторое перекрытие. Это ускорит Ваш поиск, потому что, если число Вы ищете, находится в Set1, это не будет в Set2 или Set4, и Вы не должны проверять их.
Я просто хочу указать, что использование схемы как это только экономит время по наивной реализации проверки каждого набора, если у Вас есть больше чисел для проверки, чем у Вас есть наборы.
Я думаю, что организовал бы их таким же образом, Mediawiki индексирует страницы - как блочная сортировка. Я не знаю, что это - самый эффективный алгоритм там, но это должно быть быстро, и довольно легко реализовать (даже я управлял им, и в SQL в этом!!).
В основном алгоритм для сортировки
For Each SetOfNumbers
For Each NumberInSet
Put SetOfNumbers into Bin(NumberInSet)
Затем для запросов можно просто считать количество объектов в Мусорном ведре (MyNumber)
Этот подход будет работать хорошо, когда Ваш SetOfNumbers редко будет изменяться, хотя, если они регулярно изменяются, это обычно не слишком трудно для хранения Мусорных ведер обновленными также. Это - главный недостаток, то, что это торгует пространством, и начальное время сортировки, для очень быстрых запросов.
Обратите внимание, что в алгоритме я развернул Диапазоны в SetsOfNumbers - перечисление каждого числа в данном диапазоне.