我正在尋找可以幫助滿足以下要求的方法或演算法：
- 將元素劃分為定義數量的 X 磁區。如果需要，可能會隨著時間的推移手動重新定義磁區數。
- 每個磁區不應有超過 Y 個元素
- 元素具有“類別 ID”和“元素 ID”。理想情況下，具有相同類別 ID 的所有元素都應位于同一磁區內。僅當給定類別的元素多于 Y 時，它們才應溢位到盡可能少的磁區。類別數比磁區數大幾個數量級。
- 如果集合中的元素先前已分配給給定磁區，則應繼續將其分配給同一磁區
- 考慮資料的變化。現有元素可能會被移除，而每個類別中的新元素都可以添加。
到目前為止，我天真的方法是：
- 按元素數量降序對類別進行排序
- 為給定磁區保留一個具有元素計數的變數
- 將第一個類別中的行分配給第一個磁區并增加元素計數
- if count-of-elements > Y：將溢位的元素分配給下一個磁區，但前提是類別中的元素數大于 Y。否則將給定類別中的所有元素分配給下一個磁區
- 繼續直到所有元素都分配給磁區
為了持久化所有對的分配存盤在資料庫中：（元素 ID，磁區 ID）
關于連續重新分配：
- 從資料庫中洗掉任何已洗掉的元素
- 根據 (element Id, partition Id) 將現有元素分配給磁區
- 對于任何新元素，請遵循上述演算法
我主要擔心的是，在幾次這樣的運行之后，我們最終會得到遍布所有磁區的類別，因為初始磁區將全部填滿。也許向 Y 添加一個緩沖區（20% 左右）可能會有所幫助。此外，如果其中一個類別的元素數量突然增加，則磁區將需要重新平衡。
是否有任何現有的演算法可能在這里有所幫助？
uj5u.com熱心網友回復：
由于未來的資料變化，這是目前未知的 NP hard（背包）上的 NP hard（尋找分割太大類別的最佳方法）。顯然，你能做的最好的就是啟發式。
按降序對類別進行排序。對磁區使用堆/優先級佇列，將每個類別放入最不完整的可用磁區。如果該類別不適合，則將其盡可能均勻地分成盡可能少的磁區。我的猜測（實驗！）是嘗試讓磁區保持相同的填充是最好的。
重新分配時，首先洗掉已洗掉的元素。然后按類別對新元素進行分組。按類別有多少首選位置升序排列，然后按大小降序排列。現在將具有 0 個首選位置的類別移到末尾。
對于每個類別，如果可能，將其新元素拆分到首選磁區中，使它們同樣充滿。如果這不可能，請將它們放入盡可能空的磁區中。如果這不可能，則將它們拆分以將它們放在盡可能少的磁區中。
當然，有可能提出最終將其變成一團糟的資料集。但它是一種非常善意的努力，試圖表現得很好。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505880.html
上一篇：JS中物件的遞回解決方案