这段代码的性能有什么问题?列表。包含,随机使用,线程?

为什么不直接复制一份列表-O(n)-将其洗牌,也洗牌O(n)-然后返回已请求的密钥数。事实上,洗牌只需要是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”放在第一个参数前面来将其作为扩展方法。

一些想法。

首先,每次通过循环时,您的keystoreurn列表都可能被添加到其中,对吗?您正在创建一个空列表,然后将每个新键添加到该列表中。由于列表没有预先调整大小,因此每次添加都将成为一个O(n)操作( see MSDN documentation )。若要解决此问题,请尝试像这样预先调整列表的大小。

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

其次,你的突破时间在Windows上是不现实的(好吧,好吧,不可能)。我读过的关于Windows计时的所有信息都表明,你可能希望的最好分辨率是10毫秒,但实际上它更像是15-18毫秒。实际上,请尝试以下代码:

for (int iv = 0; iv < 10000; iv++) {
    Console.WriteLine( DateTime.Now.Millisecond.ToString() );
}

您将在输出中看到离散跳跃。这是我刚刚在我的机器上运行的一个示例输出。

13
...
13
28
...
28
44
...
44
59
...
59
75
...

第三,我是否正确地假设突破时间是防止主线程锁定的时间?如果是这样,那么就很容易将函数派生到线程池线程,并让它运行到完成,而不管需要多长时间。然后,主线程可以对数据进行操作。

主要问题是在随机场景中使用重试以确保获得唯一值。这很快就会失去控制,特别是当请求的项目数量接近要获取的项目数量时,即如果增加密钥数量,您将不太经常看到问题,但这是可以避免的。

下面的方法通过保留剩余键的列表来实现。

List<string> GetSomeKeys(string[] cachedKeys, int requestedNumberToGet)
{
    int numberPossibleToGet = Math.Min(cachedKeys.Length, requestedNumberToGet);
    List<string> keysRemaining = new List<string>(cachedKeys);
    List<string> keysToReturn = new List<string>(numberPossibleToGet);
    Random rand = new Random();
    for (int i = 0; i < numberPossibleToGet; i++)
    {
        int randomIndex = rand.Next(keysRemaining.Count);
        keysToReturn.Add(keysRemaining[randomIndex]);
        keysRemaining.RemoveAt(randomIndex);
    }
    return keysToReturn;
}

对于您的版本,超时是必要的,因为您可能会长时间不断尝试获取值。特别是当您想要检索整个列表时,在这种情况下,依赖于重试的版本几乎肯定会失败。

更新: 上述性能优于这些变化:

List<string> GetSomeKeysSwapping(string[] cachedKeys, int requestedNumberToGet)
{
    int numberPossibleToGet = Math.Min(cachedKeys.Length, requestedNumberToGet);
    List<string> keys = new List<string>(cachedKeys);
    List<string> keysToReturn = new List<string>(numberPossibleToGet);
    Random rand = new Random();
    for (int i = 0; i < numberPossibleToGet; i++)
    {
        int index = rand.Next(numberPossibleToGet - i) + i;
        keysToReturn.Add(keys[index]);
        keys[index] = keys[i];
    }
    return keysToReturn;
}
List<string> GetSomeKeysEnumerable(string[] cachedKeys, int requestedNumberToGet)
{
    Random rand = new Random();
    return TakeRandom(cachedKeys, requestedNumberToGet, rand).ToList();
}

一些迭代次数为10.000次的数字:

Function Name    Elapsed Inclusive Time Number of Calls
GetSomeKeys              6,190.66       10,000
GetSomeKeysEnumerable     15,617.04       10,000
GetSomeKeysSwapping        8,293.64       10,000

使用 HashSet 相反 哈希集 查找的速度比 List

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

DateTime breakoutTime = DateTime.Now.AddMilliseconds(5);
int length = cachedKeys.Length;

while (DateTime.Now < breakoutTime && keysToReturn.Count < numberPossibleToGet) {
    int i = rand.Next(0, length);
    while (!keysToReturn.Add(cachedKeys[i])) {
        i++;
        if (i == length)
            i = 0;
    }
}

考虑使用 Stopwatch 而不是 DateTime.Now 约会时间,现在 当你谈论毫秒的时候。

问题很可能在这里:

if (!keysToReturn.Contains(randomKey))
    keysToReturn.Add(randomKey);

这将需要迭代列表以确定键是否在返回列表中。但是,可以肯定的是,您应该尝试使用工具对此进行分析。此外,5ms在0.005秒时速度相当快,您可能需要增加它。