生成随机唯一数字的性能问题
本文关键字:性能 问题 数字 唯一 随机 | 更新日期: 2023-09-27 18:08:44
我有一种情况,我需要创建数以万计的唯一数字。然而,这些数字必须是9位数字,不能包含任何0。我目前的方法是生成9个数字(1-9)并将它们连接在一起,如果数字不在列表中,则将其添加到列表中。例如
public void generateIdentifiers(int quantity)
{
uniqueIdentifiers = new List<string>(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<T>
而不是List<T>
。
此外,使用StringBuilder而不是简单的字符串操作将使您获得另外25%的收益。如果你可以用数字代替字符串,你就赢了,因为它只需要三分之一或四分之一的时间。
var quantity = 400000;
var uniqueIdentifiers = new HashSet<int>();
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);
}
在我的机器上,400,000个数字大约需要270毫秒,1,000,000个数字大约需要700毫秒。这甚至没有任何并行性。由于使用HashSet<T>
而不是List<T>
,该算法在O(n)内运行,即持续时间将线性增长。因此,10,000,000个值大约需要7秒。
这个建议可能流行,也可能不流行....这取决于人们的观点。因为你还没有太具体地说明你需要他们做什么,多久一次,或者确切的数字,我将建议一个蛮力的方法。
我将生成十万个数字-应该不会花很长时间,也许几秒钟?然后使用Parallel LINQ对它们执行Distinct()以消除重复项。然后使用另一个PLINQ查询对余数运行一个正则表达式,以消除任何带有零的余数。然后取最上面的x千。(PLINQ在处理这类大型任务方面非常出色)。如果需要,冲洗并重复,直到你的需要足够。
在一台不错的机器上,编写这个简单的函数所花费的时间比运行它所花费的时间要长。我还想问,当你说你实际上需要"数万"个条目时,为什么要测试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<string>(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秒。
也许这样会更快:
//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();
看看已经发布的解决方案,我的解决方案似乎相当基本。但是,它可以工作,并且在大约15秒内生成100万个值(11秒内生成1000万个值)。
public static void generateIdentifiers(int quantity)
{
HashSet<int> uniqueIdentifiers = new HashSet<int>();
while (uniqueIdentifiers.Count < quantity)
{
int value = random.Next(111111111, 999999999);
if (!value.ToString().Contains('0') && !uniqueIdentifiers.Contains(value))
uniqueIdentifiers.Add(value);
}
}
使用字符串数组或stringbuilder,同时使用字符串添加。
如果多于
,您的代码效率就会降低,因为在生成许多id后,您的列表可能会保存新生成的id,因此while循环将运行比您需要的更多的时间。
使用for循环并从该循环生成id,而不随机化。如果需要随机id,请再次使用for循环并生成比您需要的更多的id,并给出生成间隔,并从该列表中随机选择您需要的id。
使用下面的代码创建一个静态列表,并在启动程序时填充它。稍后我将添加第二个代码来生成随机id列表。[我有点忙]
public static Random RANDOM = new Random();
public static List<int> randomNumbers = new List<int>();
public static List<string> randomStrings = new List<string>();
private void fillRandomNumbers()
{
int i = 100;
while (i < 1000)
{
if (i.ToString().Contains('0') == false)
{
randomNumbers.Add(i);
}
}
}
我认为第一件事是使用StringBuilder,而不是连接-您将会感到惊喜。另一件事-使用更有效的数据结构,例如HashSet<>或HashTable。
如果你可以放弃不为零的奇怪要求,那么你当然可以只使用一个随机操作,然后按照你想要的方式格式化你的结果数。
我认为@slugster大致上是正确的——尽管您可以运行两个并行进程,一个生成数字,另一个验证它们,并在验证后将它们添加到可接受的数字列表中。一旦你有足够的,通知原始进程停止。
结合其他建议-使用更有效和合适的数据结构-你应该有一些可接受的工作。
然而,为什么你需要这些数字的问题也很重要——这个需求似乎应该被分析。
像这样?
public List<string> generateIdentifiers2(int quantity)
{
var uniqueIdentifiers = new List<string>(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;
}