Enumerasi rentang ImmutableSortedDictionary dengan kunci

11

Saya sedang membaca tentang C # ImmutableSortedDictionarydi System.Collections.Immutabledan berpikir tentang cara menerapkannya dalam program saya. Saya sangat suka C ++ lower_bounddan upper_bound(lihat di sini ), dan saya agak berharap untuk melihat sesuatu semacam itu untuk rentang pencarian. Namun, metode serupa tampaknya tidak ada dalam dokumentasi . Apakah saya melewatkan sesuatu? Atau apakah MS benar-benar menyediakan kamus yang diurutkan tanpa akses yang efisien ke rentang yang diurutkan? Itu tidak persis seperti sesuatu yang bisa dilakukan pada salah IEnumerablesatu kunci seperti mengatakan metode ekstensi, jadi saya agak bingung saya tidak melihat sesuatu yang disediakan langsung oleh koleksi.

c# .net algorithm immutability immutable-collections J Trana
sumber
Eric Lippert membagikan implementasi AVL tree yang tidak dapat diubah pada tahun 2008. Dari komentar, saya belum berpikir ini telah dioptimalkan secara khusus untuk kecepatan atau efisiensi, tetapi IBinarySearchTree<K,V>implementasinya terlihat lebih dekat dengan apa yang saya harapkan. Aku ingin tahu apakah dia pernah mempermainkannya lebih jauh?
J Trana
The ImmutableList<T>kelas juga diimplementasikan sebagai pohon AVL. Dari kode sumber :/// The root node of the AVL tree that stores this set.
Theodor Zoulias
Apakah Anda tahu apakah maksudnya daftar tersebut menggunakan AVL true untuk mengimplementasikan immutability atau jika pohon AVL itu sendiri tidak dapat diubah? (mungkin tidak masalah karena mereka toh tidak mengekspos pohon itu).
J Trana
Berikut adalah keuntungan dari ImmutableList<T>(didukung oleh pohon AVL) dibandingkan ImmutableArray<T>(didukung oleh array), menurut dokumentasi . Alasan untuk menggunakan daftar tidak berubah: 1) Memperbarui data adalah umum atau jumlah elemen tidak diharapkan kecil. 2) Memperbarui koleksi lebih penting daripada kinerja iterasi konten.
Theodor Zoulias
Ini karena ketika menambahkan atau menghapus elemen dari pohon AVL besar, Anda bisa mendapatkan pohon baru tanpa merusak yang asli, dengan berbagi sebagian besar node dan membuat hanya beberapa node baru. ( Persistent data structure - Trees )
Theodor Zoulias

Jawaban:

9

Sangat menjengkelkan bahwa koleksi bawaan yang tersedia tidak menawarkan serangkaian fitur lengkap (seperti metode yang SortedDictionarykurang BinarySearch), memaksa kami untuk mencari solusi pihak ketiga (seperti perpustakaan C5 ).

Dalam kasus Anda, alih-alih ImmutableSortedDictionaryAnda mungkin bisa menggunakan ImmutableSortedSet, menanamkan nilai dalam kunci dan menggunakan pembanding yang sesuai. Setidaknya API dari kelas ini berisi properti Mindan Max.

Theodor Zoulias
sumber
2
Sebagai catatan, kelas abadi lainnya, the ImmutableList<T>, diimplementasikan secara internal sebagai pohon . Jadi 10 kali lebih lambat dan mengalokasikan 12 kali lebih banyak memori daripada a List<T>. Gunakan ImmutableArray<T>sebagai gantinya.
Theodor Zoulias
1
Hehe, saya sudah menggunakan C5 tetapi mencari untuk melihat apa yang tersedia untuk koleksi abadi (di luar foto). Terima kasih! Saya akan mengulurkan harapan bahwa orang lain telah memecahkan masalah ini dalam beberapa bentuk, tetapi saya akan mengingatnyaImmutableSortedSet
J Trana
@TheodorZoulias apa gunanya memiliki metode BinarySearch di SortedDictionary, ketika metode TryGetValue bekerja di log (N)? lihat di sini
Giorgi Chkhikvadze
2
@GiorgiChkhikvadze, BinarySearch dapat memberikan Anda elemen berikutnya yang lebih besar dari item yang Anda cari, jika tidak ditemukan kecocokan yang tepat.
Theodor Zoulias
1
@GiorgiChkhikvadze Mungkin perbedaan terbesar di sini adalah bahwa nilai kembali bukan hanya nilai tunggal dalam koleksi, tetapi lebih merupakan cara untuk mengindeks ke dalam koleksi secara efisien. Metode BinarySearch khusus bukan hanya karena menemukan nilai secara efisien tetapi karena ia menemukan indeks bahkan dalam kasus kehilangan seperti yang ditunjukkan Theodor - yang memungkinkan akses cepat ke misalnya array. Namun dalam kasus pohon, indeks integer mungkin bukan cara yang efisien untuk mengakses struktur; C ++ memecahkan ini melalui penggunaan objek iterator (walaupun dengan kompleksitasnya sendiri).
J Trana