Apakah memori semua permutasi yang mungkin dari blok dan pointer kilobyte mungkin?

23

Ini adalah ide yang cukup sulit untuk membungkus kepala saya dan saya akan sangat menghargai suntingan / bantuan untuk membuatnya lebih mudah dibaca bagi mereka yang tahu.

Apakah secara teoritis mungkin untuk memiliki hard drive yang telah disimpan di dalamnya satu salinan dari setiap kemungkinan permutasi biner satu kilobyte dan kemudian memiliki sisa sistem hanya membuat pointer ke lokasi ini?

Apakah sistem yang dibuat sedemikian rupa bisa lebih cepat daripada sekadar menyimpan informasi secara langsung?

Untuk menjelaskan cara lain, katakanlah alih-alih memiliki kalimat:

"Halo, saya Bob." dan "Sandwich itu terlihat lezat."

... disimpan di hard drive, kami akan memiliki semua permutasi alfabet dan karakter lainnya hingga beberapa nomor (katakanlah, 1000 karakter atau lebih), dan kemudian simpan kalimat-kalimat kami seperti:

[Pointer # 21381723]

theory pointers storage information-theory Amagii Discordus Penndragon
sumber
21
Anda mungkin ingin mempertimbangkan Berapa banyak tweet bahasa Inggris unik yang mungkin? Berapa lama bagi populasi dunia untuk membacanya dengan lantang? . Anda berurusan dengan angka yang sangat besar.
Anda mungkin tertarik dengan cara git bekerja, yang disebut content addressable .
JDługosz
5
github.com/philipl/pifs didasarkan pada prinsip yang sama dengan ide Anda, kecuali alih-alih memiliki semua permutasi kb, ia menggunakan pi.
Waxen
12
Pointer Anda harus sepanjang 1 kilobyte. Anda dapat memilih untuk tidak menyimpan blok yang tidak masuk akal dalam bahasa Inggris - dalam hal ini Anda telah secara mandiri menemukan kembali ide kompresi!
user253751
Jawaban dasar adalah TIDAK - tidak mungkin karena # dan ukuran permutasi Tapi aplikasi apa yang Anda pikir akan berguna untuk jika mungkin ??
Archangel

Jawaban:

91

Ada 2 8192 kemungkinan blok 1K berbeda. Menyimpan mereka semua akan membutuhkan 2 8202 bit penyimpanan. Karena alam semesta hanya mengandung sekitar 10 80 (atau ~ 266 ) partikel, itu adalah taruhan yang aman bahwa tidak mungkin untuk menyimpan semuanya, dan Anda tidak perlu bertanya-tanya apakah itu akan menghemat waktu atau tidak.

Namun, sebenarnya ada cara yang lebih menarik untuk menjawab ini. Anda menyarankan untuk membuat indeks ke dalam kumpulan konstanta yang sangat besar. Tapi bagaimana Anda tahu indeks mana yang harus dereferensi? Bayangkan demi argumen bahwa Anda ingin menyimpan hanya 1 karakter blok: a, b, c... Agaknya indeks Anda akan menjadi 0, 1, 2 dll, karena itulah tata letak yang paling efisien untuk menyimpan blok-blok.

Apakah Anda memperhatikan sesuatu tentang pengaturannya? Indeks Anda, pada kenyataannya, adalah representasi kode dari data yang disimpan ! Dengan kata lain, Anda tidak perlu melakukan dereferensi sama sekali, Anda hanya perlu mengubah indeks menjadi data yang Anda inginkan.

Ketika Anda menyimpan semua nilai yang mungkin dari sesuatu dalam sebuah tabel, ini selalu terjadi: indeks Anda menjadi hanya versi yang disandikan dari data itu sendiri, jadi menyimpan data menjadi tidak perlu sejak awal. Ini mengapa di dunia nyata, indeks hanya berguna untuk data jarang (misalnya semua halaman web yang dikunjungi, tidak semua halaman web yang bisa ada , atau bahkan semua yang melakukan eksis).

Kilian Foth
sumber
17
Jadi, dalam satu hal, kita sudah menggunakan sistem ini - tetapi kita melakukannya dengan evaluasi malas dari pola bit berukuran kilobyte, yang memungkinkan kita menghemat banyak ruang penyimpanan!
Theodoros Chatzigiannakis
3
Penyimpanan sedikit berkurang, karena tumpang tindih (1024 nol diikuti oleh 1024 yang berisi 1025 pola unik) ... berkurang tetapi masih sangat besar. Juga, blok 1KB adalah 2 <sup> 13 </sup> bit, bukan 2 <sup> 10 </sup>.
Ben Voigt
2
Perhatikan bahwa batas 10 ^ 80 pada partikel di alam semesta tidak secara langsung berarti Anda tidak dapat menyimpan lebih dari, katakanlah, 10 ^ 80 bit di alam semesta - karena dengan setiap partikel Anda berpotensi menyimpan lebih dari satu bit informasi ( berdasarkan posisinya di dalam alam semesta, dan mungkin kecepatannya dll). Itu tidak berarti Anda dapat menyimpan setiap blok 1K - jumlah yang melebihi jumlah partikel dengan faktor yang sangat besar, jadi itu masih taruhan yang sangat aman Anda tidak dapat menyimpan semuanya!
psmears
2
@ Neil Jika Anda memiliki sistem pengkodean yang memungkinkan Anda untuk menyimpan 10 ^ 80 dengan mengkodekannya sebagai "10 ^ 80" lalu bagaimana Anda menyimpan "10 ^ 80"? Jika beberapa bagian data dikodekan lebih pendek dari data aktual, yang lain harus dikodekan lebih lama. Atau jika semua data Anda berupa angka, maka Anda menyimpan setiap angka desimal sebagai satu byte penuh.
Random832
3
Dengan urutan de Bruijn 2 ^ 1024 bit sudah cukup.
gronostaj
20

Seperti yang telah ditunjukkan orang lain, Anda memiliki 2 ^ 8192 kemungkinan untuk blok 1k. Ini berarti Anda akan membutuhkan 8192 bit untuk menyandikan alamat blok jika semua alamat blok dikodekan dengan jumlah bit yang sama, sehingga alamat Anda akan panjang 1k. Anda tidak akan mendapatkan apa pun kecuali menambahkan lapisan tipuan sehingga Anda tidak akan mendapatkan kinerja apa pun.

Jika Anda ingin memiliki alamat yang lebih pendek, Anda harus menyandikan beberapa blok dengan alamat pendek dan beberapa dengan yang lebih panjang dan membuatnya sehingga yang lama tidak sering muncul, dan Anda sekarang cukup mengompresi data (mungkin dengan sesuatu seperti a Huffman code ). Itu akan membutuhkan pengetahuan tentang data yang Anda simpan sebelum menyimpannya atau perubahan reguler dalam pengkodean. Mungkin juga kurang efisien daripada algoritma kompresi lain yang menggunakan blok dengan panjang yang berbeda-beda.

pengguna2313067
sumber
1

Ada dua masalah dengan itu.

Pertama, "semua kemungkinan permutasi biner satu kilobyte" adalah sejumlah besar data. 1024 byte * 8 bit per byte = 8192 bit dalam satu kilobyte. Semua permutasi yang memungkinkan adalah 2 ^ 8192. Itu sekitar 1.09e+2466kilobyte! (Untuk tujuan perbandingan, drive 1 TB adalah 1e09kilobyte.)

Kedua, bahkan jika Anda memiliki tabel yang sangat besar, dan Anda mengindeksnya dengan pointer, apa yang akan Anda lakukan jika Anda ingin referensi beberapa data yang lebih kecil dari tepat 1 KB?

Mason Wheeler
sumber
2
Menyimpan semua blok yang lebih kecil dari 1 KB juga tidak akan memakan banyak ruang. Dengan asumsi hanya blok ukuran byte, ukuran blok kecil bersama-sama hanya sedikit lebih dari 1/256 dari ukuran blok 1-KB. Dengan asumsi blok berukuran kecil, Anda menambahkan tentang ukuran yang sama lagi.
Paŭlo Ebermann
-1

Seperti yang ditunjukkan poster lain, pada suatu titik, ukuran pointer yang diperlukan untuk mengindeks ke dalam daftar Anda dari semua nilai yang mungkin membatalkan keuntungan Anda.

Namun, beberapa bahasa menggunakan versi terbatas dari apa yang Anda sarankan untuk mengoptimalkan penggunaan memori. Python menggunakan string 'magang' untuk mengurangi jumlah string duplikat dalam memori. Anda dapat menemukan informasi lebih lanjut dengan mencari 'python string intern'.

JS.
sumber
1
OP bertanya tentang set yang padat, yang berisi setiap permutasi. Pointer hanya berguna untuk data yang jarang, di mana bit yang diperlukan untuk memegang pointer lebih kecil dari bit yang diarahkan. Interning dapat membuat ruang lebih jarang jika ada duplikat, jadi ada koneksi di sana, tetapi jawaban Anda tidak benar-benar mengucapkannya dengan baik.
Peter Cordes