Какой тип отсортированной структуры данных оптимизирован для поиска элементов в диапазоне?

Question

Допустим, у меня есть несколько объектов с датами, и я регулярно хочу найти все объекты, попадающие между двумя произвольными датами. Какая структура данных будет полезна для этого?

Answer 1

Двоичное дерево поиска звучит как то, что вы ищете. Вы можете использовать его, чтобы найти все объекты в O (log (N) + K), где N - общее количество объектов, а K - количество объектов, которые фактически находятся в этом диапазоне. (при условии, что он сбалансирован). Вставка / удаление - O (log (N)).

Большинство языков имеют встроенную реализацию этого.

• C ++: http://www.cplusplus.com/reference/stl/set/
• Java: http://java.sun.com/j2se/1.4.2/docs/api/java/util/TreeSet.html

Вы можете найти нижнюю границу диапазона (в журнале (n)), а затем выполнять итерацию оттуда до достижения верхней границы.

Answer 2

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

Выполните бинарный поиск, чтобы найти индекс, который> = дата начала. Затем вы можете либо выполнить другой поиск, чтобы найти индекс, который <= конечная дата, оставляя вас со смещением и количеством элементов, либо, если вы собираетесь обрабатывать их в любом случае, просто повторяйте список, пока вы не превысите конечную дату. </p>

Answer 3

Если вам нужно внести изменения с произвольным доступом: дерево, как в ответе v3. Найдите нижнюю часть диапазона с помощью поиска, затем посчитайте вверх. Вставка или удаление узла - это O (log N). stbuton делает хорошее замечание, что если вы хотите разрешить дублирование (как это представляется возможным для событий с метками дат), то вам не нужен набор на основе дерева.

Если вам не нужно вносить изменения с произвольным доступом: отсортированный массив (или вектор или что-то еще). Найдите место начала диапазона с помощью бинарной отбивки, затем посчитайте вверх. Вставка или удаление - O (N) в середине. Дубликаты просты.

Алгоритмическая производительность поиска одинакова в обоих случаях: O (M + log N), где M - размер диапазона. Но массив использует меньше памяти для каждой записи, и может быть быстрее для подсчета в диапазоне, потому что после двоичного преобразования это просто прямой последовательный доступ к памяти, а не следующие указатели.

В обоих случаях вы можете сделать так, чтобы вставка в конце была (амортизирована) O (1). Для дерева сохраните запись конечного элемента в заголовке, и вы получите оценку O (1). Для массива вырастите по экспоненте, и вы получите амортизированный O (1). Это полезно, если вносимые вами изменения всегда или почти всегда «добавляют новое событие с текущим временем», поскольку время (как вы надеетесь) неубывающее количество. Если вы используете системное время, то, конечно, вам придется проверять, чтобы избежать аварий, когда часы сбрасываются назад.

Альтернативный ответ: таблица SQL, и пусть база данных оптимизирует, как она хочет. А структура Google BigTable специально разработана для быстрого выполнения запросов, гарантируя, что результат любого запроса всегда будет последовательной последовательностью из предварительно подготовленного индекса: -)

Answer 4

Трудно дать хороший ответ, не вдаваясь в подробности.

Какая производительность вам нужна?

Если с линейной нормой все в порядке, я бы просто использовал список дат и перебрал бы список, собирая все даты, попадающие в диапазон. Как Эндрю Грант предложил.

У вас есть дубликаты в списке?

Если вам нужно иметь повторяющиеся даты в вашей коллекции, то большинство реализаций бинарного дерева, вероятно, будут отсутствовать. Что-то вроде TreeSet в Java - это реализации реализаций, которые не допускают повторения элементов.

Каковы характеристики доступа? Множество поисков с небольшим количеством обновлений или наоборот?

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

Итак, каковы характеристики доступа к структуре данных, какая производительность вам нужна, и какие структурные характеристики она должна поддерживать (например, должны разрешать повторяющиеся элементы)?

Answer 5

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

A куча кажется идеальным кандидатом. В практических приложениях кучи просто представлены массивом, в котором все объекты хранятся в порядке. Видя, что отсортированный массив является кучей, это просто способ сделать вставку новых объектов, а удаление происходит в нужном месте и в O (log (n)).

Когда вам нужно найти все объекты между датой A (исключено) и B (включено), найдите позицию A (или позицию insert , то есть позицию более раннего элемента позже чем A), и позиция B (или позиция вставки B), и вернуть все объекты между этими позициями (который является просто секцией между этими позициями в массиве / куче)