生成随机唯一数字的性能问题

Question

我有一种情况,我需要创建成千上万的唯一数字.但是这些数字必须是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

Answer 1

正如其他人所提到的,使用a HashSet<T>而不是a 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);
}

我的机器上需要大约270毫秒才能获得400,000个数字,大约700毫秒需要1,000,000个数字.这甚至没有任何并行性.由于使用a HashSet<T>而不是a List<T>,该算法在O(n)中运行,即持续时间将线性增长.因此,10,000,000个值大约需要7秒.