给定长度为n的列表，使用C#选择k个随机元素

本文关键字：选择 使用 元素 随机 列表 | 更新日期: 2023-09-27 18:24:06

我发现了这篇文章：

从链接列表中有效地选择一组随机元素

但这意味着，为了在样本中接近真正的随机性，我必须迭代所有元素，用随机数将它们放入内存，然后排序。我这里有一组非常大的项目（数百万）-有更有效的方法来解决这个问题吗？

给定长度为n的列表，使用C#选择k个随机元素

我建议简单地打乱元素，就像你在写一个修改过的Fisher Yates shuffle一样，但只需要打乱第一个k元素。例如：

public static void PartialShuffle<T>(IList<T> source, int count, Random random)
{
    for (int i = 0; i < count; i++)
    {
        // Pick a random element out of the remaining elements,
        // and swap it into place.
        int index = i + random.Next(source.Count - i);
        T tmp = source[index];
        source[index] = source[i];
        source[i] = tmp;
    }
}

调用此方法后，第一个count元素将是从原始列表中随机选取的元素。

请注意，我已经指定了Random作为参数，这样您就可以重复使用同一个参数。不过，要小心线程——有关更多信息，请参阅我关于随机性的文章。

看看这个扩展方法http://extensionmethod.net/csharp/ienumerable-t/shuffle.您可以添加Skip（）Take（）类型，将值从最终列表中分页出来。

如果元素可以在内存中，请先将它们放入内存

List<Element> elements = dbContext.Select<Element>();

现在你知道了元素的数量。创建一组唯一索引。

var random = new Random();
var indexes = new HashSet<int>();
while (indexes.Count < k) {
    indexes.Add(random.Next(elements.Count));
}

现在你可以从列表中读取元素

var randomElements = indexes.Select(i => elements[i]);

我假设DB包含唯一的元素。如果不是这种情况，您将不得不创建一个HashSet<Elements>，或者在从DB查询时附加.Distinct()。

更新

正如Patricia Shanahan所说，如果k与n相比很小，这种方法会很好地工作。如果不是这样，我建议选择一组n-k索引来排除

var random = new Random();
var indexes = new HashSet<int>();
IEnumerable<Element> randomElements;
if (k <= elements.Count / 2) {
    while (indexes.Count < k) {
        indexes.Add(random.Next(elements.Count));
    }
    randomElements = indexes.Select(i => elements[i]);
} else {
    while (indexes.Count < elements.Count - k) {
        indexes.Add(random.Next(elements.Count));
    }
    randomElements = elements
        .Select((e,i) => indexes.Contains(i) ? null : elements[i])
        .Where(e => e != null);
}
相关文章：