Hai Rekan Statistik,
Saya memiliki hash penghasil sumber (mis., Menghitung string dengan stempel waktu dan informasi lainnya dan hashing dengan md5) dan saya ingin memproyeksikannya ke sejumlah bucket (katakan 100).
contoh hash: 0fb916f0b174c66fd35ef078d861a367
Apa yang saya pikirkan pada awalnya adalah menggunakan hanya karakter pertama dari hash untuk memilih ember, tetapi ini mengarah pada proyeksi liar yang tidak seragam (yaitu beberapa huruf terlihat sangat jarang dan lainnya sangat sering)
Kemudian, saya mencoba mengubah string hexa ini menjadi integer menggunakan jumlah nilai char, kemudian mengambil modulo untuk memilih sebuah bucket:
import sys
for line in sys.stdin:
i = 0
for c in line:
i += ord(c)
print i%100
Tampaknya berhasil dalam praktiknya, tetapi saya tidak tahu apakah ada akal sehat atau hasil teoretis yang dapat menjelaskan mengapa dan sejauh mana ini benar?
[Sunting] Setelah beberapa pemikiran saya sampai pada kesimpulan berikut: Secara teori Anda dapat mengubah hash menjadi integer (sangat besar) dengan menafsirkannya sebagai angka: i = h [0] + 16 * h [1] + 16 * 16 * h [2] ... + 16 ^ 31 * h [31] (setiap huruf mewakili angka heksadesimal). Kemudian Anda bisa memodulasi angka besar ini untuk memproyeksikannya ke ruang bucket. [/ Edit]
Terima kasih!
Jawaban:
NB: memberikan jawaban yang muncul dari diskusi dalam komentar sehingga lebih mudah dibaca untuk orang yang tertarik
(versi terbaru)
Misalkan kita memiliki sumber yang menghasilkan acara independen yang ingin kita distribusikan secara seragam ke dalam emberB
Langkah kuncinya adalah:
Untuk 1. solusi yang populer adalah menggunakan MurmurHash untuk menghasilkan integer 64 atau 128 bit.
Untuk 3. solusi sederhana adalah dengan beralih pada dan periksa bahwa ada dij=1..B p [bjB,bj+1B[
Dalam (python) pseudo-code prosedur keseluruhan bisa menjadi:
(versi sebelumnya, benar-benar tidak optimal)
Pengamatan pertama adalah bahwa huruf ke- n dari hash harus didistribusikan secara seragam sehubungan dengan alfabet (yang panjangnya di sini 16 huruf - terima kasih kepada @leonbloy karena menunjukkannya).
Kemudian, untuk memproyeksikannya ke rentang [0,100 [, triknya adalah mengambil 2 huruf dari hash (mis. Posisi 1 dan 2) dan menghasilkan bilangan bulat dengan itu:Nilai ini hidup dalam kisaran [0,16+ (16-1) * 16 [, maka kita hanya perlu memodulnya hingga 100 untuk menghasilkan ember di kisaran [0, 100 [kisaran:Seperti yang ditunjukkan dalam komentar, melakukan jadi dampak keseragaman distribusi karena huruf pertama lebih berpengaruh daripada yang kedua.Secara teori Anda dapat mengubah seluruh hash menjadi bilangan bulat (sangat besar) dengan menafsirkannya sebagai angka: i = h [0] + 16 * h [1] + 16 * 16 * h [2] ... + 16 ^ 31 * h [31] (setiap huruf mewakili angka heksadesimal). Kemudian Anda bisa memodulasi angka besar ini untuk memproyeksikannya ke ruang bucket. Seseorang kemudian dapat mencatat bahwa mengambil modulo dari i dapat diuraikan menjadi operasi distributif dan aditif:
sumber
Saya memiliki masalah yang sama dan muncul dengan solusi berbeda yang mungkin lebih cepat dan lebih mudah diimplementasikan dalam bahasa apa pun.
Pikiran pertama saya adalah untuk mengirimkan barang dengan cepat dan seragam dalam jumlah yang tetap, dan agar dapat diukur, saya harus meniru keacakan.
Jadi saya mengkodekan fungsi kecil ini mengembalikan angka float di [0, 1 [diberikan string (atau segala jenis data sebenarnya).
Di sini, di Python:
Tentu saja itu tidak acak, bahkan itu bukan pseudo acak, data yang sama akan selalu mengembalikan checksum yang sama. Tapi itu bertindak seperti acak dan cukup cepat.
Anda dapat dengan mudah mengirim dan kemudian mengambil item dalam ember N dengan hanya menetapkan setiap item ke nomor bucket math.floor (N * pseudo_random_checksum (item)).
sumber