Алгоритм поиска интервалов , в которые попадает число.

[Rulikkk]

Всем привет!
Имеется следующая задача:
Есть некий поток чисел A (каждое порядка 10 знаков).
Есть некий набор интервалов B. Необходимо из интервалов быстро выбрать один, в который попадает каждое новое число.

Есть следующие свойства (их не надо дополнительно проверять):
1. "длина" интервала -- это количество цифр в границе интервала. Длина левой и правой границы всегда одинакова.
0-9 интервал длины 1.
15-67 длины 2.
Интервала 23-345 не может быть.
2. Интервалы не четкие:
В интервал 56-59 должны попасть все числа, которые начинаются на 56, 57, 58 и 59. Таким образом 57345324623 попадает в этот интервал.
3. В рамках одной длины не существует пересекающихся интервалов:
Интервалы 3-5 и 4-6 не могут иметь места,
в то время как 1-7 и 23-45 могут.
4. Среди всех интервалов, в который попадает очередное число A должен быть выбран интервал наибольшей длины:
234567 попадает как в 1-7, так и в 23-23 -> должен быть выбран интервал 23-23.

Количество интервалов большое (10^5), длина большинства интервалов 5, соответственно допускается съесть побольше памяти, чтобы ускорить поиск, сделав какой-то препроцессинг.
Интервалы меняются не часто.

[Akina]

Конвертируешь интервал в набор (скажем 23-25 в 23,24,25), все значения сортируешь. И вот уже вхождение в интервал заменяется на поиск значения, что быстрее. Даже если общее количество наборов составит 10^6 или там 10^7 - это 20-24 бинарных поисков (половинное деление). Должно просто летать...
Чтобы убрать накладнЫе расходы обратного преобразования - хранишь соответствие значение-интервал (23:23-25,24:23-25,25:23-25).
Само собой ищешь начиная с максимальных (т.е. если макс. Интервал пятициферный, сперва ищешь по первым 5 цифрам, если не найдено - по первым четырём, по первым трём... и так пока не найдёшь), таблицы для каждой длины - отдельные.

Сообщение отредактировано: Akina - 03.12.09, 07:31

[Rulikkk]

Akina, а как быть например со свойством

Цитата Rulikkk @ 03.12.09, 07:19

2. Интервалы не четкие:
В интервал 56-59 должны попасть все числа, которые начинаются на 56, 57, 58 и 59. Таким образом 57345324623 попадает в этот интервал.

?

Я не очень понял, как при таких условиях выполняется бинарный поиск.

И во что должен конвертироваться интервал 1-7 ?

[Akina]

Цитата Rulikkk @ 03.12.09, 07:30

В интервал 56-59 должны попасть все числа, которые начинаются на 56, 57, 58 и 59. Таким образом 57345324623 попадает в этот интервал.

Интервал конвертируется в двумерный массив
56 56 59
57 56 59
58 56 59
59 56 59

Берём 57345324623, отрезаем первые 2 цифры (57). Во всём массиве двухциферных значений (сортированном) ищем методом половинного деления совпадение.

Цитата Rulikkk @ 03.12.09, 07:30

во что должен конвертироваться интервал 1-7 ?

1 1 7
2 1 7
3 1 7
4 1 7
5 1 7
6 1 7
7 1 7

[Rulikkk]

Оп, спасибо, заметил правку.

Добавлено 03.12.09, 07:36
Зы,

Цитата Akina @ 03.12.09, 07:34

Интервал конвертируется в двумерный массив
56 56 59
57 56 59
58 56 59
59 56 59

Ну это уж слишком, достаточно указатель хранить =)

[Akina]

Цитата Rulikkk @ 03.12.09, 07:34

это уж слишком, достаточно указатель хранить

Это уже реализация.

[Rulikkk]

Она самая, чёрт побери

Добавлено 03.12.09, 08:09
Я подумал немного над этим алгоритмом.
Как насчёт такой идеи.

1. Искать будем от самого длинного до самого короткого префикса. Это отличная идея. Примем её.

Далее:
2. Разворачивание интервалов -- не очень хорошо, по памяти страшновато.
3. Бинарный поиск рулит.

Вывод. Думать надо как быстро найти нужный интервал в рамках одной длины.
Я вот подумал как можно попробовать.

Пример: интервалы 100-105, 199-456, 567-789.

Алгоритм:
1. Создать сортированный по параметру "число" массив записей (число; начало/конец; интервал)
для примера будет вот так:
(100, начало, 100-105)
(105, конец, 100-105)
(199, начало, 199-456)
(456, конец, 199-456)
(567, начало, 567-789)
(789, конец, 567-789)

2. Бинарный поиск позволит быстро найти в этом массиве место для любого числа.
Зная это место, можно быстро определить (по тому, что слева и справа от него), попало ли оно в интервал, и если да -- то в какой.

Сообщение отредактировано: Rulikkk - 03.12.09, 08:10

[Akina]

Цитата Rulikkk @ 03.12.09, 07:38

Бинарный поиск позволит быстро найти в этом массиве место для любого числа.

Бинарный поиск предназначен для поиска полного совпадения.
В твоей модификации тебе нужно искать нестрогое совпадение, да ещё проверять, попал ты в интервал или между интервалами.

Если тебя не пугает поиск нестрогого - ради бога. Сортируешь свои интервалы по нижней границе, и выполняешь поиск наибольшего, который не больше искомого. После чего проверяешь вхождение в найенный интервал. Если у тебя интервалы "широкие" (кол-во значений > 4 * кол-во интервалов) - это более быстрый способ. Если "узкие" - быстрее способ с развёрткой интервала в набор значений.

Сообщение отредактировано: Akina - 03.12.09, 08:19

[Rulikkk]

Цитата Akina @ 03.12.09, 08:17

Бинарный поиск предназначен для поиска полного совпадения.

Неверно.

пусть есть массив 1 3 78 99 105 169 207 366 405
ищем дихотомией место для числа 250

1-405, средний элемент 105, 105<250
105 - 405, середина 207, 207<250
207-405, середина 366, 366>250
207-366 profit.

Добавлено 03.12.09, 08:34

Цитата Akina @ 03.12.09, 08:17

(кол-во значений > 4 * кол-во интервалов)

Пусть кол-во значений(S) = C * кол-во интервалов(N).
Тогда

Размер массива по твоему алгоритму = Len_a = S = C*N
Мой алгоритм = Len_b = 2*N. Думаю, что тут можно даже улучшить до 1*N.
Таким образом, эти алгоритмы имеют сложность порядка ln(C*N) и ln(2*N), и отличаются всего лишь на константу...
Но вот по памяти разница куда более существенна.

[Akina]

Цитата Rulikkk @ 03.12.09, 08:22

пусть есть массив 1 3 78 99 105 169 207 366 405
ищем дихотомией место для числа 250

А для 400? а для 410? лишние проверки, которые не ложатся в алгоритм, а являются его дополнением, позволяющим искать нестрого.
Впрочем, это в данном случае неважно.

Добавлено 03.12.09, 08:36
Да и чего ты со мной споришь? тебе же реализовывать, а не мне. И принимать результат у тебя тоже не мне.

[Rulikkk]

Цитата Akina @ 03.12.09, 08:34

А для 400? а для 410? лишние проверки, которые не ложатся в алгоритм, а являются его дополнением, позволяющим искать нестрого.
Впрочем, это в данном случае неважно.

Ага

Хорошо лишь что в C# Array.BinarySearch кажется уже это всё позволяет =)

[MBo]

Левые концы интервалов представляем в виде строк
Дополняем до наибольшей длины символом '*' (его код меньше, чем у цифр)
Сортируем полученное лексикографически
из набора 1 2 3 13-15 21-22 27-28 215-217
получаем
1**
13*
2**
21*
215
27*
3**
Теперь каждое для каждого числа, переведенного в аналогичную форму, бинарным поиском легко найти левую границу интервала, в который он может попасть, и после этого проверить правую границу интервала

[Rulikkk]

0-5, 6-9
00-54, 56-99
000-555, 556-558
перейдёт в
0**
00*
000
556
56*
6**

для интервала 559:
0**
00*
000
556
БИНАРНЫЙ ПОИСК ПОКАЖЕТ СЮДА
56*
6**

но:
556-558 не подходит
000-555 не подходит
00-54 не подходит
0-5 подходит.

Получаем что после бинарного происходит линейный поиск наверх.
В общем-то может получится достаточно долго, нет?

[MBo]

Верно, упустил. Попробуем так:
Второй список - правых концов, но в нем дополняем не звездочкой, а "@", и ищем правую границу.
54@
555
558
5@@
99@
9@@

[Pavlovsky]

1) Будем воспринипать входной поток чисел, как поток символьных строк. То есть сравнение двух чисел ХХХХХ>YYYYYYY будем воспринимать как сравнение текстовых строк, упорядоченных в лексиграфическом порядке.
2) Для начала уберем из расмотрения вложенные интервалы.

Итак у нас есть множество интервалов, которуе не пересекаются друг с другом.

3) Дальше рулит бинарный поиск. Пример. Пусть у нас есть интервалы: 11-13 (15) 18-19 (24) 25-29 (30) 38-46. В скобках число для сравнения в бинарном дереве.

Входное число 2499999
2499999>24 идем вправо
2499999<30 идем влево
Так как достигли листа дерева, проверяем на вхождение в интервал. 2499999 не входит в интервал 25-29. Облом.

Входное число 26
26>24 идем вправо
26<30 идем влево
Так как достигли листа дерева, проверяем на вхождение в интервал. 26 входит в интервал 25-29. Интервал найден!

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

Сообщение отредактировано: Pavlovsky - 03.12.09, 13:32