这段代码在性能方面有什么问题？List.Contains,随机使用,线程？

Question

我有一个本地类,其中有一个方法用于构建一个字符串列表,我发现当我点击这个方法(在一个1000次的for循环中)时,它通常不会返回我请求的数量.

我有一个全局变量:

string[] cachedKeys

传递给方法的参数:

int requestedNumberToGet

该方法看起来类似于:

List<string> keysToReturn = new List<string>();
int numberPossibleToGet = (cachedKeys.Length <= requestedNumberToGet) ? 
cachedKeys.Length : requestedNumberToGet;
Random rand = new Random();

DateTime breakoutTime = DateTime.Now.AddMilliseconds(5);

//Do we have enough to fill the request within the time? otherwise give 
//however many we currently have
while (DateTime.Now < breakoutTime
    && keysToReturn.Count < numberPossibleToGet
    && cachedKeys.Length >= numberPossibleToGet)
{
    string randomKey = cachedKeys[rand.Next(0, cachedKeys.Length)];
    if (!keysToReturn.Contains(randomKey))
        keysToReturn.Add(randomKey);
}

if (keysToReturn.Count != numberPossibleToGet)
    Debugger.Break();

我在cachedKeys中有大约40个字符串,长度不超过15个字符.

我不是线程专家所以我实际上只是在一个循环中调用这个方法1000次并且一直在那里进行调试.

这台运行的机器是一个相当强大的桌面,所以我希望突破时间是真实的,实际上它在循环的任何一点随机断开(我已经看过20s,100s,200s,300s).

任何人都有任何想法,我在这里错了吗？

编辑:仅限于.NET 2.0

编辑:突破的目的是,如果方法执行时间太长,客户端(使用XML提要数据的几个Web服务器)将不必等待其他项目依赖项初始化,它们只是给出0结果.

编辑:以为我会发布表现统计数据

原版的

• '0.0042477465711424217323710136' - 10
• '0.0479597267250446634977350473' - 100
• '0.4721072091564710039963179678' - 1000

双向飞碟

• '0.0007076318358897569383818334' - 10
• '0.007256508857969378789762386' - 100
• '0.0749829936486341141122684587' - 1000

弗雷迪里奥斯

• '0.0003765841748043396576939248' - 10
• '0.0046003053460705201359390649' - 100
• '0.0417058592642360970458535931' - 1000

Answer 1

为什么不直接获取列表的副本 - O(n) - 将其洗牌,也是O(n) - 然后返回已请求的密钥数.实际上,shuffle只需要是O(nRequested).继续使用未抽取位的开头交换列表中未抽取位的随机成员,然后将混洗位扩展为1(只是一个名义计数器).

编辑:这是一些产生结果的代码IEnumerable<T>.请注意,它使用延迟执行,因此如果您在首次开始迭代结果之前更改传入的源,您将看到这些更改.获取第一个结果后,元素将被缓存.

static IEnumerable<T> TakeRandom<T>(IEnumerable<T> source,
                                    int sizeRequired,
                                    Random rng)
{
    List<T> list = new List<T>(source);

    sizeRequired = Math.Min(sizeRequired, list.Count);

    for (int i=0; i < sizeRequired; i++)
    {
        int index = rng.Next(list.Count-i);            
        T selected = list[i + index];
        list[i + index] = list[i];
        list[i] = selected;
        yield return selected;
    }
}

我们的想法是,在你获取n元素之后的任何时候,n列表的第一个元素都是那些元素 - 所以我们确保不再选择那些元素.然后从"其余"中选择一个随机元素,将其交换到正确的位置并产生它.

希望这可以帮助.如果你正在使用C#3,你可能希望通过将"this"放在第一个参数前面来使其成为扩展方法.