Эффективное удаление дубликатов с небольшим объемом памяти

Я хочу эффективно отфильтровать список целых чисел для дубликатов таким образом, чтобы хранить только полученный набор.

Один способ это можно увидеть:

• у нас есть диапазон целых чисел с N большим (скажем, 2 40 )$S = \{1, \dots{}, N\}$$N$$2^{40}$
• у нас есть функция с, предположительно, многими столкновениями (изображения равномерно распределены в S )$f : S \to S$$S$
• тогда нам нужно хранить , то есть { f ( x ) | x ∈ S $f[S]$$\{f(x) | x \in S\}$

У меня есть достаточно точная (вероятностная) оценка того, что есть, и поэтому может выделять структуры данных заранее (скажем, | f [ S ] | ≈ 2 30 ).$|f[S]|$$|f[S]| \approx 2^{30}$

У меня было несколько идей, но я не уверен, что будет лучшим подходом:

• о наборе битов не может быть и речи, потому что входной набор не помещается в память.
• хеш-таблицу, но (1) она требует некоторой перегрузки памяти, скажем, 150% от и (2) таблица должна быть исследована при сборке, что требует дополнительного времени из-за нехватки памяти.$|f[S]|$
• сортировка «на лету», предпочтительно со сложностью (сортировка без сравнения). В связи с этим я не уверен, в чем заключается основное различие между сортировкой сегментов и флэш- сортировкой .$O(N)$
• простой массив с бинарным деревом поиска, но для этого требуется время .$O(N \log |f[S]|)$
• возможно, использование фильтров Блума или подобной структуры данных может быть полезно для ослабления (с ложными срабатываниями) проблемы.

Некоторые вопросы по stackoverflow, кажется, решают такие вещи ( /programming/12240997/sorting-array-in-on-run-time , /programming/3951547/java -array-find-duplicates ), но ни один из них не соответствует моим требованиям.

Почему не мусорное ведро и цепь?

Идея состоит в том, чтобы хранить натуральные числа, представимые битами, в массиве A из 2 $n = k+m$$A$$2^k$ записей, представляющих диапазоны значений: запись , y ≥ 0 , представляет диапазон [ 2 m y , 2 m ( y) + 1 ) - 1 ] . Для любого 1 ≤ x < 2 n мы можем написать x = 2 m$A[y]$$y \ge 0$$[2^m y, 2^m(y+1)-1]$$1 \le x \lt 2^n$ где y имеет k битов, а z имеет m битов. Попробуйте сохранить z (не x !) В месте y :$x = 2^m y + z$$y$$k$$z$$m$$z$$x$$y$

• Когда , ничего не делать: x является дубликатом.$A[y]=z$$x$

• Когда не инициализирован, сохраните z в A [ y ] .$A[y]$$z$$A[y]$

• В противном случае сохраните индекс в отдельном массиве, который используется для связывания (которые столкнулись в точке y ) в связанных списках. Вам нужно будет выполнить линейный поиск по списку, возглавляемому A [ y ], и, в зависимости от того, что обнаруживает поиск, потенциально вставить z в список.$z$$y$$A[y]$$z$

В конце концов, легко восстановить, просматривая инициализированные записи A и - путем простого объединения двух цепочек битов - повторной сборки каждого z, найденного в местоположении y (либо непосредственно, либо внутри цепочки, на которую есть ссылка), в исходную значение x = 2 m y + z .$f(S)$$A$$z$$y$$x = 2^m y + z$

Когда распределение близко к равномерному и превышает N , цепочки не будет много (это можно оценить обычными способами), и цепочки будут иметь тенденцию быть короткими. Когда распределение неоднородно, алгоритм все еще работает, но может достигнуть квадратичной синхронизации. Если это возможно, используйте что-то более эффективное, чем цепочки (и заплатите немного за хранение).$2^k$$N$

Необходимая память составляет не более битов для A и 2 2 k битов для цепочек (при условии, что m ≤ k ). Это именно то пространство, которое требуется для хранения 2 k значений по n битов каждое. Если вы уверены в единообразии, вы можете перераспределить хранилище для цепей. Если возможна неоднородность, вы можете увеличить k и полностью защитить цепочку хранения.$2^n$$A$$2^{2k}$$m \le k$$2^k$$n$$k$

Альтернативный способ мышления об этом решении является то , что она является хэш - таблица с особенно хорошей хеш - функции (взять наиболее значимые биты) , и из - за этого, мы только должны хранить наименее значимый т = п - K битов стол.$k$$m=n-k$

Существуют способы наложения хранилища для цепей на хранилище для но, похоже, это не стоит беспокоиться, потому что это не сэкономит много (при условии, что m намного меньше, чем k ) пространства и усложнит разработку кода, отлаживать и поддерживать.$A$$m$$k$