Здравствуйте, ExtraLamer, Вы писали:
EL>Есть отсортированные числа.
EL>Например [2,10,17,60,132 ... ...]
EL>Ищу максимально быстрый алгоритм для поиска интервала чисел.
EL>Например для вышепривиденного примера. от 5 до 34, ответом будет: 10,17.
EL>Думал о рекурсии с делением массива на 2 и о деревьях. Оба варианта медленные. В идеале за минимальное количество шагов.
Эмм... обычный двоичный поиск. Только вы ищите не одно число (точнее место, где оно могло бы быть), а два. И выводите все что между ними.
Здравствуйте, ExtraLamer, Вы писали:
EL>Есть отсортированные числа.
EL>Например [2,10,17,60,132 ... ...]
EL>Ищу максимально быстрый алгоритм для поиска интервала чисел.
EL>Например для вышепривиденного примера. от 5 до 34, ответом будет: 10,17.
EL>Думал о рекурсии с делением массива на 2 и о деревьях. Оба варианта медленные.
Логарифм -- медленно? А что быстрее, константа? Ну тоже можно сделать, если памяти не жалко. Для каждого n нужно хранить округление вверх (для определения нижней границы интервала) и вниз (для верхней). Например можно завести два массива -- верхних и нижних границ. По типу:
Здравствуйте, ExtraLamer, Вы писали:
EL>Есть отсортированные числа.
EL>Например [2,10,17,60,132 ... ...]
EL>Ищу максимально быстрый алгоритм для поиска интервала чисел.
EL>Например для вышепривиденного примера. от 5 до 34, ответом будет: 10,17.
EL>Думал о рекурсии с делением массива на 2 и о деревьях. Оба варианта медленные. В идеале за минимальное количество шагов.
Вот шуточное решение на стандартных алгоритмах здесь.
А почему поиск дихотомией двух концов отрезка "медленный". Вроде ж теоретически быстрее чем O(Log_2 N) найти нельзя (ибо Log_2 N бит информации по крайней мере нужно, чтобы указать положение одного конца)?
Re[2]: поиск числа в интервале отсортированных чисел
Здравствуйте, ExtraLamer, Вы писали:
EL>Здравствуйте, SergH, Вы писали:
SH>>Но это нужно кучу памяти, если числа большие.
EL>Увы, этот вариант и подобные я сразу отбросил — массивы очень большие.
SH>>Минимальное -- это какое?
EL>Количество шагов где-то в промежутке между хэштаблицей и деревьями. Я бы использовал хэштаблицу но она видимо неприменима.
А можно узнать про параметры массивов данных и параметры работы с ними? Т.е. размер(очень большой), тип(только целочисленный), количество операций поиска интервала в соотношении с размером(приблизительно равны), может ли изменяться массив(нет) и др. Т.к. вы хотите что-то между константным временем и логарифмом, то нужно выполнить оптимизации исходя из природы данных. Сложно что-то подсказать, не зная этой природы.
Re[2]: поиск числа в интервале отсортированных чисел
Здравствуйте, Acteon, Вы писали:
A>Эмм... обычный двоичный поиск. Только вы ищите не одно число (точнее место, где оно могло бы быть), а два. И выводите все что между ними.
Зачем искать второе?
Re[2]: поиск числа в интервале отсортированных чисел
Здравствуйте, _hum_, Вы писали:
__>А почему поиск дихотомией двух концов отрезка "медленный". Вроде ж теоретически быстрее чем O(Log_2 N) найти нельзя (ибо Log_2 N бит информации по крайней мере нужно, чтобы указать положение одного конца)?
Ага. Но на практике бывают нюансы... Вы делаете это неправильно
Здравствуйте, wildwind, Вы писали:
W>Здравствуйте, Acteon, Вы писали:
A>>Эмм... обычный двоичный поиск. Только вы ищите не одно число (точнее место, где оно могло бы быть), а два. И выводите все что между ними.
W>Зачем искать второе?
Зависит от задач, которые нужно выполнять над интервалом. Можно обойтись и без поиска. Но в общем случае надо искать (с оптимизацией по позиции уже найденного первого элемента).
Re[3]: поиск числа в интервале отсортированных чисел
Здравствуйте, ExtraLamer, Вы писали:
EL>Увы, этот вариант и подобные я сразу отбросил — массивы очень большие.
А чисел в них много?
EL>Количество шагов где-то в промежутке между хэштаблицей и деревьями. Я бы использовал хэштаблицу но она видимо неприменима.
Мысль следующая. Если числа сгруппированы в компактные кучки, разбросанные на большом пространстве, можно совместить дерево и таблицу. Для чисел в диапазоне между кучками дерево будет давать ответ сразу. Для остальных чисел оно бужет указывать кучку. Внутри кучек, т.к. они небольшие, можно завести массивы верхних-нижних граней.
Т.е. получится что мы уменьшаем высоту дерева.
Если числа равномерно распределены, то не знаю, что делать.
Хотя можно попробовать прикрутить сюда radix sort. Может быть получится.
Делай что должно, и будь что будет
Re[4]: поиск числа в интервале отсортированных чисел
Здравствуйте, Acteon, Вы писали:
A>Зависит от задач, которые нужно выполнять над интервалом. Можно обойтись и без поиска. Но в общем случае надо искать (с оптимизацией по позиции уже найденного первого элемента).
Задача обозначена конкретно — выдать все числа в интервале; либо итератор по ним.
Re[4]: поиск числа в интервале отсортированных чисел
Здравствуйте, Acteon, Вы писали:
A>А можно узнать про параметры массивов данных и параметры работы с ними? Т.е. размер(очень большой), тип(только целочисленный), количество операций поиска интервала в соотношении с размером(приблизительно равны), может ли изменяться массив(нет) и др. Т.к. вы хотите что-то между константным временем и логарифмом, то нужно выполнить оптимизации исходя из природы данных. Сложно что-то подсказать, не зная этой природы.
Вроде как все написал, суммирую:
* большое количество чисел (например 10 000 000)
* целочисленные
* уже отсортированные
* форма представления данных — любая, например массив или дерево. Лишь бы быстро находился интервал в этой любой форме.
* ограничение на память. думаю не более в 1.5 раза от номинального значения, занимаемое числами.
* Любое число может быть удалено или добавлено. Т.е. каждый раз нужно находить за нового все числа.
Re[5]: поиск числа в интервале отсортированных чисел
EL>Вроде как все написал, суммирую: EL>* большое количество чисел (например 10 000 000) EL>* целочисленные EL>* уже отсортированные EL>* форма представления данных — любая, например массив или дерево. Лишь бы быстро находился интервал в этой любой форме. EL>* ограничение на память. думаю не более в 1.5 раза от номинального значения, занимаемое числами. EL>* Любое число может быть удалено или добавлено. Т.е. каждый раз нужно находить за нового все числа.
если они в отсортированном массиве, то бинарный поиск (в котором склеено 2 поиска) это самый оптимальный вариант.
Но массив не подходит если нужно часто добавлять-удалять. Значит http://en.wikipedia.org/wiki/Skip_list
Re[5]: поиск числа в интервале отсортированных чисел
Здравствуйте, wildwind, Вы писали:
W>Здравствуйте, Acteon, Вы писали:
A>>Зависит от задач, которые нужно выполнять над интервалом. Можно обойтись и без поиска. Но в общем случае надо искать (с оптимизацией по позиции уже найденного первого элемента).
W>Задача обозначена конкретно — выдать все числа в интервале; либо итератор по ним.
Где вы это увидели выдать все числа в интервале? Автор топика хочет интервал найти, а не все числа в нем. Вдруг он хочет сложить первый элемент интервала с последним. Тогда проходить по интервалу совсем не надо, и оптимальнее будет второй поиск.
Re[5]: поиск числа в интервале отсортированных чисел
Здравствуйте, ExtraLamer, Вы писали:
EL>Здравствуйте, Acteon, Вы писали:
A>>А можно узнать про параметры массивов данных и параметры работы с ними? Т.е. размер(очень большой), тип(только целочисленный), количество операций поиска интервала в соотношении с размером(приблизительно равны), может ли изменяться массив(нет) и др. Т.к. вы хотите что-то между константным временем и логарифмом, то нужно выполнить оптимизации исходя из природы данных. Сложно что-то подсказать, не зная этой природы.
EL>Вроде как все написал, суммирую: EL>* большое количество чисел (например 10 000 000) EL>* целочисленные EL>* уже отсортированные EL>* форма представления данных — любая, например массив или дерево. Лишь бы быстро находился интервал в этой любой форме. EL>* ограничение на память. думаю не более в 1.5 раза от номинального значения, занимаемое числами. EL>* Любое число может быть удалено или добавлено. Т.е. каждый раз нужно находить за нового все числа.
Возможно стоит искать не алгоритм поиска, а форму представления данных. Т.е. не массив или дерево, а что-то специфическое (или самому придумать ).
Re[6]: поиск числа в интервале отсортированных чисел
Здравствуйте, Acteon, Вы писали:
A>Где вы это увидели выдать все числа в интервале? Автор топика хочет интервал найти, а не все числа в нем. Вдруг он хочет сложить первый элемент интервала с последним. Тогда проходить по интервалу совсем не надо, и оптимальнее будет второй поиск.
увы, нужны все числа в интервале.
Re[5]: поиск числа в интервале отсортированных чисел
Здравствуйте, ExtraLamer, Вы писали:
EL>Здравствуйте, Acteon, Вы писали:
A>>А можно узнать про параметры массивов данных и параметры работы с ними? Т.е. размер(очень большой), тип(только целочисленный), количество операций поиска интервала в соотношении с размером(приблизительно равны), может ли изменяться массив(нет) и др. Т.к. вы хотите что-то между константным временем и логарифмом, то нужно выполнить оптимизации исходя из природы данных. Сложно что-то подсказать, не зная этой природы.
EL>Вроде как все написал, суммирую: EL>* большое количество чисел (например 10 000 000) EL>* целочисленные EL>* уже отсортированные EL>* форма представления данных — любая, например массив или дерево. Лишь бы быстро находился интервал в этой любой форме. EL>* ограничение на память. думаю не более в 1.5 раза от номинального значения, занимаемое числами. EL>* Любое число может быть удалено или добавлено. Т.е. каждый раз нужно находить за нового все числа.
, чем обычный двоичный поиск не устраивает? Двоичным поиском нашли начало и пошли итерироваться. Итерирование в среднем ведь скорее всего дольше этого самого двоичного поиска будет. Или в интервалы всегда будет очень мало чисел попадать?
В идеале за минимальное количество шагов.
