Math.Random的算法

8
这是一位面试官问的问题。我无法回答。
问题是,假设你想从给定的数组中选择一个随机数。 条件是不能按顺序选择任何内容并且不使用内置的Random函数。 我不知道。想知道这个Math.Random是如何为我们工作的?
我谷歌搜索了一下,并没有找到背后的实现/逻辑。
有人知道吗?

3
问题描述过于模糊。 - David
1
我不知道确切的算法,但它与本地时间有关(纳秒等)。 - Captain GouLash
2
请参阅:http://en.wikipedia.org/wiki/Pseudorandom_number_generator。同时,使用当前时间作为种子。 - ElKamina
1
好的。高层次的讨论,设计模式,软件架构...在会议或演示中都很好。但是在日常活动中,当需要高效的核心级别代码时,它们并不适用。随机数生成在计算机科学中非常重要,比MVVM/WinRT之类的东西更重要。作为一个软件人员,你不能忽视算法、运行时间复杂度、性能和类似的事情。 - Ajay
1
@Ajay 和 @Highscore,SOF 已经推出了一个很好的平台叫做 Chat。也请利用那个平台 :) - Billa
显示剩余17条评论
8个回答

22

到目前为止,已经有三个人告诉你要使用Ticks的最后一位数字来生成随机数。 这种方法是行不通的。 如果在紧密循环中这样做,你很快就会明白为什么这是一个坏主意。

这个问题没有被很好地提出。我喜欢在面试中问模糊的问题,因为这样可以了解候选人如何处理模糊情况。在这种情况下,我会立即反击并找出面试官所说的“随机”是什么意思。伪随机性是否足够好?是否有高质量的熵源可用?

一旦你澄清了问题,回答就应该更容易了。

问题归结为管理熵。如果你有一个非常弱的熵源——比如Ticks的值(不是最后一位数字,它毫无价值,而是整个值),那么你可以使用它来种子化一个伪随机数生成器。如果你有一个高质量的熵源,那么你可以直接使用它来生成随机比特。


3
@Thomas: 不,你的算法太糟糕了。尝试连续运行你的程序十次并查看结果。我得到的结果是:6、37、95、81、68、69、50、12、58、36——6、4、95、81、2、55、0、68、58、99——6、37、95、81、68、12、50、79、58、90……注意到什么奇怪的地方了吗?第一个数字总是六,第二个数字通常是37,第三个数字总是94,第四个数字总是81……这是极其糟糕的随机性 - Eric Lippert
第一次尝试,我有46、31、25、80、16、28、36、9、8、99... 顺便说一下,我们是在面试的情境下交谈,对吧? 如果你没有更多细节,那么你可能只想要一个线性分布,仅此而已。 如果你开始谈论熵,我猜这就是面试的结束了... - Thomas
3
@Thomas:连续做十次尝试。 - Eric Lippert
5
@ken2k: 你指出了你的推理中的谬误。“我们不知道这会返回什么”和“我们知道返回值是可靠随机分布的”是相反的,但你却将它们视为同义词。我们不能轻率地假设任何未知量都是随机分布的!它可能非常不随机。我们不知道,因此我们不应该假设分布恰好是我们想要的那个。 - Eric Lippert
2
@ken2k:我们必须区分外行人对“随机”的定义,基本上是“我不知道的东西”,和工程师对随机的定义,即一种固有的不可预测过程,产生的结果却在总体上可靠地符合特定的分布。一个值仅仅是不可预测还不够;它的分布必须在总体上符合某个模型才能真正算作是随机的。 - Eric Lippert
显示剩余8条评论

7

保证是随机的。(开玩笑):

void Main()
{
    Enumerable.Range(0, 10).Select(x => ComeOnItsKindaRandom(0, 10)).Dump();
}

public int ComeOnItsKindaRandom(int minValue, int maxValue)
{
    var query = "http://www.random.org/integers/?num=1&min={0}&max={1}&col=1&base=10&format=plain&rnd=new";
    var request = WebRequest.Create(string.Format(query, minValue, maxValue));
    var response = request.GetResponse();
    using(var sr = new StreamReader(response.GetResponseStream()))
    {
        var body = sr.ReadToEnd().Trim();
        return int.Parse(body);
    }
}

2
@HighCore 现在,现在,现在...唯一的要求是“条件是你不应该按顺序选择任何东西,也不应该使用内置的随机函数。” - 这个通过了! :) - JerKimball

5

如果您只想从数组中获取一个项,而不使用Random类,则可以使用带有未知值的模数函数,例如DateTime.Now.Ticks

string[] items = new[] { "1", "2", "3", "4", "5" };

// Modulo items.Lenth returns a value from 0 to Length - 1
int index = (int)(DateTime.Now.Ticks % items.Length);

Console.WriteLine(items[index]);

1
这个不起作用。在循环中尝试一下,你就会知道原因了。 - Eric Lippert
1
@EricLippert 这基本上就是我为什么说“一个项目”的原因。整个重点在于,您无法预测第一次调用DateTime.Now时返回的值。 - ken2k
此外,DateTime.Now.Ticks 倾向于(总是?)以 0 结尾,因此它经常可以被 2、5 和 10 整除。这几乎肯定会有利于根据数组长度返回相同的元素。编辑:在我的测试中,数组长度为 5 的索引始终返回 0,数组长度为 6 的索引始终选择 02 - Chris Sinclair
@ken2k 是的,我刚意识到这可能取决于平台或.NET实现。我只是想说,你需要对DateTime.Now.Ticks值进行更多微调,而不仅仅是直接按原样模数(例如,请参见Thomas的答案)。 - Chris Sinclair
@EricLippert 只有在调用之间的时间保持恒定时,它才会返回相同的数字。再次强调,我没有理解问题为“编写一个伪随机生成器”,而是“编写一种从此数组中返回一个(伪)随机元素的方法”。 - ken2k
显示剩余6条评论

4

I would use the

DateTime.Now.Tick 

例如,对于Math.Random(10),我只取最后两个数字。

或者你可以像下面这样取此刻的模数:

public static class MyMath
{
    private static int counter = 1;

    public static int Random(int max)
    {
        counter++;
        long ticks = DateTime.Now.Ticks;
        int result = Math.Abs((int) (ticks/counter)%max);
        return result;
    }
}

请看以下测试:

    [Test]
    public void test()
    {
        List<int> test = new List<int>();

        for (int i = 0; i < 10; i++)
        {
            test.Add(MyMath.Random(100));
        }

        Console.WriteLine("result:");
        foreach (int i in test)
        {
            Console.WriteLine();
        }
    }

当我得到一个由5个元素组成的数组时,我不知道这将如何工作。我会得到什么样的刻度和如何得到我的数字? - Billa
@Billa Datetime.Now.Tick 只是给你一个时间戳,一个长整型(数字),它非常精确地表示当你获取此属性时的时间,因此例如现在是:634994778252950613。它经常变化,非常适合生成随机数! - Thomas
5
这个算法很糟糕,多次运行时会产生高度非随机的结果。Ticks不适用于生成随机数。与处理器速度相比,它并不经常变化,即使它变化了,程序所做的工作量与Ticks的变化量之间存在着强烈的相关性。它根本就不是随机的;它与程序的行为紧密相关。正如你所期望的那样,它在计时程序。 - Eric Lippert
1
如果您想使用滴答声作为熵源,那么您最不应该使用的是低位,因为它们在程序的生命周期内不会改变。滴答声不是处理器的高性能计数器。正确的使用滴答声的方法是使用其中间位作为熵源来种植高质量的PRNG,例如Mersenne Twister。您只需要使用滴答声一次,而不是像您在这里一样持续不断地使用。 - Eric Lippert
那么在面试中你会提出什么建议呢?什么都不提出因为它不完美吗?我永远不会雇用你,我需要聪明的人,能够找到解决方案。而问这个问题,我并不期望完美的随机答案,因为你是对的,完美的随机答案不存在! - Thomas
显示剩余3条评论

1

这是一个用C语言实现的随机数示例。你可以尝试用C#重写它。

C语言的随机数:终于结束了? http://www.cse.yorku.ca/~oz/marsaglia-rng.html

它似乎质量非常高。

但在面试中编写此代码可能并不容易,但你肯定可以告诉他使用的思路。


0

只是一个想法,你可以使用 DateTime.Now.Ticks 中的最后一位数字来选择索引的基础。或者对相同的东西进行一些哈希函数。或者使用一个可以提供从辐射中测量出的随机数的 Web 服务。 Math.Random 只是从预定义的表中选择(确实如此,它并不是真正的随机)。


试着看一下Ticks的最后一位数字,你很快就会明白为什么这样做行不通。 - Eric Lippert
@EricLippert 我知道有很多零,这就是我说“最后之一”的原因。如果不清楚的话我很抱歉。 - David S.

0

我认为他们只是想知道你是否了解LCG(线性同余生成器)算法。

然而,它们背后的数学有些棘手,所以我怀疑他们不可能期望你能够脱口而出写一个。

但如果失败了,你难道不能像这样欺骗来生成一个随机索引吗?

int index = Guid.NewGuid().GetHashCode() % array.Length;


0

首先,伪随机数不仅仅是随机数,因为在计算形式下无法生成随机数序列,

大多数伪随机数生成器 PRNG 都采用以下形式:

在时间 0:R(0) = Random(Seed)

在时间 i:R(i) = Random(R(i-1));

其次,随机并不意味着您不知道第 i 次结果会是什么,而是该序列是强大的,并且很难猜测给定一系列结果的公式或种子

希望这有所帮助


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接