首頁>技術>

首先讓我們回顧一下:

擴容時,隨機選擇要移動的元素從現有 n 節點擴容到 n+1 節點時,n 節點上每個元素有 1/(n+1) 的機率移動到新節點使用穩定的、可重現的隨機數序列——以 key 為隨機數種子

我們遺留了一個問題,O(n) 的演算法複雜度不夠理想,如何最佳化?

最佳化複雜度

與其在 bucket 逐步增加的過程中,每次隨機地決定是否跳躍到新增的 bucket。我們嘗試隨機決定下一次加到第幾個 bucket 才跳躍。當然,這個隨機選取的目標需要符合一定的機率分佈。

假設上一次 k 的跳躍發生在增加第 b+1 個 bucket 時,即 ch(k,b) != ch(k,b+1)ch(k,b+1) = b+1(本文 bucket 編號從 1 開始)。這一次跳躍,我們隨機選擇了一個位置 j+1,即 ch(k,j+1) != ch(k,j)ch(k,j) = ch(k,b+1)

作為單次選擇,跳躍發生在 b+2(連續跳)或者 INT_MAX(再也不跳了),都是可能的。但總體上,j 的選擇要滿足一定的規律。

定義事件:對於任意 i >= b+2,在增加第 b+2、b+3 ... i 個 bucket 時,都沒有發生跳躍。該事件當且僅當 j+1 > i,即 j >= i 時成立。

該事件的機率可以這麼算:

從 b+1 增加到 b+2,不跳躍的機率是 (b+1)/(b+2)一直加到第 i 個 bucket,都不跳躍,其機率為 (b+1)/(b+2)*(b+2)/(b+3)*...*(i-1)/(-) = (b+1)/iP(j>=i) = (b+1)/i。該等式對於任意 i 都成立。

j 是我們任選的,可能 j>=i,也可能 j<i。選擇方式待定,但要讓機率 P(j>=i)等於(b+1)/i。

每次要選擇 j 時,我們生成一個 [0,1) 上均勻分佈的隨機數 r,顯然,布林表示式 r <= (b+1)/i 為 true 的機率是 (b+1)/i。我們先變換一下表達式:

r <= (b+1)/i 變換後可得 i <= (b+1)/r。由於 i 是整數,(b+1)/r 向下取整不等式依然成立,表示式最後變換為 i <= floor((b+1)/r)

當上述表示式為 true 時,我們就選則大 j (j>=i);否則,我們就選則小 j (j<i)。這個選擇方式, 就使 P(j>=i) = (b+1)/i 成立。

i <= floor((b+1)/r) 時,i 最大可為 floor((b+1)/r),則 j>=floor((b+1)/r)i > floor((b+1)/r) 時,i 最小可為 floor((b+1)/r)+1,則 j<=floor((b+1)/r)

綜上 j = floor((b+1)/r)。計算有 num_buckets 時,key 應當所在的 bucket 編號(本文中從 1 開始)的程式碼為:

func ch2(key int, num_buckets int) int {    r := rand.New(rand.NewSource(int64(key)))    b1 := -1    j := 0    for j < num_buckets {        b1 = j + 1        j = int(math.Floor(float64(b1)/r.Float64()))    }    return b1}

r 的平均值是 0.5,即跳躍平均發生在 bucket 數量翻倍時。粗略的看,演算法複雜度是 O(log(n))。

13
最新評論
  • BSA-TRITC(10mg/ml) TRITC-BSA 牛血清白蛋白改性標記羅丹明
  • 總結:上傳python專案至git上前的一些準備工作