如何從數組中創建嚴格排序的均勻分佈桶？

Question

我正在尋找採取一個整數數組，並在該陣列上執行部分桶排序。桶中的每個元素都小於當前的桶元素。例如，如果我有10個存儲桶，其值爲0-100 0-9將在第一個存儲區中執行，而第二個存儲區將執行10-19，依此類推。

舉個例子，我可以把1 12 23 44 48放到4個桶中，但是如果我有1,2,7,4,9,1，那麼所有的值都會進入一個桶。我正在尋找一種在保持排序的同時將值均勻分配給所有存儲桶的方法。每個存儲桶中的元素不必進行排序。例如，我看起來與此類似。

2 1 9 2 3 8 7 4 2 8 11 4 => [[2,1]，[2,2]，[3]，[4]，[4]，[7]，[ 8]，[9]，[11]]

我試圖使用此作爲一種快速的方法來分區映射減少列表。

感謝您的幫助。

編輯，也許這將清除的東西了：

我想去的地方在bucket1 < bucket2 < bucket3所有元素......，其中每個桶是無序創建一個散列函數。

Answer 1

如果我正確地理解了它，則需要大約100TB的數據或13,743,895,347,200個未簽名的64位整數，並且要通過多個存儲桶進行分配。

第一步可能是對輸入進行迭代，看例如，每個整數的最高24位，並對它們進行計數。這將給你一個16,777,216個範圍的列表，每個範圍的平均數爲819,200，所以它可能存儲在32位無符號整數中，這將佔用64 MB。

然後，您可以使用它創建一個查詢表，告訴您這16,777,216個範圍中的每個範圍都會進入哪個存儲區。您可以計算每個存儲桶中應該有多少整數（輸入大小除以存儲桶數量），然後遍歷陣列，保持計數總數，並將每個範圍設置爲存儲桶1，直到運行總量過多對於存儲區1，則將範圍設置爲存儲區2，依此類推......

當然總會存在必須在存儲區n和存儲區n + 1之間進行拆分的範圍。爲了跟蹤這一點，你需要創建第二個表格來存儲這些分割範圍中有多少個整數應該進入第n + 1個分區。

所以，你現在已經例如：

HIGH 24-BIT  RANGE   BUCKET BUCKET+1 

    0   0 ~ 2^40-1  1   0 
    1  2^40 ~ 2*2^40-1  1   0 
    2  2*2^40 ~ 3*2^40-1  1   0 
    3  3*2^40 ~ 4*2^40-1  1   0 
     ... 
    16  16*2^40 ~ 17*2^40-1  1   0 
    17  17*2^40 ~ 18*2^40-1  1 284,724 <- highest 284,724 go into bucket 2 
    18  18*2^40 ~ 19*2^40-1  2   0 
     ... 

您現在可以遍歷再次輸入，併爲每個整數看看最高的24位，並使用查找表，看看哪個桶整數應該進入。如果範圍沒有分割，您可以立即將整數移動到右邊的桶中。對於每個拆分範圍，創建一個有序列表或優先級隊列，該隊列可以保存需要進入下一個存儲桶的整數;您只在此列表或隊列中存儲最高值;任何較小的整數都會直接進入存儲區，並且如果將整數添加到完整列表或隊列中，則最小值將移至存儲區。最後，這個列表或隊列被添加到下一個存儲桶中。

範圍的數量應儘可能使用可用內存，因爲這樣可以最大限度地減少拆分範圍中的整數數量。通過大量輸入，您可能需要將分割範圍保存到磁盤，然後分別單獨查看每個分割範圍，找到最高x值，然後相應地將它們移動到分區。

第一次運行時，其複雜度爲N，然後在迭代遍歷輸入時再遍歷範圍R，然後遍歷N，然後對於拆分範圍，您將有類似M.logM的東西進行排序和M進行分配，所以總共爲2 * N + R + M.LogM + M.使用大量範圍來保持低分割範圍內的整數數量可能是加快處理速度的最佳策略。

---

實際上，這是在分割範圍的整數的數目M取決於水桶B的數目並且爲R，其中M = N × B/R，以使得例如有千桶和一百萬個範圍，0.1％的輸入將在分割範圍內並且必須被分類。 （這些是平均值，具體取決於實際分配情況。）這使得總的複雜性2 × N + R +（N × B/R）.Log（N × B/R）+ N × B/R。

又如：

輸入：N = 13,743,895,347,200無符號64位整數
範圍：2 （使用每個整數的最高32位）每範圍
整數：3200（平均）
計數列表：2 16位整數= 8 GB
查找表：2 16位整數= 8 GB
分程表：乙16位整數= 2 ×乙字節

隨着1024桶，這將意味着，B/R = 1/2 ，並且有1023分裂與3200左右的範圍內的整數每個或總共大約3,276,800個整數;這些將不得不被分類並分配到桶中。

使用1,048,576個桶，這將意味着B/R = 1/2 ，並且有1,048,575個分割範圍，每個分割範圍大約有3200個整數，總共約爲3,355,443,200個整數。 （超過65,536個桶當然需要一個32位整數查找表）。

（如果您發現每個範圍的總計數不等於輸入的總大小，溢出計數列表中，您應該切換到一個更大的整數類型計數）

---

讓我們通過一個很小的例子運行：在區間1-100分50個整數必須分佈在5桶。我們選擇了一些範圍，比如20，並逐一輸入來算整數每個範圍內的號碼：

2 9 14 17 21 30 33 36 44 50 51 57 69 75 80 81 87 94 99 
1 9 15 16 21 32 40 42 48 55 57 66 74 76 88 96 
5 6 20 24 34  50 52 58 70 78   99 
    7       51  69 
           55 

3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3 

然後，知道每個桶應該持有10個整數，我們遍歷計數的列表每範圍，每個範圍分配給一斗：

3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3 <- count/range 

1 1 1 1 2 2 2 2 3 3 3 4 4 4 4 5 5 5 5 5 <- to bucket 
      2   1  1        <- to next 

當一個範圍內有兩個桶之間被分割，我們將它應該去的下一桶在一個單獨的表整數數量。我們可以再次迭代輸入，並將所有在非分割範圍內的整數移入桶中;在分割範圍的整數被暫時轉移到單獨的水桶：

bucket 1: 9 14 2 9 1 15 6 5 7 
temp 1/2: 17 16 20 
bucket 2: 21 33 30 32 21 24 34 
temp 2/3: 36 40 
bucket 3: 44 50 48 42 50 
temp 3/4: 51 55 52 51 55 
bucket 4: 57 75 69 66 74 57 57 70 69 
bucket 5: 81 94 87 80 99 88 96 76 78 99 

然後我們來看看溫水桶一個接一個，發現X最高整數作爲第二個表顯示，其移動到下一桶，和剩下到從前的水桶：

temp 1/2: 17 16 20  (to next: 2) bucket 1: 16   bucket 2: 17 20 
temp 2/3: 36 40   (to next: 1) bucket 2: 36   bucket 3: 40 
temp 3/4: 51 55 52 51 55 (to next: 1) bucket 3: 51 51 52 55 bucket 4: 55 

而最終的結果是：

bucket 1: 9 14 2 9 1 15 6 5 7 16 
bucket 2: 21 33 30 32 21 24 34 17 20 36 
bucket 3: 44 50 48 42 50 40 51 51 52 55 
bucket 4: 57 75 69 66 74 57 57 70 69 55 
bucket 5: 81 94 87 80 99 88 96 76 78 99 

所以，出的50個整數，我們不得不進行排序一組3,2和5 intege RS。

---

其實，你並不需要創建一個表整數的應該進入下一個水桶分割範圍內的號碼。您知道每個存儲桶應該有多少個整數，因此在初始分配之後，您可以查看每個存儲桶中已有多少個整數，然後從分解範圍中添加必需數量的（最低值）整數。在上面的例子，這預計每剷鬥10點的整數，這將是：

3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3 <- count/range 
1 1 1/2 2 2/3 3/4 4 4 4 5 5 5 5 5 <- to bucket 

bucket 1: 9 14 2 9 1 15 6 5 7  <- add 1 
temp 1/2: 17 16 20      <- 3-1 = 2 go to next bucket 
bucket 2: 21 33 30 32 21 24 34   <- add 3-2 = 1 
temp 2/3: 36 40       <- 2-1 = 1 goes to next bucket 
bucket 3: 44 50 48 42 50     <- add 5-1 = 4 
temp 3/4: 51 55 52 51 55     <- 5-4 = 1 goes to next bucket 
bucket 4: 57 75 69 66 74 57 57 70 69  <- add 1-1 = 0 
bucket 5: 81 94 87 80 99 88 96 76 78 99 <- add 0 

---

如何輸入的多將在分割範圍和需要的計算要排序的，上面給出的作爲M = N × B/R，是大致均勻分佈的輸入的平均值。稍有偏差，在輸入空間的某個部分具有更多值將不會產生太大影響，但確實可以制定最壞情況輸入來阻止算法。

讓我們再在該實施例中的外觀：

輸入：N = 13,743,895,347,200無符號64位整數
範圍：2 （使用每個整數的最高32位）每範圍
整數：3200（平均）
剷鬥：每桶1,048,576
整數：13107200

首先，如果整數範圍包含多於2個整數，則必須將64位整數用於計數表，因此它的大小爲32GB，這可能會迫使您使用更少的範圍，具體取決於可用內存。

此外，每個存儲區的整數大於每個存儲區的目標大小的自動分隔範圍。因此，如果整數分佈在很多本地羣集中，那麼您可能會發現大部分輸入都在需要排序的分割範圍內。

如果你有足夠的內存來運行使用2- 範圍中的第一個步驟，則每個範圍具有2 不同的值，你可以分發分割範圍並且使用計數排序桶（其具有線性複雜）。

如果您沒有內存使用範圍，並且最終出現問題的大分割範圍，則可以在分割範圍上再次使用完整算法。假設您使用了2個範圍，期望每個範圍能夠保持大約51,200個整數，並且最終會出現一個意想不到的大分割範圍，其中需要分配391個桶，需要5,120,000,000個整數。如果你在這個有限的範圍內再次運行該算法，那麼只需391個桶就可以得到一個範圍（每個範圍平均擁有19個整數，最多有16個不同的值），並且只有很小的風險纔會以大再次分割範圍。