Menghapus duplikat secara efisien dan dengan overhead memori rendah

Saya ingin memfilter secara efisien daftar bilangan bulat untuk duplikat dengan cara yang hanya disimpan oleh set hasil.

Salah satu cara ini dapat dilihat:

kami memiliki serangkaian bilangan bulat dengan besar (katakanlah ) $S = \{1, \dots{}, N\}$ $N$ $2^{40}$
kami memiliki fungsi dengan, konon, banyak tabrakan (gambar didistribusikan secara seragam dalam ) $f : S \to S$ $S$
kita perlu menyimpan , yaitu $f[S]$ $\{f(x) | x \in S\}$

Saya memiliki estimasi (probabilistik) yang cukup akurat tentang apaadalah, dan karena itu dapat mengalokasikan struktur data di muka (katakan ). $|f[S]|$ $|f[S]| \approx 2^{30}$

Saya punya beberapa ide, tetapi saya tidak yakin apa yang akan menjadi pendekatan terbaik:

bitet keluar dari pertanyaan karena set input tidak sesuai dengan memori.
tabel hash, tetapi (1) membutuhkan beberapa overhead memori, katakanlah 150% daridan (2) tabel harus dieksplorasi ketika dibangun yang membutuhkan waktu tambahan karena overhead memori. $|f[S]|$
semacam "on the fly", lebih disukai dengan kompleksitas (jenis non-perbandingan). Mengenai itu, saya tidak yakin apa perbedaan utama antara jenis ember dan flashsort . $O(N)$
array sederhana dengan pohon pencarian biner, tetapi ini membutuhkan waktu . $O(N \log |f[S]|)$
mungkin menggunakan filter Bloom atau struktur data serupa dapat berguna dalam relaksasi (dengan positif palsu) dari masalahnya.

Beberapa pertanyaan tentang stackoverflow tampaknya mengatasi hal-hal semacam ini ( /programming/12240997/sorting-array-in-on-run-time , /programming/3951547/java -array-Finding-duplikat ), tetapi tampaknya tidak ada yang cocok dengan persyaratan saya.

algorithms data-structures sorting dokter
sumber

Apakah Anda perlu menghitung f [S] (apa pun itu), atau untuk dapat mengetahui dengan cepat apakah ada x di dalamnya?

Gilles 'SO- stop being evil'

@Gilles: Saya percaya bahwa, karena tidak ada struktur yang jelas dapat ditemukan di f [S], kedua solusi itu setara.

doc

Jumlah Anda tidak bertambah. Gambar yang diharapkan dari sebuah fungsi acak pada domain dari ukuran kira-kira . Masalah lain adalah bahwa melalui akan memakan waktu terlalu lama kecuali Anda memiliki superkomputer atau sekelompok besar yang Anda inginkan.

N

$N$

(1 - 1 / e) N

$(1-1/e)N$

2^{56}

$2^{56}$

Yuval Filmus

Waktu untuk pohon pencarian biner adalah , yang mungkin atau mungkin tidak dekat dengan dalam praktiknya tetapi masih lebih akurat.

O (N \log | f [S] |)

$O(N \log |f[S]|)$

O (N \log N)

$O(N\log N)$

jmad

Dengan , bukankah algoritma waktu linear juga akan menjadi penghalang? (Dari perhitungan saya, bahkan jika Anda mempertimbangkan satu elemen dalam 1 nano-detik, itu akan membawa Anda 2 tahun yang baik!).

N \sim 2^{56}

$N \sim 2^{56}$

S

$S$

Aryabhata

Jawaban:

Kenapa tidak bin dan rantai?

Idenya adalah untuk menyimpan bilangan bulat positif yang dapat direpresentasikan oleh bit dalam array dari entri yang mewakili rentang nilai: entri , , mewakili kisaran . Untuk setiap kita dapat menulis mana memiliki bit dan memiliki bit . Cobalah untuk menyimpan (bukan !) Di lokasi : $n = k+m$ $A$ $2^k$ $A[y]$ $y \ge 0$ $[2^m y, 2^m(y+1)-1]$ $1 \le x \lt 2^n$ $x = 2^m y + z$ $y$ $k$ $z$ $m$ $z$ $x$ $y$

Ketika sudah, jangan lakukan apa-apa: adalah duplikat. $A[y]=z$ $x$
Ketika tidak diinisialisasi, simpan di . $A[y]$ $z$ $A[y]$
Jika tidak, simpan indeks ke dalam array terpisah yang digunakan untuk rantai 's (yang bertabrakan pada ) dalam daftar tertaut. Anda harus mencari secara linear melalui daftar yang dikepalai oleh dan, tergantung pada apa yang ditemukan oleh pencarian, berpotensi memasukkan ke dalam daftar. $z$ $y$ $A[y]$ $z$

Pada akhirnya, mudah untuk dipulihkan dengan memutar melalui entri yang diinisialisasi dari dan - dengan hanya menggabungkan dua bitstrings - memasang kembali setiap ditemukan di lokasi (baik secara langsung atau dalam rantai yang direferensikan di sana) ke aslinya nilai . $f(S)$ $A$ $z$ $y$ $x = 2^m y + z$

Ketika distribusi mendekati seragam dan melebihi , tidak akan ada banyak rantai (ini dapat dinilai dengan cara biasa) dan rantai akan cenderung pendek. Ketika distribusinya tidak seragam, algoritme masih berfungsi, tetapi dapat mencapai waktu kuadratik. Jika itu suatu kemungkinan, gunakan sesuatu yang lebih efisien daripada rantai (dan bayar sedikit overhead untuk penyimpanan). $2^k$ $N$

Penyimpanan yang dibutuhkan paling banyak adalah bit untuk dan bit untuk rantai (dengan asumsi ). Ini adalah persis ruang yang dibutuhkan untuk menyimpan nilai setiap bit. Jika Anda yakin dengan keseragaman, Anda dapat mengalokasikan simpanan yang kurang untuk rantai. Jika ketidakseragaman adalah suatu kemungkinan, Anda mungkin ingin meningkatkan dan menganjurkan penyimpanan rantai sepenuhnya. $2^n$ $A$ $2^{2k}$ $m \le k$ $2^k$ $n$ $k$

Cara alternatif untuk memikirkan solusi ini adalah bahwa ia adalah tabel hash dengan fungsi hash yang sangat bagus (ambil bit yang paling signifikan) dan, karena itu, kita hanya perlu menyimpan bit paling tidak signifikan dalam tabel . $k$ $m=n-k$

Ada beberapa cara untuk overlay penyimpanan untuk rantai dengan penyimpanan untuk tetapi tampaknya tidak layak repot, karena itu tidak akan menghemat banyak (dengan asumsi jauh lebih kecil dari ) ruang dan akan membuat kode lebih sulit untuk dikembangkan, debug, dan pertahankan. $A$ $m$ $k$

whuber
sumber

Saya pikir paragraf kedua hingga terakhir adalah yang utama di sini, dan mungkin harus di atas (sebagai ide). Saya tidak tahu istilah "bin and chain" (meskipun masuk akal setelah membaca posting). Gagasan ini dapat diperluas untuk mencoba .

Raphael

Jadi, ini pada input yang berdistribusi buruk. Saya tidak melihat bagaimana ini efisien.

Θ (n^{2})

$\Theta(n^2)$

einpoklum

@einpoklum Jawaban ini secara eksplisit menjelaskan kondisi di mana solusinya efisien.

Whuber