在C#中从List<T>中选择N个随机元素

Question

在C#中从List<T>中选择N个随机元素

c#algorithmcollectionsrandomelement

208

我需要一个快速的算法从一个通用列表中选择5个随机元素。例如，我想从一个List<string>中获取5个随机元素。

- JC Grubbs

15

“随机”一词是否包含重复选择？换句话说，同一个元素是否可以被多次选中？（真正的随机）或者一旦选择了一个元素，该元素是否应从可用池中删除，不能再次选择？ - Pretzel

你只是洗牌并取前N个..为什么这里会有这么多讨论？ - Fattie

被接受的答案并非完全错误，甚至不算错。请参见此处：https://dev59.com/N5Pfa4cB1Zd3GeqPEIJc。即使未提及，用例考虑也不是无关紧要的。 - uckelman

嗨@uckelman，干杯，已经有大量的讨论指出了明显的问题；蓄水池抽样仅在某些领域（实际上，在维基百科文章的第二个当前句子中完全概述）中有用。所提出的问题特别是关于C#中的List<string>，用户特别想要一个快速简单的解决方案。（显然，答案是排序并取五个。如果您在领域内做任何其他事情，那将是极其糟糕的工程。请注意，当然可以编造... - Fattie

...正在使用Hadoop和GPU或其他技术，然后在那个领域里，您需要分析哪种（正如您所说）蓄水池抽样方法（其中包括许多方法，并且仍在不断研究中）最好。更具体地说，看看选定的“答案”。假设这是一个实际项目，比如Nintendo的游戏团队之类的。场地上有“40”辆坦克，必须随机选择5辆。其中一名程序员开始编写该解决方案-他们只会被立即解雇！天哪。不当的工程设计是极其糟糕的工程设计。 - Fattie

显示剩余9条评论

35个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cardinal · Answer 1

public static IEnumerable<T> GetRandom<T>(IList<T> list, int count, Random random)
    {
        // Probably you should throw exception if count > list.Count
        count = Math.Min(list.Count, count);

        var selectedIndices = new SortedSet<int>();

        // Random upper bound (exclusive)
        int randomMax = list.Count;

        while (selectedIndices.Count < count)
        {
            int randomIndex = random.Next(0, randomMax);

            // skip over already selected indices
            foreach (var selectedIndex in selectedIndices)
                if (selectedIndex <= randomIndex)
                    ++randomIndex;
                else
                    break;

            yield return list[randomIndex];

            selectedIndices.Add(randomIndex);
            --randomMax;
        }
    }

内存： ~count
时间复杂度：O(count²)

- TXNPRS · Answer 2

简短易懂，希望能帮到大家！

if (list.Count > maxListCount)
{
    var rndList = new List<YourEntity>();
    var r = new Random();
    
    while (rndList.Count < maxListCount)
    {
        var addingElement = list[r.Next(list.Count)];

        //element uniqueness checking
        //choose your case
        //if (rndList.Contains(addingElement))
        //if (rndList.Any(p => p.Id == addingElement.Id))
            continue;
    
        rndList.Add(addingElement);
    }
    
    return rndList;
}

- Tobias Hertkorn · Answer 3

这比人们想象的要难得多。请参阅 Jeff 的优秀文章“洗牌”。

我写了一篇非常简短的文章，其中包括 C# 代码：
返回给定数组的 N 个元素的随机子集

- Kuba Szostak · Answer 4

public static IEnumerable<TItem> RandomSample<TItem>(this IReadOnlyList<TItem> items, int count) 
{
    if (count < 1 || count > items.Count)
    {
        throw new ArgumentOutOfRangeException(nameof(count));
    }
    List<int> indexes = Enumerable.Range(0, items.Count).ToList();
    int yieldedCount = 0;

    while (yieldedCount < count)
    {
        int i = RandomNumberGenerator.GetInt32(indexes.Count);
        int randomIndex = indexes[i];
        yield return items[randomIndex];

        // indexes.RemoveAt(i);                  // Avoid removing items from the middle of the list
        indexes[i] = indexes[indexes.Count - 1]; // Replace yielded index with the last one
        indexes.RemoveAt(indexes.Count - 1);     
        yieldedCount++;
    }
}

- Wolf5 · Answer 5

当处理大型列表时（每个元素的操作成本很高），并且如果您可以接受可能存在重复项，则可以使用LINQ：

new int[5].Select(o => (int)(rnd.NextDouble() * maxIndex)).Select(i => YourIEnum.ElementAt(i))

针对我的使用，我有一个包含100,000个元素的列表，由于它们是从数据库中提取出来的，与整个列表上的随机数相比，我将时间减少了一半（或更多）。

拥有一个大列表将大大降低重复的概率。

- Lesmian · Answer 6

我想分享我的方法。看了其他答案后，我在想我们是否真的需要跟踪已选择的项目以保持结果的唯一性。通常这会减慢算法的速度，因为如果你偶然选择了同一个项目，你需要重复抽取。所以我想出了一些不同的方法。如果您不介意修改输入列表，您可以一次性打乱项目，使选择的项目最终出现在列表的开头。

因此，在每次迭代中，您选择一个项目，然后将其切换到列表的前面。结果，您最终得到了随机项目在输入列表的开头。这样做的缺点是输入列表的顺序被修改了，但您不需要重复抽取，结果是唯一的。不需要任何额外的内存分配等。即使对于像随机选择列表中的所有项目这样的边缘情况，它也非常快速。

以下是代码：

public IEnumerable<T> Random_Switch<T>(IList<T> list, int needed)
{
    for (int i = 0; i < needed; i++)
    {
        var index = _rnd.Next(i, list.Count);
        var item = list[index];
        list[index] = list[i];
        list[i] = item;
    }
    
    return list.Take(needed);
}

我也参考了@Leaky的答案进行了一些基准测试，以下是结果：

|             Method | ListSize | SelectionSize |        Mean |       Error |      StdDev |      Median |   Gen0 | Allocated |
|------------------- |--------- |-------------- |------------:|------------:|------------:|------------:|-------:|----------:|
| Test_IterateSelect |       50 |             5 |    662.2 ns |    13.19 ns |    27.54 ns |    660.9 ns | 0.0477 |     200 B |
| Test_RandomIndices |       50 |             5 |    256.6 ns |     5.12 ns |    12.86 ns |    254.0 ns | 0.0992 |     416 B |
|   Test_FisherYates |       50 |             5 |    405.4 ns |     8.05 ns |    17.33 ns |    401.7 ns | 0.1407 |     590 B |
|  Test_RandomSwitch |       50 |             5 |    152.8 ns |     2.91 ns |     4.87 ns |    153.4 ns | 0.0305 |     128 B |

| Test_IterateSelect |       50 |            10 |    853.8 ns |    17.07 ns |    29.44 ns |    853.9 ns | 0.0687 |     288 B |
| Test_RandomIndices |       50 |            10 |    530.8 ns |    10.63 ns |    28.93 ns |    523.7 ns | 0.1812 |     760 B |
|   Test_FisherYates |       50 |            10 |    862.8 ns |    17.09 ns |    38.92 ns |    859.2 ns | 0.2527 |    1057 B |
|  Test_RandomSwitch |       50 |            10 |    267.4 ns |     5.28 ns |    13.81 ns |    266.4 ns | 0.0343 |     144 B |

| Test_IterateSelect |       50 |            25 |  1,195.6 ns |    23.58 ns |    46.54 ns |  1,199.1 ns | 0.1049 |     440 B |
| Test_RandomIndices |       50 |            25 |  1,455.8 ns |    28.81 ns |    58.20 ns |  1,444.0 ns | 0.3510 |    1472 B |
|   Test_FisherYates |       50 |            25 |  2,066.7 ns |    41.35 ns |    85.40 ns |  2,049.0 ns | 0.4463 |    1869 B |
|  Test_RandomSwitch |       50 |            25 |    610.0 ns |    11.90 ns |    20.83 ns |    610.5 ns | 0.0496 |     208 B |

| Test_IterateSelect |       50 |            50 |  1,436.7 ns |    28.51 ns |    61.37 ns |  1,430.1 ns | 0.1717 |     720 B |
| Test_RandomIndices |       50 |            50 |  6,478.1 ns |   122.70 ns |   247.86 ns |  6,488.7 ns | 0.7248 |    3048 B |
|   Test_FisherYates |       50 |            50 |  3,428.5 ns |    68.49 ns |   118.15 ns |  3,424.5 ns | 0.5455 |    2296 B |
|  Test_RandomSwitch |       50 |            50 |  1,186.8 ns |    23.38 ns |    48.81 ns |  1,179.4 ns | 0.0725 |     304 B |

| Test_IterateSelect |      500 |             5 |  4,374.6 ns |    80.43 ns |   107.37 ns |  4,362.9 ns | 0.0458 |     200 B |
| Test_RandomIndices |      500 |             5 |    252.3 ns |     5.05 ns |    13.21 ns |    251.3 ns | 0.0992 |     416 B |
|   Test_FisherYates |      500 |             5 |    398.0 ns |     7.97 ns |    18.48 ns |    399.3 ns | 0.1411 |     592 B |
|  Test_RandomSwitch |      500 |             5 |    155.4 ns |     3.10 ns |     7.24 ns |    155.0 ns | 0.0305 |     128 B |

| Test_IterateSelect |      500 |            10 |  4,950.1 ns |    96.72 ns |   150.58 ns |  4,942.7 ns | 0.0687 |     288 B |
| Test_RandomIndices |      500 |            10 |    490.0 ns |     9.70 ns |    20.66 ns |    490.6 ns | 0.1812 |     760 B |
|   Test_FisherYates |      500 |            10 |    805.2 ns |    15.70 ns |    20.96 ns |    808.2 ns | 0.2556 |    1072 B |
|  Test_RandomSwitch |      500 |            10 |    254.1 ns |     5.09 ns |    13.31 ns |    253.6 ns | 0.0343 |     144 B |

| Test_IterateSelect |      500 |            25 |  5,785.1 ns |   115.19 ns |   201.74 ns |  5,800.2 ns | 0.0992 |     440 B |
| Test_RandomIndices |      500 |            25 |  1,123.6 ns |    22.31 ns |    53.03 ns |  1,119.6 ns | 0.3510 |    1472 B |
|   Test_FisherYates |      500 |            25 |  1,959.1 ns |    38.82 ns |    91.51 ns |  1,971.1 ns | 0.4807 |    2016 B |
|  Test_RandomSwitch |      500 |            25 |    601.1 ns |    11.83 ns |    23.63 ns |    599.8 ns | 0.0496 |     208 B |

| Test_IterateSelect |      500 |            50 |  6,570.5 ns |   127.03 ns |   190.13 ns |  6,599.8 ns | 0.1678 |     720 B |
| Test_RandomIndices |      500 |            50 |  2,199.6 ns |    43.23 ns |    73.41 ns |  2,198.6 ns | 0.7286 |    3048 B |
|   Test_FisherYates |      500 |            50 |  3,830.0 ns |    76.33 ns |   159.33 ns |  3,809.9 ns | 0.9842 |    4128 B |
|  Test_RandomSwitch |      500 |            50 |  1,150.7 ns |    22.60 ns |    34.52 ns |  1,156.7 ns | 0.0725 |     304 B |

| Test_IterateSelect |     5000 |             5 | 42,833.1 ns |   779.35 ns | 1,463.80 ns | 42,758.9 ns |      - |     200 B |
| Test_RandomIndices |     5000 |             5 |    248.9 ns |     4.95 ns |     9.29 ns |    248.8 ns | 0.0992 |     416 B |
|   Test_FisherYates |     5000 |             5 |    388.9 ns |     7.79 ns |    17.90 ns |    387.0 ns | 0.1411 |     592 B |
|  Test_RandomSwitch |     5000 |             5 |    153.8 ns |     3.10 ns |     6.41 ns |    154.7 ns | 0.0305 |     128 B |

| Test_IterateSelect |     5000 |            10 | 46,814.2 ns |   914.35 ns | 1,311.33 ns | 46,822.7 ns | 0.0610 |     288 B |
| Test_RandomIndices |     5000 |            10 |    498.9 ns |    10.01 ns |    28.56 ns |    491.1 ns | 0.1812 |     760 B |
|   Test_FisherYates |     5000 |            10 |    800.1 ns |    14.44 ns |    29.83 ns |    796.3 ns | 0.2556 |    1072 B |
|  Test_RandomSwitch |     5000 |            10 |    271.6 ns |     5.45 ns |    15.63 ns |    269.2 ns | 0.0343 |     144 B |

| Test_IterateSelect |     5000 |            25 | 50,900.4 ns | 1,000.71 ns | 1,951.81 ns | 51,068.5 ns | 0.0610 |     440 B |
| Test_RandomIndices |     5000 |            25 |  1,112.7 ns |    20.06 ns |    30.63 ns |  1,114.6 ns | 0.3510 |    1472 B |
|   Test_FisherYates |     5000 |            25 |  1,965.9 ns |    38.82 ns |    62.68 ns |  1,953.2 ns | 0.4807 |    2016 B |
|  Test_RandomSwitch |     5000 |            25 |    610.7 ns |    12.23 ns |    20.76 ns |    613.6 ns | 0.0496 |     208 B |

| Test_IterateSelect |     5000 |            50 | 52,062.6 ns | 1,031.59 ns | 1,694.93 ns | 51,882.6 ns | 0.1221 |     720 B |
| Test_RandomIndices |     5000 |            50 |  2,203.7 ns |    43.90 ns |    87.67 ns |  2,197.9 ns | 0.7286 |    3048 B |
|   Test_FisherYates |     5000 |            50 |  3,729.2 ns |    73.08 ns |   124.10 ns |  3,701.8 ns | 0.9842 |    4128 B |
|  Test_RandomSwitch |     5000 |            50 |  1,185.1 ns |    23.29 ns |    39.54 ns |  1,186.5 ns | 0.0725 |     304 B |

我猜如果你真的需要保持输入列表不变，你可以存储被交换的索引并在函数返回之前恢复顺序，但这当然会导致额外的分配。

- Kristofer · Answer 7

这是我的方法（完整文本在此http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html）。

它应该以O(K)的时间运行，而不是O(N)，其中K是所需元素的数量，N是要选择的列表的大小：

public <T> List<T> take(List<T> source, int k) {
 int n = source.size();
 if (k > n) {
   throw new IllegalStateException(
     "Can not take " + k +
     " elements from a list with " + n +
     " elements");
 }
 List<T> result = new ArrayList<T>(k);
 Map<Integer,Integer> used = new HashMap<Integer,Integer>();
 int metric = 0;
 for (int i = 0; i < k; i++) {
   int off = random.nextInt(n - i);
   while (true) {
     metric++;
     Integer redirect = used.put(off, n - i - 1);
     if (redirect == null) {
       break;
     }
     off = redirect;
   }
   result.add(source.get(off));
 }
 assert metric <= 2*k;
 return result;
}

- Mushroomator · Answer 8

>= .NET 8: GetItems<T>() 在.NET 8中（目前仍处于预览阶段），我们可以通过以下方法之一来解决这个问题，这是一个内置的方法。

Random.GetItems<T>()，它不是加密安全的，但速度快。
RandomNumberGenerator.GetItems<T>()，它使用加密安全的随机数生成器来选择项目。

该函数接受一个Array<T>或Span<T>，并返回一个选择的元素数组或写入到目标 Span（请参阅重载）。

var strings = new List<string>
{
    "a",
    "b",
    "c"
};
var numberOfStringsToSelect = 2;
var randomStrings = Random.Shared.GetItems<string>(CollectionsMarshal.AsSpan(strings), numberOfStringsToSelect);
Console.WriteLine(string.Join(", ", randomStrings));

我正在使用CollectionsMarshal.AsSpan()来从List<T>创建一个Span<T>。使用这种方法时，您不应该添加/删除列表中的任何项。或者，您可以将列表转换为数组，并将该数组传递给GetItems<T>()。

- hitec · Answer 9

最近我在项目中使用了类似于Tyler的第一点的想法来实现这个功能。
我加载了一堆问题并随机选择了五个。排序是通过使用IComparer实现的。
所有问题都被加载到QuestionSorter列表中，然后使用List的Sort函数进行排序，并选择前k个元素。

    private class QuestionSorter : IComparable<QuestionSorter>
    {
        public double SortingKey
        {
            get;
            set;
        }

        public Question QuestionObject
        {
            get;
            set;
        }

        public QuestionSorter(Question q)
        {
            this.SortingKey = RandomNumberGenerator.RandomDouble;
            this.QuestionObject = q;
        }

        public int CompareTo(QuestionSorter other)
        {
            if (this.SortingKey < other.SortingKey)
            {
                return -1;
            }
            else if (this.SortingKey > other.SortingKey)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
    }

使用方法：

    List<QuestionSorter> unsortedQuestions = new List<QuestionSorter>();

    // add the questions here

    unsortedQuestions.Sort(unsortedQuestions as IComparer<QuestionSorter>);

    // select the first k elements

- apdnu · Answer 10

这种方法不如被接受的解决方案那么优雅和高效，但编写起来很快。首先随机排列数组，然后选择前K个元素。在Python中，

import numpy

N = 20
K = 5

idx = np.arange(N)
numpy.random.shuffle(idx)

print idx[:K]