Baru-baru ini, di salah satu proyek, muncul masalah: ada sekumpulan set, yang harus disimpan secara efisien dalam RAM. Karena ada banyak set, tapi sedikit memori. Dan kita harus melakukan sesuatu.
Karena bahasa di mana semua ini ditulis adalah C #, yaitu nuansa. Yakni, HashSet <int> standar menghabiskan 16 byte untuk menyimpan satu nomor, faktor phill juga mempengaruhi. Ada implementasi yang lebih efisien (saya akan menulis tentang mereka suatu hari nanti), tetapi di sisi lain, Anda dapat dengan bodoh menyimpan dalam array, 4 byte per nomor (Anda perlu menyimpan int), yang cukup efisien. Tetapi bisakah itu dikurangi lebih lanjut?
Saya harus segera mengatakan bahwa saya tidak punya jawaban tentang cara terbaik untuk melakukannya, mungkin tidak ada, karena ada banyak faktor yang terkait dengan distribusi data tertentu. Tapi ada ide yang akan saya bagikan: opsi apa yang ada untuk menghemat memori. Saya juga menyarankan agar Anda berpikir sendiri sebelum membaca posting, ini masih pemanasan yang baik untuk pikiran. Untuk lebih spesifik, saya akan merumuskan masalah sebagai berikut:
Ada satu set ints unik non-negatif (32 bit). Diperlukan untuk menyimpannya secara efisien dalam RAM, dari operasi - membuat satu set dan mendapatkan semua elemen. Tidak perlu mendapatkan item dengan indeks, menambah yang baru atau menghapusnya.
Artikel itu akan berisi banyak huruf dan angka dan tidak ada satu gambar pun (kecuali kucing yang dikemas di KDPV).
, , .. , . . - , - , . - , - .
, — , .
, : , . 10
Jadi, kami memiliki data dasar - array int, 4 byte (32 bit) per nomor. Kami akan membangun indikator ini.
Untuk memulainya, saya akan mengungkapkan ide cemerlang: agar sebuah angka menempati memori kurang dari 32 bit, Anda harus menyimpannya menggunakan bit yang lebih sedikit. Ide keren, ya? Dan orang mendapatkan ketenaran dan pengakuan untuk ini. Jadi semakin buruk saya.
Penyimpangan lirik: beberapa tahun yang lalu, spesialis Perkeretaapian Rusia menemukan bahwa jika Anda membuat roda bulat dan berukuran sama, maka kereta akan melaju lebih cepat dan lebih tenang.
Memisahkan angka berdasarkan ukuran
Solusi sederhana untuk memulai: Angka dari 0 hingga 255 dapat disimpan menggunakan 1 byte per angka, hingga 65536 dengan dua, hingga 16777216 dengan tiga. Oleh karena itu solusi pertama:
Kami membuat 4 array, di satu kami menyimpan angka dengan 1 byte, di lainnya dengan 2, di ketiga dengan 3, dan yang keempat, saya usulkan untuk menebaknya sendiri.
Tepuk tangan, dan kami sudah menabung. Tapi mengapa tetap di tempat Anda dulu? Mari gunakan 32 array! Dan menyimpan nomor dengan 1, 2 ... bit. Ini menjadi lebih ekonomis.
Di sisi lain, apa itu array? Ini adalah penunjuk ke blok memori (8 byte), panjang dan untuk C # juga memori untuk objek array itu sendiri (20 byte). Secara total, setiap array berharga 32 byte (sebenarnya, dalam C #, sebuah objek mengambil setidaknya 24 byte dengan kelipatan 8, di mana 20 byte untuk objek, dan 4 untuk apa yang tersisa atau bodoh untuk penyelarasan). Selanjutnya, perhitungan untuk sistem 64-bit. Untuk 32 bit, pointer 2 kali lebih sedikit, keselarasan juga 4, jadi hampir semuanya 2 kali lebih ekonomis.
Untuk apa bagian ini? Selain itu, 32 array akan memakan 1KB memori hanya untuk dirinya sendiri. Apa yang harus dilakukan tentang hal itu? Dan semuanya sederhana: kami akan menyimpan 32 array ini dalam satu array!
Di elemen pertama kita menyimpan panjang array satu-bit, lalu array itu sendiri, lalu panjang untuk dua bit, dll. Hasilnya, hanya ada overhead 32 byte dan penyimpanan yang efisien.
Seorang pembaca yang ingin tahu (saya selalu menyukai frase ini) mungkin memperhatikan masalah tertentu: untuk menyimpan nomor dari satu bit, pertama-tama kita menghabiskan 2 bit untuk panjangnya (0, 1 atau 2), dan kemudian 2 bit untuk nomor itu sendiri. Tetapi Anda hanya dapat menggunakan 2 bit: bit pertama - apakah ada 0, yang kedua - apakah ada 1.
Kami baru saja membuat bitmap . Anda tidak perlu terlalu khawatir dan menyimpan angka dari 0 hingga 255 dengan metode ini - ada angka - 1, tidak - 0. Dan menghabiskan 32 byte di atasnya (8 bit dalam satu byte * 32 = 256). Secara alami, dengan setiap nilai baru, efektivitas kartu mulai menurun. Itu. untuk menyimpan semua int kita membutuhkan 536870912 byte ... Ini terlalu banyak. Jadi kapan harus berhenti: pada 256, pada 16, pada 65536 - tergantung pada data. Biarlah 256. Saya suka nomor ini, indah.
Itu. kami menyimpan 256 angka pertama dengan bitmap, kemudian kami menyimpan panjang angka dengan panjang tertentu dalam bit dan angka itu sendiri.
Tapi lihat apa yang terjadi: angka dari 0 sampai 511 membutuhkan 9 bit untuk disimpan. Pada saat yang sama, kami adalah angka dari 0 hingga 255 - kami telah menyimpannya. Itu. dalam kisaran 9 bit angka 12 tidak dapat ditemukan.Hanya 256 dan lebih. Jadi mengapa menyimpannya dalam 9 bit, jika Anda dapat menyimpan angka dari 0 hingga 255 dan kemudian menambahkan 256 yang hilang di kepala Anda. Simpan satu bit lagi! Secara alami, setiap rentang berikutnya juga akan 1 bit lebih ekonomis. Kita hebat!
Apa lagi yang bisa kamu lakukan? Dan Anda bisa melihat datanya. Jika mereka sangat padat (1,2,3,5,6), maka Anda tidak dapat menyimpan nomor itu sendiri, tetapi yang tidak ada (4). Itu. alih-alih menyimpan 5 angka bersyarat, kami akan menyimpannya. Aturan sederhana: kami memiliki lebih dari setengah - kami menyimpan yang tidak ada, sebaliknya sebaliknya. Di mana menyimpannya? Dan panjangnya! Lihat: untuk menyimpan angka sepanjang 10 bit, kita membutuhkan 11 bit (karena dari 0 hingga 1024, inklusif). Tetapi pada saat yang sama, nilai dalam 11 bit dapat didorong pada tahun 2048, dan kami hanya menggunakan 1025. Jadi kami akan menyimpan: panjang positif - kami menyimpan angka. Negatif - kami menyimpan apa yang tidak. Saya menyarankan agar pembaca membuat sendiri perhitungan rinci sebagai latihan independen (karena saya tidak yakin semuanya akan cocok, jadi saya akan berpura-pura bahwa itu perlu).
Hasilnya, kami mendapatkan: array di mana 16 byte pertama adalah topeng bit untuk keberadaan angka dari 0 hingga 255, lalu - panjang dengan indikasi - kami menyimpan angka atau ketidakhadirannya, angka itu sendiri, panjang bit untuk selanjutnya, dll.
Setelah Anda menerapkan ini, dan bahkan tanpa kesalahan, saya pikir Anda akan langsung menuju ke durke, programmer berikutnya yang mencoba memahami kode ini akan mengikuti Anda. Jadi mari kita coba beberapa opsi lagi.
Kami memikirkan ketertiban
Lihat. Kami memiliki array. Apa yang dia miliki, sebagai lawan banyak? Dan dia memiliki: urutan elemen. Ini adalah informasi tambahan, dan kami belum menggunakannya. Apa yang dapat Anda lakukan?
Dan Anda tidak dapat menyimpan elemen itu sendiri, tetapi perbedaan di antara mereka:
1,2,3,4,8 => 1,1,1,1,4
Ie. kami menyimpan yang pertama apa adanya, yang kedua - kami menambahkan nilai yang pertama ke yang kedua, dll. Apa yang diberikannya kepada kita? Dan fakta bahwa jika kita mengurutkan array terlebih dahulu , maka nilai kita di dalamnya akan menjadi lebih kecil secara umum, dan dapat disimpan dalam bit yang lebih sedikit.
Selain itu, menurut kondisi masalah, semua elemen berbeda-beda, yaitu. kita masih bisa mengurangi satu dari perbedaan untuk menyimpan bit:
1,2,3,4,8 => 1,1,1,1,4 => 1,0,0,0,3
Ini tidak sulit, jadi mengapa dan tidak.
Tapi sekarang masalahnya sudah teratasi. Karena Sekarang kita tidak dapat menyimpan angka secara mandiri, tetapi hanya dalam urutan yang sama, maka metode dengan larik dan panjang tidak lagi sesuai. Anda harus memikirkan sesuatu yang lain, karena semua nomor harus disimpan secara berurutan.
Simpan panjang angka dalam bit sebelum angka itu sendiri.
Bukan pilihan yang buruk. Jumlahnya mulai dari 1 hingga 32 bit, mis. untuk panjangnya kita butuh 5 bit, lalu nomornya sendiri. Untuk kenyamanan, Anda dapat memotong kasus ekstrem (ya, mengapa kita akan menabung di sana? Pennies!), Atau sebaliknya, sorot secara terpisah - misalnya, jika panjangnya 0, maka itu berarti angka 0, jika panjangnya 1 - angka - 1, jika panjangnya 2, lalu 2 berikutnya bit number 2,3,4,5 (kita sudah tahu bahwa kita bisa beralih ke sesuatu yang tidak bisa), dll.
Atau dapatkah menyimpan panjang sebuah angka dalam bilangan itu sendiri?
Kuantitas panjang variabel
Tidak peduli bagaimana kami yang pertama mengajukan pertanyaan ini, jadi ada solusi standar. Digunakan untuk menyimpan string di UTF-8 dan banyak tempat lainnya. Artinya sederhana.
Jika angkanya dari 0 hingga 127 inklusif, kami menyimpannya dalam 1 byte (meskipun kami hanya menggunakan 7 bit). Jika lebih, maka atur bit ke-8 menjadi 1 dan gunakan byte berikutnya dengan cara yang sama (7 bit, hilang - kotak centang dan berikutnya). Itu. angka-angka kecil akan disimpan dalam satu byte, sedikit lagi - dalam dua, dan seterusnya hingga 5.
Anda dapat mengatakan - fuu ... kami hanya bermain dengan bit, dan kemudian byte pergi, tidak keren! Ya, itu tidak keren, di sisi lain, bekerja dengan byte masih lebih mudah daripada dengan bit, sedikit penghematan, tetapi kecepatan kerja lebih tinggi dan kodenya lebih jelas. Tapi ... menghabiskan sedikit per byte entah bagaimana tidak terlalu keren, mungkin ada solusi yang lebih baik?
Menggunakan nilai sebagai bendera
Mari lewati semua alasan dan segera putuskan. Kami akan menyimpannya sebagai berikut:
- angka dari 0 hingga 252 akan disimpan dalam satu byte. Jika lebih, maka:
- jika angkanya dari 252 ke 252 + 256 = 508 kita atur nilainya 252, dan di byte berikutnya angkanya adalah 252 (ya, kita sudah tahu cara menggeser nilai)
- jika dari 252 + 256 hingga 252 + 256 + 65536, setel 253 dan gunakan 2 byte berikutnya untuk menyimpan nomor itu sendiri - perbedaan yang tidak perlu
- jika dari 252 + 256 + 65536 hingga 252 + 256 + 65536 + 16777216, masukkan 254 dan 3 byte
- sebaliknya - 255 dan 4 byte.
Apakah ini cara yang baik? Semuanya relatif. Dalam satu byte kita dapat mendorong nilai hingga 252, sedangkan di VLQ hanya hingga 127, tetapi hanya 508 dalam 2 byte, dan sudah 16383 di VLQ. Metode ini bagus jika nomor Anda cukup padat, dan di sini kita akan menang. Tetapi hal yang baik tentang metode ini adalah dapat disesuaikan dengan rentang yang berbeda. Misalnya, jika kita mengetahui bahwa sebagian besar angka adalah dari 10.000 hingga 50.000, maka kita selalu dapat menyimpannya dalam dua byte, tetapi jika beberapa angka besar keluar, kita akan menulis 65535 dan sudah menggunakan 4. Faktanya, kami mengoptimalkan penyimpanan kisaran yang diperlukan dengan biaya penyimpanan yang tidak efisien tidak perlu.
Kesimpulan
Kami memeriksa cara-cara utama untuk menghemat memori (sebenarnya, imajinasi saya telah habis, tetapi saya tidak mau mengakuinya). Teknik-teknik ini dapat digabungkan, digunakan untuk tugas-tugas lain, dan dimodifikasi agar sesuai dengan situasi. Apa teknik terbaik pada akhirnya? Itu semua tergantung pada data Anda. Ambil dan cobalah. Untungnya, tidak perlu mengimplementasikan semuanya sekaligus. Cukup mudah untuk menulis kode yang hanya akan mengevaluasi panjangnya. Dan setelah penilaian, sudah terapkan apa yang Anda suka.
Jangan lupa tentang kecepatan semua ini: apakah Anda siap menghabiskan banyak waktu menyiapkan data atau mendapatkannya. Apakah layak memulai perkelahian dengan bit, atau tidakkah seharusnya Anda pergi di bawah byte. Apakah cukup untuk mengoptimalkan situasi yang sering terjadi, meninggalkan situasi langka dengan implementasi yang tidak efektif. Apakah mungkin, tergantung pada datanya, untuk menggunakan metode penyimpanan yang berbeda (misalnya, adalah bodoh untuk menyimpan hingga 8 byte dalam array, karena biaya samping akan melahap semua keuntungan, dan dari 1 byte - umumnya disimpan dalam array pseudo dari satu elemen, yaitu di jumlah).
Juga, beberapa kata tentang kompresi: ini tidak akan terlalu efektif. Algoritme kompresi sangat menyukai pengulangan, tetapi tidak terlalu banyak di sini. Jika Anda menggunakan Zip bersyarat, yang terdiri dari LZ77 + Huffman, kecil kemungkinannya sesuatu yang berguna akan keluar dengan LZ77, tetapi Huffman mungkin mencoba menghemat byte. Jadi Zip akan menjadi setengah tidak berguna. Tapi kecepatannya akan turun sangat, sangat banyak.
Situasi di mana kita tahu bahwa kita memiliki banyak set dan kita dapat menyimpan semuanya menggunakan irisan yang berbeda belum dipertimbangkan sama sekali. Di sini saya akui - saya tidak yakin itu akan berhasil. Segera, saya tidak menemukan pilihan. Tetapi saya menyadari bahwa itu akan sulit. Namun, Anda mungkin berbeda pendapat.
Jadi bagikan ide Anda di komentar, mungkin saya melewatkan beberapa gajah yang jelas yang akan menghemat lebih banyak byte dan mendapatkan hasil sedemikian rupa sehingga ibu rumah tangga dari iklan deterjen (yang cukup untuk satu tetes) akan iri pada kita semua!