Skema yang baik untuk mewakili bilangan bulat dari 0 hingga tak terbatas, dengan asumsi Anda memiliki penyimpanan biner linear tak terbatas?

10

Saya ingin skema untuk mewakili angka integer yang dimulai dengan 0, tanpa batas (dengan asumsi akses ke penyimpanan linier tak terbatas).

Berikut skema yang dapat mewakili angka dari 0 hingga 255:

Gunakan byte pertama dari penyimpanan (alamat 0) untuk menyimpan integer.

Sekarang, misalkan saya ingin mewakili angka yang lebih besar dari 255. Tentu saja, saya bisa menggunakan lebih dari 1 byte untuk mewakili integer, tetapi selama itu adalah angka tetap, pada akhirnya akan ada integer yang begitu besar sehingga tidak dapat diwakili oleh skema asli.

Berikut skema lain yang harus dapat melakukan tugas, tetapi mungkin jauh dari efisien.

Cukup gunakan semacam byte "end of number" yang unik, dan gunakan semua byte sebelumnya untuk mewakili nomor tersebut. Jelas, byte "akhir angka" ini tidak dapat digunakan di mana saja dalam representasi angka, tetapi ini dapat dicapai dengan menggunakan sistem penomoran basis-255 (bukan basis-256).

Namun, itu lambat dan mungkin tidak efisien. Saya ingin memiliki yang lebih baik yang berkinerja lebih baik dengan nilai dan skala rendah dengan baik.

Pada dasarnya, ini adalah sistem UUID. Saya ingin melihat apakah mungkin untuk membuat sistem UUID yang berkinerja cepat yang dapat secara teoritis skala untuk digunakan selama bertahun-tahun, ribuan tahun, jutaan tahun, tanpa harus dirancang ulang.

storage numbers uuid Dmitri Shuralyov
sumber
1
Apakah Anda menginginkan sesuatu yang dapat menskala tanpa batas (seperti pada pembukaan Anda), atau selama jutaan tahun (seperti pada penutupan Anda)? Kedua persyaratan (jelas) sangat berbeda. Dua pelengkap pada mesin 64-bit akan berskala selama jutaan tahun.
user16764
1
@ user16764, maksud Anda variabel integer 64-bit tunggal? Itu tentu tidak akan berhasil: jika 6 juta orang mengkonsumsi 1 juta UUID per detik, itu tidak akan bertahan lebih dari sebulan.
Dmitri Shuralyov
1
Dan berapa lama waktu yang dibutuhkan mesin 128-bit?
user16764
2
Ide-ide dalam RFC 2550 , yang menyediakan representasi ASCII lexicographical-memerintahkan untuk bilangan bulat positif besar sewenang-wenang, dapat disesuaikan dengan ini. Pada akhirnya memecah menjadi segmen unary yang mengkodekan panjang segmen basis-26 yang mengkodekan panjang segmen basis-10 - dua basis yang terakhir lebih berkaitan dengan representasi ASCII daripada apa pun yang fundamental untuk skema.
Random832
1
Dengan asumsi Anda menghasilkan angka 128 bit secara berurutan: jika kita meningkatkan kapasitas komputasi semua komputer dengan memberikan setiap manusia komputer-petaflop, maka akan diperlukan 9 juta tahun sebelum angka-angka ini habis. Jika di sisi lain setiap manusia secara acak menghasilkan 600 juta angka 128 bit, ada kemungkinan 50% mereka menghasilkan 1 duplikat. Apakah itu cukup baik untukmu? ( en.wikipedia.org/wiki/Universally_unique_identifier ) Jika tidak, menggunakan 256 bit mengalikan kedua angka ini dengan 2 ^ 128 = 3,4 * 10 ^ 38, yang lebih dari kuadrat usia alam semesta dalam hitungan detik.
Alex ten Brink

Jawaban:

13

Suatu pendekatan yang saya gunakan: hitung jumlah bit terdepan 1, katakanlah n. Ukuran angka kemudian 2 ^ n byte (termasuk 1 bit terkemuka). Ambil bit setelah 0 bit pertama sebagai integer, dan tambahkan nilai maksimum (plus satu) yang dapat diwakili oleh angka menggunakan pengkodean ini dalam 2 ^ (n-1) byte.

Jadi, 

                  0 = 0b00000000
                   ...
                127 = 0b01111111
                128 = 0b1000000000000000
                   ...
              16511 = 0b1011111111111111
              16512 = 0b11000000000000000000000000000000
                   ...
          536887423 = 0b11011111111111111111111111111111
          536887424 = 0b1110000000000000000000000000000000000000000000000000000000000000
                   ...
1152921505143734399 = 0b1110111111111111111111111111111111111111111111111111111111111111
1152921505143734400 = 0b111100000000000000000000000000000000000000000000 ...

Skema ini memungkinkan nilai non-negatif diwakili dengan tepat dalam satu cara.

(Setara, digunakan jumlah 0 bit terkemuka.)

retracile
sumber
1
Sulit bagi saya untuk mencari tahu jawaban mana yang diterima, karena saya pikir banyak dari mereka sangat informatif dan baik. Tapi saya pikir yang ini paling cocok untuk pertanyaan yang saya ajukan (mungkin bukan yang mendasar yang ada dalam pikiran saya, yang lebih sulit untuk diungkapkan).
Dmitri Shuralyov
2
Saya menulis artikel yang lebih mendalam dengan contoh implementasi dan pertimbangan desain.
retracile
10

Ada banyak teori yang didasarkan pada apa yang Anda coba lakukan. Lihatlah halaman wiki tentang kode universal - ada daftar lengkap metode pengkodean bilangan bulat (beberapa di antaranya sebenarnya digunakan dalam praktik).

Dalam kompresi data, kode universal untuk bilangan bulat adalah kode awalan yang memetakan bilangan bulat positif ke codeword biner

Atau Anda bisa menggunakan 8 byte pertama untuk menyimpan panjang angka dalam beberapa unit (kemungkinan besar byte) dan kemudian meletakkan byte data. Akan sangat mudah diimplementasikan, tetapi agak tidak efisien untuk jumlah kecil. Dan Anda akan dapat membuat kode integer cukup lama untuk mengisi semua drive data yang tersedia untuk umat manusia :)

Matěj Zábský
sumber
Terima kasih untuk itu, itu sangat menarik. Saya ingin menandai ini sebagai jawaban yang diterima, tetapi mengambil tempat ke-2. Ini adalah jawaban yang sangat bagus dari sudut pandang teoritis, IMO.
Dmitri Shuralyov
4

Bagaimana kalau jumlah angka 1 di depan ditambah angka 0 pertama menjadi ukuran (sizeSize) dari ukuran angka (numSize) dalam bit. NumSize adalah angka biner yang memberikan ukuran representasi angka dalam byte termasuk bit ukuran. Bit yang tersisa adalah angka (num) dalam biner. Untuk skema bilangan bulat positif, berikut adalah beberapa contoh nomor contoh:

Number              sizeSize  numSize    num
63:                 0 (1)     1 (1)      111111
1048575:            10 (2)    11 (3)     1111 11111111 11111111
1125899906842623:   110 (3)   111 (7)    11 11111111 11111111 11111111 11111111 11111111 11111111
5.19.. e+33:        1110 (4)  1111 (15)  11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
Briguy37
sumber
4

Bagaimana dengan itu: Satu byte untuk panjang, kemudian n byte untuk nomor (byte paling signifikan pertama). Ulangi panjang + angka selama panjang sebelumnya 255.

Ini memungkinkan untuk jumlah besar yang sewenang-wenang, tetapi masih mudah ditangani dan tidak menghabiskan terlalu banyak memori.

pengguna281377
sumber
fNek: Tidak ada batas atas. Misalnya, jika Anda memerlukan 513 byte untuk nomor tersebut, urutan byte adalah [255, b0, ..., b255.255, b256, ..., b511,2, b512, b513]
user281377
Maaf. Harus belajar membaca lebih cermat.
fNek
3

Mengapa tidak menggunakan 7 bit saja dari setiap byte, dan menggunakan bit ke-8 untuk menunjukkan apakah ada byte lain yang harus diikuti? Jadi 1-127 akan berada dalam satu byte, 128 akan diwakili oleh 0x80 0x01, dll.

Paul Tomblin
sumber
1
Skema ini mengkodekan hanya 128 nilai dalam setiap 8 bit, yang sebenarnya kurang efisien ruang daripada skema pengkodean kedua yang diajukan oleh penanya, di mana 255 nilai dikodekan dalam setiap 8 bit. Kedua skema menderita dari kenyataan bahwa Anda perlu membaca di seluruh nomor untuk mengetahui berapa banyak penyimpanan yang Anda butuhkan untuk menyimpannya.
Mark Booth
3
Jadi, Anda perlu memindai nomor itu dua kali untuk membuat salinannya, jadi apa? Jika saya bisa menunggu satu angka yang sangat besar, saya bisa menunggu dua kali.
Russell Borogove
Meskipun saya tidak menentukannya dengan sangat hati-hati, saya mencari solusi yang melakukan seefisien mungkin (bukan solusi yang hanya cocok dengan persyaratan; Saya sudah menggambarkan satu jawaban potensial yang tidak efisien dalam pertanyaan saya).
Dmitri Shuralyov
3

Sistem UUID didasarkan pada daya komputasi yang terbatas (tetapi besar) di alam semesta yang terbatas (tetapi besar). Jumlah UUID besar bahkan jika dibandingkan dengan hal-hal besar yang tidak masuk akal seperti jumlah partikel di alam semesta. Jumlah UUID, dengan jumlah bit tetap apa pun, kecil, dibandingkan dengan tak terbatas.

Masalah dengan menggunakan 0xFFFF untuk mewakili flag angka Anda adalah membuat pengodean nomor Anda menjadi kurang efisien ketika angka besar. Namun, tampaknya skema UUID Anda memperburuk masalah ini. Alih-alih satu dari 256 byte dilewati, Anda sekarang memiliki seluruh ruang UUID terbuang. Efisiensi perhitungan / pengenalan (alih-alih ruang) banyak bergantung pada komputer teoretis Anda (yang, saya asumsikan Anda miliki jika Anda berbicara tentang infinity). Untuk TM dengan selotip dan pengontrol keadaan terbatas, skema UUID apa pun tidak mungkin untuk menskalakan secara efisien (pada dasarnya, lemma pemompaan mengacaukan Anda dari bergerak melampaui penanda ujung dengan panjang bit tetap secara efisien). Jika Anda tidak mengasumsikan pengendali keadaan terbatas, ini mungkin tidak berlaku, tetapi Anda harus memikirkan ke mana perginya bit dalam proses decoding / pengenalan.

Jika Anda hanya ingin efisiensi yang lebih baik daripada 1 dari 256 byte, Anda dapat menggunakan bit 1-bit apa pun yang akan Anda gunakan untuk skema UUID Anda. Itu 1 dari 2 ^ bit-panjang inefisiensi.

Perhatikan bahwa ada skema penyandian lainnya. Pengkodean byte dengan pembatas merupakan cara termudah untuk diterapkan.

ccoakley
sumber
2

Saya sarankan memiliki array byte (atau int atau long) dan bidang panjang yang mengatakan berapa lama angkanya.

Ini kira-kira pendekatan yang digunakan oleh BigInteger Java . Ruang alamat yang dimungkinkan dari ini sangat besar - cukup mudah untuk memberikan UUID berbeda untuk setiap atom di alam semesta :-)

Kecuali Anda memiliki alasan yang sangat baik untuk melakukan sebaliknya, saya sarankan hanya menggunakan BigInteger secara langsung (atau yang setara dalam bahasa lain). Tidak ada kebutuhan khusus untuk menemukan kembali roda angka besar ....

mikera
sumber
Anda tidak dapat menyandikan panjang array ketika jumlah bidang bisa tak terbatas.
Slawek
Saya setuju bahwa menggunakan solusi yang ada (terutama yang telah melalui pemeriksaan profesional) untuk masalah yang diberikan, jika memungkinkan, lebih disukai. Terima kasih.
Dmitri Shuralyov
@ Lawek: benar, tetapi untuk kasus penggunaan OP menggambarkan (yaitu UUID), BigInteger secara efektif tak terbatas. Anda tidak dapat menyandikan informasi tanpa batas di komputer mana pun dengan memori berukuran terbatas, jadi BigInteger sama bagusnya dengan apa pun yang mungkin Anda capai.
mikera
2

Pertama-tama, terima kasih kepada semua orang yang memberikan jawaban yang bagus untuk pertanyaan saya yang relatif kabur dan abstrak.

Saya ingin berkontribusi jawaban potensial yang saya pikirkan setelah memikirkan jawaban lain. Itu bukan jawaban langsung untuk pertanyaan yang diajukan, tetapi itu relevan.

Seperti yang ditunjukkan beberapa orang, menggunakan integer ukuran 64/128/256 bit sudah memberi Anda ruang yang sangat besar untuk UUID. Jelas itu tidak terbatas, tetapi ...

Mungkin itu mungkin ide yang baik untuk hanya menggunakan ukuran tetap int (katakanlah, 64-bit untuk memulai) sampai 64-bit tidak cukup (atau dekat dengan itu). Kemudian, dengan anggapan Anda memiliki akses ke semua instance UUID sebelumnya, tingkatkan saja semuanya ke int 128-bit dan anggap itu sebagai ukuran tetap bilangan bulat Anda.

Jika sistem memungkinkan jeda / gangguan layanan, dan karena operasi "membangun kembali" seperti itu harus terjadi sangat jarang, mungkin manfaatnya (sistem yang sangat sederhana, cepat, mudah diimplementasikan) akan mengatasi kerugiannya (harus membangun kembali semua bilangan bulat yang sebelumnya dialokasikan ke ukuran bit integer baru).

Dmitri Shuralyov
sumber