生成随机唯一数字的性能问题
我有一种情况，我需要创建成千上万的唯一数字。 但是这些数字必须是9位数，不能包含任何0。 我当前的方法是生成9位数（1-9）并将它们连接在一起，如果该数字不在列表中，则将其添加到其中。 例如
public void generateIdentifiers(int quantity) { uniqueIdentifiers = new List(quantity); while (this.uniqueIdentifiers.Count < quantity) { string id = string.Empty; id += random.Next(1,10); id += random.Next(1,10); id += random.Next(1,10); id += " "; id += random.Next(1,10); id += random.Next(1,10); id += random.Next(1,10); id += " "; id += random.Next(1,10); id += random.Next(1,10); id += random.Next(1,10); if (!this.uniqueIdentifiers.Contains(id)) { this.uniqueIdentifiers.Add(id); } } } 然而，在大约400,000时，由于越来越多的生成数字是重复的，因此该过程确实变慢了。 我正在寻找一种更有效的方式来执行此过程，任何帮助将非常感激。
编辑： – 我正在生成这些 – http://www.nhs.uk/NHSEngland/thenhs/records/Pages/thenhsnumber.aspx
正如其他人所提到的，使用HashSet而不是List 。
此外，使用StringBuilder而不是简单的字符串操作将获得另外25％。 如果你可以使用数字而不是字符串，那么你就赢了，因为它只需要三分之一或四分之一的时间。
var quantity = 400000; var uniqueIdentifiers = new HashSet(); while (uniqueIdentifiers.Count < quantity) { int i=0; i = i*10 + random.Next(1,10); i = i*10 + random.Next(1,10); i = i*10 + random.Next(1,10); i = i*10 + random.Next(1,10); i = i*10 + random.Next(1,10); i = i*10 + random.Next(1,10); i = i*10 + random.Next(1,10); i = i*10 + random.Next(1,10); i = i*10 + random.Next(1,10); uniqueIdentifiers.Add(i); }
我的机器上需要大约270毫秒才能获得400,000个数字，大约700毫秒需要1,000,000个数字。 这甚至没有任何并行性。 由于使用了HashSet而不是List ，因此该算法在O（n）中运行，即持续时间将呈线性增长。 因此，10,000,000个值大约需要7秒。
这个建议可能会或可能不会受欢迎……这取决于人们的观点。 因为你没有过于具体地说明你需要什么，经常或确切的数字，我会建议一个暴力的方法。
我会产生十万个数字 – 不应该花很长时间，也许几秒钟？ 然后使用Parallel LINQ对它们执行Distinct（）以消除重复。 然后使用另一个PLINQ查询对剩余部分运行正则表达式，以消除其中的任何零。 然后拿前十千。 （PLINQ非常适合翻阅像这样的大型任务）。 如果需要，冲洗并重复，直到您有足够的需求为止。
在一台体面的机器上，只需要花费更长的时间来编写这个简单的function，而不是运行它。 当你说你实际上需要“成千上万”时，我还会查询为什么你有400K条目要测试？
这里的诀窍是你只需要一万个唯一数字。 从理论上讲，你可能有近9,0E + 08的可能性，但为什么要关心你需要这么少？
一旦你意识到你可以减少组合，那么创建足够的唯一数字很容易：
long[] numbers = { 1, 3, 5, 7 }; //note that we just take a few numbers, enough to create the number of combinations we might need var list = (from i0 in numbers from i1 in numbers from i2 in numbers from i3 in numbers from i4 in numbers from i5 in numbers from i6 in numbers from i7 in numbers from i8 in numbers from i9 in numbers select i0 + i1 * 10 + i2 * 100 + i3 * 1000 + i4 * 10000 + i5 * 100000 + i6 * 1000000 + i7 * 10000000 + i8 * 100000000 + i9 * 1000000000).ToList();
此代码段会立即创建超过1,000,000个有效唯一编号的列表。
尝试避免检查，确保始终选择一个唯一的号码：
static char[] base9 = "123456789".ToCharArray(); static string ConvertToBase9(int value) { int num = 9; char[] result = new char[9]; for (int i = 8; i >= 0; --i) { result[i] = base9[value % num]; value = value / num; } return new string(result); } public static void generateIdentifiers(int quantity) { var uniqueIdentifiers = new List(quantity); // we have 387420489 (9^9) possible numbers of 9 digits in base 9. // if we choose a number that is prime to that we can easily get always // unique numbers Random random = new Random(); int inc = 386000000; int seed = random.Next(0, 387420489); while (uniqueIdentifiers.Count < quantity) { uniqueIdentifiers.Add(ConvertToBase9(seed)); seed += inc; seed %= 387420489; } }
我会尝试用小数字解释背后的想法......
假设您最多有7种可能的组合。 我们选择一个对7为素数的数，例如3，以及一个随机起始数，例如4。
在每一轮，我们将当前数字加3，然后我们得到模7的结果，所以我们得到这个序列：
4 - > 4 + 3％7 = 0
0 - > 0 + 3％7 = 3
3 - > 3 + 3％7 = 6
6 - > 6 + 6％7 = 5
通过这种方式，我们以非连续的方式生成从0到6的所有值。 在我的例子中，我们正在做同样的事情，但是我们有9 ^ 9种可能的组合，并且作为数字素数，我选择386000000（你只需要避免3的倍数）。
然后，我拿起序列中的数字，然后将其转换为基数9。
我希望这很清楚:)
我在我的机器上进行了测试，生成400k的唯一值需要大约1秒钟。
Meybe这会更快：
//we can generate first number wich in 9 base system will be between 88888888 - 888888888 //we can't start from zero becouse it will couse the great amount of 1 digit at begining int randNumber = random.Next((int)Math.Pow(9, 8) - 1, (int)Math.Pow(9, 9)); //no we change our number to 9 base, but we add 1 to each digit in our number StringBuilder builder = new StringBuilder(); for (int i=(int)Math.Pow(9,8); i>0;i= i/9) { builder.Append(randNumber / i +1); randNumber = randNumber % i; } id = builder.ToString();
看看已发布的解决方案，我看起来相当基本。 但是，它起作用，并产生大约1s的100万个值（11s中的1000万个）。
public static void generateIdentifiers(int quantity) { HashSet uniqueIdentifiers = new HashSet (); while (uniqueIdentifiers.Count < quantity) { int value = random.Next(111111111, 999999999); if (!value.ToString().Contains('0') && !uniqueIdentifiers.Contains(value)) uniqueIdentifiers.Add(value); } }
使用字符串数组或字符串构建器，wjile使用字符串添加。
更重要的是，你的代码效率不高，因为在生成许多id之后，你的列表可能会保存新生成的id，因此while循环将运行超出你需要的数量。
用于循环并从此循环生成您的id而不随机化。 如果需要随机id，则再次使用for循环并生成超出需要的数量并给出生成间隔，并从该列表中随机选择您需要多少。
使用下面的代码获得静态列表并在启动程序时填写它。 我稍后会添加第二个代码来生成随机ID列表。 [我有点忙]
public static Random RANDOM = new Random(); public static List randomNumbers = new List (); public static List randomStrings = new List (); private void fillRandomNumbers() { int i = 100; while (i < 1000) { if (i.ToString().Contains('0') == false) { randomNumbers.Add(i); } } }
我认为首先要使用StringBuilder，而不是连接 – 你会惊喜地发现。 Antoher的东西 – 使用更有效的数据结构，例如HashSet <>或HashTable。
如果你可以放弃非常奇怪的要求而不是零 – 那么你当然可以只使用一个随机操作，然后按照你想要的方式格式化你得到的数字。
我认为@slugster大致正确 – 虽然您可以运行两个并行进程，一个用于生成数字，另一个用于validation它们并在validation时将它们添加到接受的数字列表中。 一旦你有足够的信号，就会发出原始过程的信号。
将此与其他建议相结合 – 使用更有效和更合适的数据结构 – 您应该拥有可接受的工作。
然而，为什么需要这样的数字的问题也很重要 – 这个要求似乎应该被分析。
像这样的东西？
public List generateIdentifiers2(int quantity) { var uniqueIdentifiers = new List (quantity); while (uniqueIdentifiers.Count < quantity) { var sb = new StringBuilder(); sb.Append(random.Next(11, 100)); sb.Append(" "); sb.Append(random.Next(11, 100)); sb.Append(" "); sb.Append(random.Next(11, 100)); var id = sb.ToString(); id = new string(id.ToList().ConvertAll(x => x == '0' ? char.Parse(random.Next(1, 10).ToString()) : x).ToArray()); if (!uniqueIdentifiers.Contains(id)) { uniqueIdentifiers.Add(id); } } return uniqueIdentifiers; }