乐趣区

关于python:Python代码阅读第10篇随机打乱列表元素

jiezi

Python 代码浏览合集介绍：为什么不举荐 Python 初学者间接看我的项目源码

本篇浏览的代码实现了随机打乱列表元素的性能，将原有列表乱序排列，并返回一个新的列表（不扭转原有列表的程序）。

本篇浏览的代码片段来自于 30-seconds-of-python。

shuffle

from copy import deepcopy
from random import randint

def shuffle(lst):
  temp_lst = deepcopy(lst)
  m = len(temp_lst)
  while (m):
    m -= 1
    i = randint(0, m)
    temp_lst[m], temp_lst[i] = temp_lst[i], temp_lst[m]
  return temp_lst

# EXAMPLES
foo = [1,2,3]
shuffle(foo) # [2,3,1], foo = [1,2,3]

Python 实际上提供了和 shuffle 性能相似的规范库函数random.shuffle，不过这个函数会在原列表上进行打乱，扭转原列表的元素程序。当初咱们还是看下下面这段代码，如何实现乱序排列，如何实现返回新列表而不扭转原列表内容。

copy.deepcopy(x[, memo])

shuffle函数应用了深拷贝将原始列表拷贝了一份传递给了长期列表，后续的所有操作都是基于长期列表进行的，所以不会影响到原有的列表。

那么为什么不间接应用赋值语句呢？temp_lst = lst或者 temp_lst = lst[:]？因为 Python 的赋值语句实际上是将一个name 绑定到了对象上。下面的两种赋值语句实际上使得多个 name 绑定到了一个对象上。那么对于可变类型的对象而言，本身的扭转会反映到不同的 name 上。所以应用下面两种赋值语句都不能做到不影响原始列表。

>>> from copy import deepcopy
>>> o = [[1,2,3],4,5]
>>> c1 = o
>>> c2 = o[:]
>>> c3 = deepcopy(o)
>>> c1[2] = 6
>>> c2[0][0] = 0
>>> c3[0][1] = 0
>>> c3[1] = 6
>>> o
[[0, 2, 3], 4, 6]

Fisher-Yates algorithm

Fisher-Yates algorithm算法实现了洗牌算法。对于长度为 n 的列表，它的古代实现能够形容为以下伪代码：

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

这个算法在数学上的根本思维是不放回的随机从原始列表中取出元素，并将取出的元素按程序放入新的列表中。应用这种形式就实现了新列表元素程序的随机。这个算法的伪代码实现，优化了整体的效率，将元素的取出和放入新的数组，替换成了在原数组上将元素进行替换。

退出移动版