在.NET中模拟Python的random.choice

Question

Python的模块'random'有一个函数 random.choice

random.choice(seq)
从非空序列seq返回一个随机元素.如果seq是空的,加注IndexError.

我怎样才能在.NET中模拟这个？

public T RandomChoice<T> (IEnumerable<T> source)

---

编辑:几年前我听到这是一个面试问题,但今天这个问题在我的工作中自然而然地发生了.面试问题有限制

• '序列太长,无法保存到内存中'
• '你只能循环一次序列'
• '序列没有长度/计数方法'(ààNETIEnumerable)

Answer 1

要创建一个只迭代源一次的方法,并且不必分配内存来临时存储它,您可以计算已迭代的项数,并确定当前项应该是结果的概率:

public T RandomChoice<T> (IEnumerable<T> source) {
  Random rnd = new Random();
  T result = default(T);
  int cnt = 0;
  foreach (T item in source) {
    cnt++;
    if (rnd.Next(cnt) == 0) {
      result = item;
    }
  }
  return result;
}

当你在第一个项目时,它应该被使用的概率为1/1(因为这是你见过的唯一项目).当你在第二个项目时,概率是它应该替换第一个项目的1/2,依此类推.

这自然会使用更多的CPU,因为它为每个项目创建一个随机数,而不是像一个随机数来选择一个项目,正如dasblinkenlight指出的那样.您可以IList<T>像Dan Tao建议的那样检查源是否实现,并使用一个实现来使用这些功能来获取集合的长度并按索引访问项目:

public T RandomChoice<T> (IEnumerable<T> source) {
  IList<T> list = source as IList<T>;
  if (list != null) {
    // use list.Count and list[] to pick an item by random
  } else {
    // use implementation above
  }
}

注意:您应该考虑将Random实例发送到方法中.否则,如果您将方法调用得太近,则会获得相同的随机种子,因为种子是从当前时间创建的.

测试运行的结果,从包含0 - 9,1000000次的数组中选取一个数字,以显示所选数字的分布不会偏斜:

0: 100278
1: 99519
2: 99994
3: 100327
4: 99571
5: 99731
6: 100031
7: 100429
8: 99482
9: 100638

Answer 2

为避免迭代序列两次(一次用于计数,一次用于元素),在获取随机元素之前将序列保存在数组中可能是个好主意:

public static class RandomExt {
    private static Random rnd = new Random();
    public static T RandomChoice<T> (this IEnumerable<T> source) {
        var arr = source.ToArray();   
        return arr[rnd.Next(arr.Length)];
    }
    public static T RandomChoice<T> (this ICollection<T> source) {
        return source[rnd.Next(rnd.Count)];
    }
}

编辑Chris Sinclair实施了一个非常好的主意.