在.NET中模拟Python的random.choice [英] Emulate Python's random.choice in .NET

问题描述

Python的模块随机"具有函数 random.choice

Python's module 'random' has a function random.choice

random.choice(seq)
从非空序列seq返回一个随机元素.如果seq为空，则引发IndexError.

random.choice(seq)
Return a random element from the non-empty sequence seq. If seq is empty, raises IndexError.

如何在.NET中模拟它?

How can I emulate this in .NET ?

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

---

几年前，我作为一个采访问题听说过这个问题，但是今天，这个问题自然发生在我的工作中.面试问题有限制条件

---

I heard this as an interview question some years ago, but today the problem occurred naturally in my work. The interview question was stated with constraints

• 序列太长，无法保存到内存"
• 您只能在序列上循环一次"
• 序列没有长度/计数方法"(la .NET IEnumerable)

推荐答案

要创建一种仅对源进行一次迭代且无需分配内存来临时存储它的方法，请计算已迭代的项目数，并确定当前项目应为结果的可能性:

To make a method that iterates the source only once, and doesn't have to allocate memory to store it temporarily, you count how many items you have iterated, and determine the probability that the current item should be the result:

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，依此类推.

When you are at the first item, the probability is 1/1 that it should be used (as that is the only item that you have seen this far). When you are at the second item, the probability is 1/2 that it should replace the first item, and so on.

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

This will naturally use a bit more CPU, as it creates one random number per item, not just a single random number to select an item, as dasblinkenlight pointed out. You can check if the source implements IList<T>, as Dan Tao suggested, and use an implementation that uses the capabilities to get the length of the collection and access items by index:

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实例发送到方法中.否则，如果您两次调用该方法的时间间隔太近，则将获得相同的随机种子，因为该种子是从当前时间创建的.

Note: You should consider sending the Random instance into the method. Otherwise you will get the same random seed if you call the method two times too close in time, as the seed is created from the current time.

测试运行的结果，从包含0-9、1000000次的数组中选择一个数字，以显示所选数字的分布没有偏斜:

The result of a test run, picking one number from an array containing 0 - 9, 1000000 times, to show that the distribution of the chosen numbers is not skewed:

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

这篇关于在.NET中模拟Python的random.choice的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！