Установить структуру данных для эффективных повторных вставок

Я ищу экономически эффективную структуру данных, которая содержит наборы (без повторений) элементов wordize и поддерживает быструю вставку (амортизированный O (1)). Под «эффективным с точки зрения пространства» я подразумеваю в идеале слов для хранения элементов. $n + o(n)$ $n$

Быть множеством - важная часть вопроса: если каждый элемент добавляется раз, используемое пространство не может быть . $\log n$ $n\log n$

Структура должна также поддерживать перечисление своих элементов (разумно и эффективно); у любой здравомыслящей структуры здесь не должно быть проблем. (Быстрые запросы членства являются плюсом.)

ds.data-structures Чарльз
источник

Есть ли причина, по которой хеш-таблица не сработает?

Дейв

@ Дэйв: я не думаю, что это соответствует требованию к месту, но я предполагаю, что достаточно строгий график динамического изменения размера может заставить его работать. Но в целом я хотел бы увидеть, что там есть, прежде чем писать код.

Чарльз

Чтобы амортизировать

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

O (1)

$O(1)$

n + o (n)

$n+o(n)$

Дейв

O (1)

$O(1)$

@Magnus: я предполагаю, что это означает, что фактические функции за O- и o-нотациями в вопросе не зависят от размера слова.

Tsuyoshi Ito

Ответы:

Я думаю, что «Краткие динамические словари и деревья» Рамана и Рао соответствуют указанным вами границам. Из аннотации:

$S \subseteq U = \{0, \dots , m − 1\}, |S| = n$ $O(1)$ $S$ $O(1)$ $B + o(B)$ $B = \lceil lg \binom{m}{n} \rceil$ $S$

jbapple
источник

Это выглядит фантастически. (Вы поймете, если я прочитал газету, прежде чем принять, хотя, верно?)

Чарльз

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

Перефразирование Википедии: Фильтр Блума - это экономически вероятностная структура данных, которая используется для проверки того, является ли элемент членом набора. Ложные срабатывания возможны, а ложные - нет. Элементы могут быть добавлены в набор, но не удалены. Чем больше элементов добавлено в набор, тем больше вероятность ложных срабатываний.

Тайсон Уильямс
источник

Мой не может, но +1 для отличной структуры данных.

Чарльз