給定一個包含 1~N 的集合，我試圖將它們公平地映射到 M 個插槽中的一個（N > M）。我認為這是多對一的映射問題。
天真的解決方案是使用模運算子，給定 N = 10 和 M = 3，我們可以進行如下映射：
N M
1 % 3 = 1 (assign to 2nd slot)
2 % 3 = 2 (assign to 3rd slot)
...
9 % 3 = 0 (assign to 1st slot)
這個解決方案看起來很公平，但需要昂貴的運營商。是否有任何現有的演算法可以解決此類問題？
提前致謝！
uj5u.com熱心網友回復：
是否%為慢運算子是有爭議的，但位操作更快。如果您樂于映射到多個 2 的冪的 bin，M=2^k，那么您可以屏蔽掉較低的 k 位
x & (M - 1);
或者
x & ((1 << k)-1);
如果 bin 的數量是梅森素數，M = 2^s-1 還有一個快速的方法來得到余數：
unsigned int mod_Mersenne(unsigned int x, unsigned int s)
{
unsigned int p = (1 << s) - 1;
unsigned int y = (x & p) (x >> s);
return (y > p) ? y - p : y;
}
我相信你也可以做到無分支，但我不記得是怎么做的。
如果您需要按順序對數字進行合并，例如在您的示例中，并且如果您可以選擇 M 作為較小整數的字長，您還可以利用無符號整數型別像模數一樣處理溢位，因此您可以執行以下操作
unsigned char i = 0; // M = 256 (probably)
for (int j = 0; j < N; j , i )
bin[i] ; // do something with the bin
當i移動超過無符號字符的大小時，它會環繞為零。
這僅適用于無符號，因此不要在此處使用有符號整數。請注意，字符不必是八位，但您可以檢查。（很有可能是）。
通常，無符號算術的行為就像您已經取模一樣，因此如果您可以選擇 N 來匹配字長，您就可以利用它。
uj5u.com熱心網友回復：
m = n % M具有常數的模數M通常直接從定義中實作
m = n - M*(n/M)
這很容易被認為是昂貴的 - 至少與位掩碼相比。
對于除以常數，復雜的編譯器通常會實作另一種演算法（由蒙哥馬利開發），該演算法首先包含一個通過倒數乘法的近似值，然后是一個或兩個調整階段以修復某些極端情況，其中第一個近似值m' = (n * R) >> K)可以相差一個（或可能有兩個）。
這提出了一些改進：
- 小心地跳過調整階段，
(1<<k)/M用某個值抵消，以便新系數乘積的最高位0 <= m'' = (n * R) >> K < M完全在所需范圍內。 - 考慮映射函式是否真的需要是模數：如果足夠了
0<= m'' < M，就不需要乘以m = n - M*m''.
對于N = 10，M = 3，合適的系數是K =3分之256= 85，K = 8，所述值映射n=0..9到m=0..2與m = n * 85 >> 8作為
// n = 0 1 2 3 4 5 6 7 8 9
// m = 0 0 0 0 1 1 1 2 2 2 (approximation of n/3)
（獲得相同輸出值集的最小數字是 btw K=16/3 = 5, k = 4）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/362047.html
標籤：算法
上一篇：最小化數量
下一篇：給定n個數字的排列陣列，計算編號。元組(i,j,k,l,m)使得i<j<k<l<m和a[i]<a[k]<a[j]<a[m]<a[l]