我正在處理一個很長的數字串列，比如 15 億。我需要一種方法來指定我想保留的數字的百分比，其余的丟棄。現在我知道我可以使用亂數生成器來隨機決定是否應該保留它，但問題是我需要保留/丟棄的數字始終相同。這意味著，如果我運行程式并決定丟棄索引 2、5 和 10，那么下次我運行程式時，它也必須丟棄 2、5 和 10。這個非常重要。
我也面臨記憶問題。為了生成一個巨大的布爾串列來確定哪些數字被丟棄，哪些不是（例如，如果我們決定這樣做），分析器說程式使用了大約 15gb 的記憶體，考慮到我還沒有，這已經太多了另一個包含 15 億個數字的串列。如果這很重要，這是我的代碼：
static bool[] GenerateShouldAddList(int totalCombos, decimal percentToAdd)
{
Random RNG = new Random();
bool[] bools = new bool[totalCombos];
int percent = (int)(percentToAdd * 100);
for (int i = 0; i < totalCombos; i )
{
int randNum = RNG.Next(0, 101);
bools[i] = randNum < percent;
}
return bools;
}
所以我在想，為了避免列出一個龐大的串列，有沒有辦法制作一個函式來接收索引號（比如索引 5364）、總數（15 億）和你想要保留的百分比，然后回傳給我是否應該添加該特定索引？如果我通過該函式一次運行每個索引，我應該只剩下我指定的數字百分比。最重要的是，這個函式應該總是為相同的索引回傳相同的結果（如果 totalNumbers 和百分比沒有改變）。我認為這是不可能的，但我也希望這里有人比我聰明得多。任何幫助表示贊賞！
uj5u.com熱心網友回復：
由于您有很多專案，我建議使用列舉，IEnumerable<T>而不是陣列（這很可能不適合記憶體）。另一個要求 - 可重復選擇 - 可以用
種子new Random(seed)解決：我們一次又一次地創建并擁有相同的序列：
static IEnumerable<bool> GenerateShouldAddList(int totalCombos, decimal percentToAdd) {
Random RNG = new Random(789); // Whatever seed you like here
double threshold = percentToAdd / 100.0;
for (int i = 0; i < totalCombos; i)
yield return RNG.NextDouble() < threshold;
}
如果你堅持有一個陣列，你可以添加.ToArray()，例如
using System.Linq;
...
bool[] array = GenerateShouldAddList(10000, 5.0m).ToArray();
但我真的懷疑你是否應該這樣做。
uj5u.com熱心網友回復：
聽起來你想要一個函式，它接受一個索引和一個百分比，并且總是給出是否應該保留該索引的相同結果，但是以一種足夠隨機的方式。這可以通過使用散列演算法來實作，以便輸入始終以隨機方式散列到相同的輸出。我用 10,000 個索引測驗了下面的內容，在 10% 時它保持 1006，在 50% 時它保持 4998，在 90% 時它保持 9006，所以保持的百分比非常接近要求的值，同時仍然是隨機的。
using System.Security.Cryptography;
public static class ToKeepOrNotToKeep
{
private static readonly MD5 _md5 = MD5.Create();
public static bool AtIndex(int index, double percentToKeep)
{
var byteArray = BitConverter.GetBytes(index);
var hash = _md5.ComputeHash(byteArray);
//I know that the hash is 16 bytes, and here we are converting
//only the first 8 bytes to a ulong, but it's still random and
//should work just as well as if we used all 16 bytes for our
//threshold test
var number = BitConverter.ToUInt64(hash, 0);
var threshold = ulong.MaxValue * percentToKeep;
if (number <= threshold)
return true;
else
return false;
}
}
像這樣運行加密哈希會產生一些開銷，所以如果您擔心性能，我會在BenchmarkDotNet運行第 11 代 i7 11370H 的筆記本電腦上運行此程序的基準測驗，平均運行時間為 220 ns。以您所說的數量，15 億次操作僅運行此方法將消耗大約 5.5 分鐘的 CPU 時間。如果您擔心這 5.5 分鐘，那么您可以找到更簡單、更快的散列方法。
我很好奇通過切換到評論中建議的更簡單的散列演算法（如 FNV-1a）你會看到多少性能提升，所以我在下面實作了它
public static class ToKeepOrNotToKeep
{
public static bool AtIndex(int index, double percentToKeep)
{
var byteArray = BitConverter.GetBytes(index);
var hash = getHash(byteArray);
var threshold = ulong.MaxValue * percentToKeep;
if (hash <= threshold)
return true;
else
return false;
}
private ulong getHash(byte[] input)
{
unchecked
{
ulong hash = 14695981039346656037;
foreach(var b in input)
{
hash ^= b;
hash *= 1099511628211;
}
}
}
}
以這個版本為基準，它比 MD5 密碼散列快得多，平均每個方法呼叫大約需要 10 ns 運行，超過 15 億次操作將是 15 秒而不是 5.5 分鐘，但分布的隨機性要小得多。為了粗略比較 MD5 哈希版本與 FNV1-a 版本的分布，這里是前 100 個索引，其中 1 表示保留，0 表示丟棄，運行率為 50%
MD5 1111011001110001001011001110110010000011000101110000001000100010100111110010111010011111000011000100
FNV-1a 1000011110000111100001111000011110000111100001111000011110000111100001111000011110000111100001111000
FNV-1a 版本感覺更具周期性，因此如果選擇中的隨機性對您很重要，那么 MD5 哈希方法的額外開銷對您來說可能是值得的。如果分塊是可以接受的并且您想要速度，那么 FNV-1a 版本會快得多。
uj5u.com熱心網友回復：
您似乎想要一個函式，它接受一個索引和一個百分比值，并回傳一個布林值，無論您is_kept(index=2, percent=50)在之前還是之后呼叫is_kept(index=50000, percent=50)并且不想存盤任何內容，其結果都是相同的。
為此，我會生成索引的哈希值，然后將其視為一個數字，除以最大哈希值并與百分比進行比較。這將給出類似隨機的行為，而無需為狀態或一長串標志分配任何記憶體。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/532374.html
標籤：C＃算法随机的
下一篇：使用遞回和記憶理解LCS問題