Atur struktur data untuk penyisipan berulang yang efisien

Saya mencari struktur data hemat-ruang yang menampung set (tanpa pengulangan) elemen wordsize dan mendukung penyisipan cepat (diamortisasi O (1)). Dengan "hemat-ruang" Maksud saya, idealnya, kata-kata untuk disimpan $n + o(n)$ $n$ elemen.

Menjadi himpunan adalah bagian penting dari pertanyaan: jika setiap elemen ditambahkan kali ruang yang digunakan tidak dapat $\log n$ $n\log n$ .

Struktur juga harus mendukung daftar unsur-unsurnya (masuk akal secara efisien); setiap struktur waras seharusnya tidak memiliki masalah di sini. (Pertanyaan keanggotaan cepat merupakan nilai tambah.)

ds.data-structures Charles
sumber

Apakah ada alasan bahwa tabel hash tidak akan melakukan trik?

Dave

@ Dave: Saya tidak berpikir itu memenuhi persyaratan ruang, tapi saya kira jadwal perubahan dinamis yang cukup ketat bisa membuatnya bekerja. Tetapi secara umum saya ingin melihat apa yang ada di luar sana sebelum benar-benar menulis kode.

Charles

Untuk mendapatkan amortisasi dengan pengubahan ukuran dinamis, Anda harus menambah ukurannya dengan fraksi konstan, yang menurut saya tidak memenuhi persyaratan ruang jika Anda ingin benar-benar memenuhi .

O (1)

$O(1)$

n + o (n)

$n+o(n)$

Dave

OK, ini agak konyol — tetapi mengingat bahwa alam semesta Anda memiliki ukuran yang konstan (elemen ukuran), bahkan vektor bit penuh akan memiliki ukuran ...

O (1)

$O(1)$

Magnus Lie Hetland

@ Magnus: Saya kira itu dimaksudkan bahwa fungsi sebenarnya di belakang O dan notasi dalam pertanyaan tidak tergantung pada ukuran kata.

Tsuyoshi Ito

Jawaban:

Saya pikir "Kamus dan Pohon Dinamis Singkat" Raman dan Rao memenuhi batasan yang Anda tentukan. Dari abstrak:

Pertama-tama kita memberikan representasi dari himpunan yang mendukung permintaan keanggotaan dalam waktu kasus terburuk dan penyisipan ke / penghapusan dari dalam diharapkan waktu diamortisasi. Penggunaan representasi bit, di mana adalah informasi-teori ruang minimum untuk mewakili . $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
sumber

Ini terlihat fantastis. (Namun, Anda akan mengerti jika saya membaca koran sebelum menerima, kan?)

Charles

Jika aplikasi Anda dapat mentolerir beberapa kesalahan positif, maka Anda harus menggunakan filter Bloom .

Paraphrase Wikipedia: Filter Bloom adalah struktur data probabilistik yang efisien-ruang yang digunakan untuk menguji apakah suatu elemen adalah anggota suatu set. Positif palsu dimungkinkan, tetapi negatif palsu tidak mungkin. Elemen dapat ditambahkan ke set, tetapi tidak dihapus. Semakin banyak elemen yang ditambahkan ke set, semakin besar kemungkinan positif palsu.

Tyson Williams
sumber

Milik saya tidak bisa, tetapi memberi +1 untuk struktur data yang hebat.

Charles