Knuth B洗牌算法
KnuthB的Python项目详细描述
Knuth B洗牌算法
破坏性的原地洗牌
反向顺序随机交换向后-一个缓存友好的就地洗牌算法。
Mac和Linux安装
$ pip install KnuthB
安装可能需要Cython和现代C++开发环境(Clang或GCC)。
洗牌测试
基本情况:随机洗牌
^{pr2}$测试用例:KnuthB.洗牌
>>> from KnuthB import shuffle as knuth
>>> a = [*range(10)]
>>> print(a)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> knuth(a)
>>> print(a)
[9, 1, 7, 8, 3, 2, 4, 6, 5, 0]
MonkeyScope计时器测试
基本情况:随机洗牌()
>>> from MonkeyScope import timer
>>> from random import shuffle as py_shuffle
>>> a = [*range(10000)]
>>> a = [*range(10000)]
>>> timer(py_shuffle, a, cycles=1)
Typical Timing: 10205985 ± 0 ns
测试用例:KnuthB.洗牌()
>>> from MonkeyScope import timer
>>> from KnuthB import shuffle as knuth
>>> a = [*range(10000)]
>>> timer(knuth, a, cycles=1)
Typical Timing: 679970 ± 0 ns
性能结果
Time to Shuffle 10,000 Items
- Random.shuffle: 10,205,985 ns (approx 10.2 milliseconds)
- KnuthB.shuffle: 679,970 ns (approx 0.7 milliseconds)
* Lower is better
- 项目
标签: