Apa struktur data yang persisten untuk sekumpulan elemen yang dipesan sebagian?

Saya perlu menyimpan set elemen tipe a. Ketik sebagian memerintahkan, sehingga membandingkan dan dapat kembali lebih kecil, lebih besar, sama atau tak tertandingi. $a_1$ $a_2$

Satu masalah dengan hashtable adalah bahwa dua elemen yang sama dapat direpresentasikan secara berbeda, dan saya tidak memiliki akses ke fungsi hashing yang konsisten dengan kesetaraan.

Membandingkan dua elemen bisa menjadi proses yang panjang sehingga akan menarik untuk meminimalkan perbandingan. Jika perlu, dimungkinkan untuk memoize panggilan ke operator perbandingan. Saya menyadari sekarang bahwa saya hanya perlu menyimpan antik (atau anggap saja begitu). Lebih tepatnya, operasi yang perlu saya lakukan adalah sebagai berikut:

Hapus elemen dari antichain;
Coba tambahkan elemen. Jika elemen lebih kecil dari anggota, jangan tambahkan, jika tidak, tambahkan dan hapus setiap elemen lebih kecil dari itu.

Saya juga dapat terikat setiap elemen oleh dua bilangan bulat, sehingga jika saya tahu bahwa dan , kemudian mengetahui langsung memberi saya . Tentu saja, tidak berarti ... Menemukan batas bilangan bulat adalah operasi yang relatif murah dibandingkan dengan perbandingan elemen yang ditiup penuh. $i_1 < a < i_2$ $i_3 < b < i_4$ $i_2 < i_3$ $a < b$ $i_2 \not< i_3$ $a \not < b$

ds.data-structures functional-programming sorting Abdallah
sumber

Saya pikir kita perlu tahu lebih banyak untuk menjawab pertanyaan Anda dengan cerdas. Apakah Anda menyimpan elemen dan urutan parsial mudah dihitung? Atau apakah Anda juga menyimpan urutan parsial dalam semacam tabel pencarian? Bagaimana Anda bermaksud menggunakan perintah parsial? Apakah Anda berharap menggunakannya dengan cara yang sama seperti urutan linear yang digunakan untuk menyimpan set (misalnya di pohon pencarian)?

Andrej Bauer

Sekarang saya menyadari bahwa saya hanya akan memiliki antik antik, saya tidak yakin ada yang lebih baik daripada solusi naif menyimpan hasil dalam daftar. Jika demikian, maaf untuk masalahnya!

Abdallah

Jika Anda pikir pertanyaan Anda sekarang diperdebatkan, mungkin Anda harus menandainya untuk dihapus / ditutup?

Suresh Venkat

Dua elemen dalam set tidak akan ada bandingannya, tetapi ini tidak berarti bahwa representasi naif adalah yang terbaik yang dapat Anda lakukan. Sebagai contoh, pertimbangkan multiset terbatas yang dipesan dengan penyertaan (= bilangan bulat yang dapat dibagi): ada banyak potensi untuk optimasi, tergantung pada representasi data Anda (menggunakan kardinalitas, menggunakan set dukungan, ...). Optimalisasi ini akan sangat tergantung pada sifat dari relasi urutan. Lalu ada masalah terpisah untuk memutuskan apakah perlu menyimpan informasi tentang elemen yang sekarang dihapus: apakah Anda akan sering membandingkannya dengan penambahan baru?

Gilles 'SANGAT berhenti menjadi jahat'

Oke terima kasih. Jadi saya menambahkan beberapa informasi (kemungkinan bilangan bulat integer) yang dapat mengarah pada optimasi.

Abdallah

Jawaban:

Makalah "Penyortiran dan Seleksi dalam PoSets" oleh Daskalakis, Karp, Mossel, Risensefield, Verbin, 2008 yang menggambarkan representasi dinamis dari PoSets berdasarkan antichains.

Anda mungkin juga tertarik dengan makalah "Succinct Posets" oleh Munro, Nicholson, 2012 yang baru-baru ini dirilis di Arxiv dan dalam daftar pustaka di dalamnya. Struktur data mereka statis tetapi saya berasumsi bahwa langkah selanjutnya adalah memiliki struktur data dinamis.

Jeremy
sumber

Penyortiran dan Pemilihan dalam Poset sangat bagus untuk mendapatkan ide tentang apa yang dibutuhkan untuk struktur data, tetapi algoritma mengasumsikan

menandai elemen-elemen dalam poset (misalnya masalah yang ingin kita selesaikan di tempat pertama!) Untuk hitung hubungan antara dua elemen dalam

setelah membangun struktur data dalam

query. Jadi, makalah ini mengasumsikan pertanyaan tentang hubungan antara dua elemen menjadi mahal dan memetakan elemen poset menjadi sepele, sedangkan memetakan struktur data biasanya mengasumsikan kebalikan dari yang pertama untuk menyelesaikan yang terakhir.

O (1)

$\mathcal{O}(1)$

O (1)

$\mathcal{O}(1)$

O (q n)

$\mathcal{O}(qn)$

Sebastian Graf

Memiliki peta yang diwakili sebagai dekomposisi rantai (minimal) adalah wawasan yang baik. Mempertahankan yang invarian melalui penghapusan adalah hal yang rumit.

Sebastian Graf

Pernahkah Anda melihat Heeringa et al "Mencari dalam Perintah Partial Dynamic Seperti Pohon" ? Mereka memberikan struktur data dinamis untuk masalah pendahulu pada poset. Ini dirancang untuk RAM, tetapi Anda dapat mewakili array sebagai pohon biner seimbang dan hanya menimbulkan overhead multiplikasi sambil membuat struktur berfungsi murni. $O(\lg n)$

jbapple
sumber

Perhatikan ini hanya mencakup perintah parsial 'mirip pohon', misalnya ketemu-semilattis, di mana semua elemen kurang dari atau sama dengan beberapa elemen emembentuk rantai.

Sebastian Graf