_DA>Я чего-то не понимаю. Если нужно выдать все числа в интервалеАвтор: ExtraLamer
Дата: 24.06.10
, чем обычный двоичный поиск не устраивает?
видишь, что он писал:
EL>>* Любое число может быть удалено или добавлено. Т.е. каждый раз нужно находить за нового все числа. 
ему нужно за ногу находить все числа
Бинарный поиск работает в массиве с random access, но в такой массив тяжело что-то добавлять/удалять.
Здравствуйте, ExtraLamer, Вы писали:
EL>Здравствуйте, Acteon, Вы писали:
A>>А можно узнать про параметры массивов данных и параметры работы с ними? Т.е. размер(очень большой), тип(только целочисленный), количество операций поиска интервала в соотношении с размером(приблизительно равны), может ли изменяться массив(нет) и др. Т.к. вы хотите что-то между константным временем и логарифмом, то нужно выполнить оптимизации исходя из природы данных. Сложно что-то подсказать, не зная этой природы.
EL>Вроде как все написал, суммирую:
EL>* большое количество чисел (например 10 000 000)
EL>* целочисленные
EL>* уже отсортированные
EL>* форма представления данных — любая, например массив или дерево. Лишь бы быстро находился интервал в этой любой форме.
EL>* ограничение на память. думаю не более в 1.5 раза от номинального значения, занимаемое числами.
EL>* Любое число может быть удалено или добавлено. Т.е. каждый раз нужно находить за нового все числа.
Я для похожей задачки спец. структуру данных лепил. Вот тут статья про мои изыскания —
http://rsdn.ru/article/cpp/segmented_list.xmlАвтор(ы): Алексей Семенюк
Дата: 31.10.2004
В статье приводится пример реализации нестандартного контейнера, позволяющего обеспечить приемлемую скорость доступа к произвольному элементу и вставки/удаления в произвольную позицию.
Здравствуйте, dilmah, Вы писали:
_DA>>Я чего-то не понимаю. Если нужно выдать все числа в интервалеАвтор: ExtraLamer
Дата: 24.06.10
, чем обычный двоичный поиск не устраивает?
D>видишь, что он писал:
D>EL>>>* Любое число может быть удалено или добавлено. Т.е. каждый раз нужно находить за нового все числа.
D>ему нужно за ногу находить все числа
D>Бинарный поиск работает в массиве с random access, но в такой массив тяжело что-то добавлять/удалять.
А, ну если еще и динамическая структура данных нужна, то ничего особо лучше сбаллансированного поискового дерева не придумаешь.
Логарифм медленный для 10кк чисел ?
