本港台开奖现场直播 j2开奖直播报码现场
当前位置: 新闻频道 > IT新闻 >

码报:【j2开奖】算法可视化:把难懂的代码画进梵高的星空(4)

时间:2016-12-07 13:05来源:118图库 作者:www.wzatv.cc 点击:
每一条线代表一个数字,数字小向左倾斜,数字大就向右倾斜。(请注意,你可以对一组任何东西进行洗牌,不只是数字,但这种可视化编码对于显示元素

  每一条线代表一个数字,数字小向左倾斜,数字大就向右倾斜。(请注意,你可以对一组任何东西进行洗牌,不只是数字,但这种可视化编码对于显示元素的顺序很管用。它的灵感来自于Robert Sedgwick的《用C语言实现的算法》中的排序可视化。

  该算法把数组划分为两个部分,右半边是已洗牌区域(用黑色表示),左半边是待洗牌区域(用灰色表示)。每一步从左边的待洗牌区域随机选择一个元素并将其移动到右侧,已洗牌区域元素数量扩大了1个。左半边的初始顺序不必保留,这样给已洗牌区域的新元素提供了空间,该算法可以简单地讲元素交换到位。最终所有的元素都被洗牌,算法终止。

  如果Fisher–Yates是一个很好的算法,那么一个不好的算法是什么样的?

  ▼这是一个——

  //不要这么做!

  function shuffle(array) {

  return array.sort(function(a, b) {

  return Math.random() - .5; // ?_?

  });

  }

  这种方法利用排序通过指定随机比较器函数来洗牌。比较器定义元素的顺序。它使用参数a和b (要比较的数组中的两个元素),如果a小于b,则返回小于零的值,如果a大于b,则返回大于零的值,如果a和b相等,则返回0。比较器在排序期间重复调用。

  如果不给array.sort指定一个比较器,元素按照字典序列排序。

  在这里,比较器返回一个在-0.5和+0.5之间的随机数。假设这定义了一个随机顺序,那么排序会随机地混杂元素并实施好的洗牌。

  不幸的是,这个假设是有缺陷的。随机成对顺序(对于任何两个元素)不会为一组元素建立随机顺序。比较器必须遵守传递性:如果a> b和b> c,则a> c。但随机比较器返回一个随机值,违反了传递性,并导致array.sort的行为是未定义的!可能你会有运气,也可能没有。

  它怎么不好呢?我们可以通过可视化输出来试着回答这个问题:

  该算法不好的另一个原因是排序需要O(n lg n)时间,使得它显著地慢于只需要O(n)时间的Fisher-Yates算法。但是速度缺陷比偏差缺陷小。

  这可能看起来是随机的,因此你可能会得出结论,随机比较器洗牌足够好了,并不再关注偏差,看作是迂腐的。但看起来可能会误导!有许多对人眼来说看起来是随机的,但实际上是非随机的。

  这种欺骗表明可视化不是一个魔术棒。算法的单次运行显示不能有效地评估其随机性的质量。我们必须仔细设计一个可视化来解决手头的具体问题:算法的偏差是什么?

  为了显示偏差,我们必须首先定义它。一个定义是基于在洗牌之后索引i处的数组元素将在洗牌之后处于索引j的概率。如果算法是无偏的,则每个元素在洗牌结束后出现在每个索引处的概率相等,因此所有i和j的概率相同:1 / n,其中n是元素的数量。

  分析计算这些概率是困难的,因为它取决于知道使用的确切排序算法。但是根据经验计算是很容易的:我们简单地洗牌数千次,并计数索引j处元素i的出现次数。该概率矩阵的有效显示是矩阵图:

码报:【j2开奖】算法可视化:把难懂的代码画进梵高的星空

  矩阵的列(水平位置)表示在洗牌之前的元素的索引,而行(垂直位置)表示洗牌之后的元素的索引。概率用颜色编码:绿色单元表示正偏差,其中元素出现地比我们对无偏差算法的预期更频繁;同样红色单元表示负偏差,其发生频率低于预期。

  如上所示,Chrome中的随机比较器洗牌结果是令人惊讶的是平庸。部分阵列仅弱偏置。然而,它在对角线下方表现出强的正偏置,这表示将元素从索引i推到i + 1或i + 2的趋势。第一行、中间行和最后一行也有奇怪的行为,这可能是Chrome使用“三中值”的快速排序的结果。

  无偏的Fisher–Yates算法看上去是这样的:

码报:【j2开奖】算法可视化:把难懂的代码画进梵高的星空

  除了由于经验测量的少量噪声之外,在该矩阵中没有可见的规律。(如果需要,可以通过进行额外的测量来降低噪声。)

(责任编辑:本港台直播)
顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
栏目列表
推荐内容