Struktur data apa yang harus saya gunakan untuk strategi caching ini?

Saya bekerja pada aplikasi .NET 4.0, yang melakukan perhitungan agak mahal pada dua ganda mengembalikan ganda. Perhitungan ini dilakukan untuk masing-masing dari beberapa ribu item . Perhitungan ini dilakukan di Taskatas threadpool thread.

Beberapa tes awal telah menunjukkan bahwa perhitungan yang sama dilakukan berulang-ulang, jadi saya ingin ke cache n hasil. Ketika cache penuh, saya ingin membuang item yang paling jarang digunakan. ( Sunting: Saya menyadari paling tidak sering tidak masuk akal, karena ketika cache sudah penuh dan saya akan mengganti hasil dengan yang baru dihitung, yang satu akan paling jarang digunakan dan segera diganti saat berikutnya hasil baru dihitung dan ditambahkan ke cache)

Untuk mengimplementasikan ini, saya berpikir untuk menggunakan Dictionary<Input, double>(di mana Inputakan menjadi kelas mini yang menyimpan dua nilai ganda input) untuk menyimpan input dan hasil yang di-cache. Namun, saya juga perlu melacak kapan suatu hasil digunakan terakhir kali. Untuk ini saya pikir saya akan memerlukan koleksi kedua menyimpan informasi yang saya perlukan untuk menghapus hasil dari kamus ketika cache sudah penuh. Saya khawatir bahwa terus-menerus menjaga daftar ini diurutkan akan berdampak negatif pada kinerja.

Apakah ada cara yang lebih baik (yaitu lebih banyak pemain) untuk melakukan ini, atau mungkin bahkan struktur data umum yang tidak saya sadari? Jenis hal apa yang harus saya profil / ukur untuk menentukan optimalitas solusi saya?

Jika Anda ingin menggunakan cache penggusuran LRU (Penggusuran yang Terakhir Digunakan), maka kemungkinan kombinasi struktur data yang baik untuk digunakan adalah:

• Daftar tertaut melingkar (sebagai antrian prioritas)
• Kamus

Ini sebabnya:

• Daftar tertaut memiliki waktu penyisipan dan penghapusan O (1)
• Daftar node dapat digunakan kembali ketika daftar penuh dan tidak ada alokasi tambahan yang perlu dilakukan.

Beginilah algoritma dasar seharusnya bekerja:

Struktur data

LinkedList<Node<KeyValuePair<Input,Double>>> list; Dictionary<Input,Node<KeyValuePair<Input,Double>>> dict;

1. Input diterima
2. Jika kamus berisi kunci
   • mengembalikan nilai yang disimpan dalam node dan memindahkan node ke awal daftar
3. Jika kamus tidak mengandung kunci
   • hitung nilainya
   • menyimpan nilai di simpul terakhir dari daftar
   • jika yang terakhir tidak memiliki nilai, hapus kunci sebelumnya dari kamus
   • pindahkan simpul terakhir ke posisi pertama.
   • simpan dalam kamus pasangan nilai kunci (input, simpul).

Beberapa manfaat dari pendekatan ini adalah, membaca dan mengatur nilai kamus mendekati O (1), menyisipkan dan menghapus simpul dalam daftar tertaut adalah O (1), yang berarti algoritma mendekati O (1) untuk membaca dan menulis nilai-nilai ke cache, dan menghindari alokasi memori dan memblokir operasi penyalinan memori, menjadikannya stabil dari sudut pandang memori.

Ini seperti banyak upaya yang harus dilakukan untuk perhitungan tunggal mengingat kekuatan pemrosesan yang Anda miliki di PC rata-rata. Selain itu, Anda masih akan dikenakan biaya panggilan pertama ke perhitungan Anda untuk setiap pasangan nilai unik, jadi 100.000 pasangan nilai unik masih akan membebani Anda Waktu _n * 100.000 minimal. Pertimbangkan bahwa mengakses nilai dalam kamus Anda kemungkinan akan menjadi lebih lambat saat kamus semakin besar. Bisakah Anda menjamin kecepatan akses kamus Anda akan memberikan kompensasi yang cukup untuk memberikan pengembalian yang masuk akal terhadap kecepatan perhitungan Anda?

Apapun itu, sepertinya Anda mungkin perlu mempertimbangkan untuk mencari cara untuk mengoptimalkan algoritma Anda. Untuk ini, Anda akan memerlukan alat profil, seperti Redgate Ants untuk melihat di mana bottleneck berada, dan untuk membantu Anda menentukan apakah ada cara untuk mengurangi beberapa overhead yang mungkin Anda miliki terkait dengan instance kelas, traverse daftar, database mengakses, atau apa pun yang menghabiskan banyak waktu.

Satu pemikiran mengapa hanya cache n hasil? Bahkan jika n adalah 300.000, Anda hanya akan menggunakan memori 7.2MB (plus tambahan apa pun untuk struktur tabel). Itu mengasumsikan tiga ganda 64 bit tentu saja. Anda bisa menerapkan memoisasi ke rutin perhitungan rumit itu sendiri jika Anda tidak khawatir kehabisan ruang memori.

Pendekatan dengan koleksi kedua baik-baik saja. Ini harus merupakan antrian prioritas yang memungkinkan menemukan / menghapus nilai min dengan cepat dan juga mengubah (meningkatkan) prioritas dalam antrian (bagian terakhir adalah yang sulit, tidak didukung oleh sebagian besar implementasi antrian prio sederhana). The perpustakaan C5 memiliki koleksi tersebut, hal itu disebut IntervalHeap.

Atau tentu saja, Anda dapat mencoba membangun koleksi Anda sendiri, sesuatu seperti a SortedDictionary<int, List<InputCount>>. ( InputCountharus kelas yang menggabungkan Inputdata Anda dengan Countnilai Anda )

Memperbarui koleksi itu saat mengubah nilai hitungan Anda dapat diterapkan dengan menghapus dan memasukkan kembali elemen.

Sebagaimana ditunjukkan dalam jawaban Peter Smith, pola yang Anda coba terapkan disebut memoisasi . Di C # cukup sulit untuk menerapkan memoisasi secara transparan tanpa efek samping. Buku Oliver Sturm dalam pemrograman fungsional dalam C # memberikan solusi (kode tersedia untuk diunduh, bab 10).

Dalam F # itu akan jauh lebih mudah. Tentu saja, ini adalah keputusan besar untuk mulai menggunakan bahasa pemrograman lain, tetapi mungkin perlu dipertimbangkan. Khususnya dalam perhitungan yang rumit, pasti akan membuat lebih banyak hal lebih mudah diprogram daripada memoisasi.