Web 技术研究所

我一直坚信着,Web 将会成为未来应用程序的主流

关于洗牌算法的装逼失败

  洗牌算法是一个经典的面试题,而有时候我会使用一些奇技淫巧来解决。比如在 JavaScript 中我可能会对 sort 方法的回调返回一个随机正负数。如果 sort 方法是冒泡排序的话,这么做是没问题的。然而 JavaScript 引擎也不是傻逼,肯定会使用更快的排序方式,所以 sort 无法洗牌。
  下面这坨代码是对 sort 方式洗牌和一般的洗牌方法做一个随机性测试和性能测试:
<script src="https://share.web-tinker.com/performance.js"></script> <script> let arr = [ 0, 0, 1000 ]; const alg1 = () => { let a = JSON.parse(JSON.stringify(arr)); return a.sort(() => Math.random() - 0.5); } const alg2 = () => { let a = JSON.parse(JSON.stringify(arr)); for (let i = 0; i < a.length; i++) { let j = Math.floor((a.length - i) * Math.random()) + i; let v = a[j]; a[j] = a[i] a[i] = v; } return a; } const check = alg => { const MAX = 1E5; let results = Array.from({ length: MAX }, alg); let sum = results.reduce((base, item) => { return base.map((value, index) => value + item[index]); }); return sum.map(value => (value / MAX).toFixed(2)); } document.write('<p>alg1: ' + check(alg1).join(' ') + '</p>'); document.write('<p>alg2: ' + check(alg2).join(' ') + '</p>'); </script> <style> p { word-spacing: 1em; } </style> <button>alg1()</button> <button>alg2()</button>
  从这个结果可以看出,使用 sort 来洗牌不仅结果的随机性有问题,连性能也不如手写的算法。结果是在下装逼失败了。
网名:
52.91.185.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^