在 Python 中的列表中混洗列表的有效方法

Question

好像以前应该问过的问题，但是我找不到。所以就到这里了。

数据：
-list子列表的主（长度 ~= 16,000,000）（每个长度最多 500 个项目）str

目标：
- 有效地打乱主列表中的每个子列表。

我已经尝试了直for-loop，列表理解，熊猫Series.apply()，pandarallel和dask数据帧.apply()和.map_partition()方法。

一个for循环大约需要15 分钟。
pd.series.apply(), dask.series.apply(), 和dask.series.map_partition()所有人都设法做到了6 分钟多一点。

我的问题是“我可以更快地实现改组吗”？制作新副本或原地改组都是可以接受的。

以下是我的尝试：

def normal_shuffle(series):
    output = series.tolist()
    length = len(output)
    for i in range(length):
        random.Random().shuffle(output[i])
    return output

def shuffle_returned(a_list):
    new_list = a_list
    random.shuffle(new_list)
    return new_list

def shuffle_partition(a_partition):
    return a_partition.apply(shuffle_returned)

%time shuffled_for = normal_shuffle(test_series)
%time shuffled_apply = test_series.apply(shuffle_returned)

pandarallel.initialize(progress_bar=False, nb_workers=8)
%time shuffled_parallel_apply = test_series.parallel_apply(shuffle_returned)

test_ddf = ddf.from_pandas(test_series, npartitions=16)
test_ddf = test_ddf.reset_index(drop=True)

shuffled_ddf = test_ddf.apply(shuffle_returned, meta="some_str")
%time shuffled_ddf.persist()

shuffled_by_parttion_ddf = test_ddf.map_partitions(shuffle_partition, meta="productId")
%time shuffled_by_parttion_ddf.persist()

现在我尝试使用 dask 分布式来查看，如果我能以某种方式错开模型训练和数据混洗，使训练时间和混洗时间重叠并实现更好的整体时间效率。

我非常感谢有关如何使其改组操作更有效的任何反馈或建议。

---

更新

尝试了一些建议后，结果证明以下是我可以实现的最快速度，这也非常简单！

%time [np.random.shuffle(x) for x in alist]

CPU times: user 23.7 s, sys: 160 ms, total: 23.9 s
Wall time: 23.9 s

单线程 numpy 是这里的方法，似乎！

Answer 1

@TerryH - 你根本不需要.shuffle()RAM 内存内容aListOfSTRINGs，它应该足以生成一个，np.random.permutation( len( aListOfListsOfSTRINGs[ ith ] ) )以便创建临时的，成本为O(1)每个260 [us]列表，花费 ALAP，一个新的随机顺序，对吧- 大小用于间接访问str- 第 i 个 - 的成员aListOfSTRINGs
_{（为什么要移动 RAM-I/O 昂贵的数据以便稍后在不需要触及任何数据时按顺序“读取”，直到 ALAP“读取”使用组件的间接寻址从缓存提供的块中获取？）}

对于希望并行的现实世界成本，您可能会喜欢这篇带有交互式图形工具的文章。

_{正如@user2357112 支持下面评论的 Monica，洗牌的目的是在内部而不是在Mea Culpa上
进行 aListOfSTRINGsaListOfListsOfSTRINGs}

问：“我可以更快地实现洗牌”吗？

是的。很多。...时间-使用足够合适的工具可以实现远远低于150 x 2.5 [s]

问：“……如何 _{才能使其洗牌操作更加高效}？”

在普通 Py2.7 工具中，就地操作需要的时间.shuffle()少于16,000,000 多个项目~ 23 [s]list( L )

from zmq import Stopwatch; aClk = Stopwatch() #_______________________ a [us] Stopwatch
pass;    import random

#_____________L creation ~ 2.7 [s]___________________________________________
aClk.start(); L = [ strID for strID in xrange( int( 16E6 ) ) ]; aClk.stop()
2721084

print L[:5] #___________________________________________________________proof
[0, 1, 2, 3, 4]

#_____________random.shuffle( L )______________________________________+proof
aClk.start(); random.shuffle( L ); aClk.stop(); print "0:5\t", L[:5]
21473261
0:5     [13868243, 13087869, 13207292, 9344202, 1853783]

#_____________random.shuffle( L )______________________________________+proof
aClk.start(); random.shuffle( L ); aClk.stop(); print "0:5\t", L[:5]
22573922
0:5     [837396, 15032889, 10942767, 14571341, 4867854]

#_______________________________________________________________________proof
>>> len( L )
16000000

该就地.shuffle()接管了~ 48 [s]普通list( L )Py3.5 工具中超过 16,000,000 个项目。

$ conda activate py3
$ python
...
aClk.start(); L = [ strID for strID in  range( int( 16E6 ) ) ]; aClk.stop()
1959052

#_____________random.shuffle( L )______________________________________+proof
aClk.start(); random.shuffle( L ); aClk.stop(); print( "0:5\t", L[:5] )
45104806
0:5     [15744525, 10635923, 14530509, 10535840, 1465987]

#_____________random.shuffle( L )______________________________________+proof
aClk.start(); random.shuffle( L ); aClk.stop(); print( "0:5\t", L[:5] )
47139358
0:5     [884437, 15420153, 9957947, 8118734, 11960914]

让我们来提升真实性能：

import numpy as np

#____________L_as_a32______________16E6________________________~ 74 [ms]
>>> aClk.start(); a32 = np.arange( 16E6, dtype = np.int32 ); aClk.stop()
74054

#_____________np.random.shuffle( a32-bit )______________________________+proof
aClk.start(); np.random.shuffle( a32 ); aClk.stop(); print "0:5\t", a32[:5]
2400786
0:5     [ 2487493 14646705 13717283  5602561  7934593]

aClk.start(); np.random.shuffle( a32 ); aClk.stop(); print "0:5\t", a32[:5]
2368381
0:5     [ 4841042 12882529 12298351  2198866  7054284]

aClk.start(); np.random.shuffle( a32 ); aClk.stop(); print "0:5\t", a32[:5]
2369011
0:5     [14595649  7239135  3339593  9517600  6506681]

#_____________np.random.shuffle( a64-bit )______________________________+proof
aClk.start(); np.random.shuffle( a64 ); aClk.stop(); print "0:5\t", a64[:5]
2424487
0:5     [ 3234133  9224551   971604 13027484   806393]

aClk.start(); np.random.shuffle( a64 ); aClk.stop(); print "0:5\t", a64[:5]
2386873
0:5     [ 3212124 10644428  8192909  2234984 13103406]

aClk.start(); np.random.shuffle( a64 ); aClk.stop(); print "0:5\t", a64[:5]
2376065
0:5     [ 5624301  7741070  8859092 12287465 11721315]

如果确实要获得终极性能：

• str按原样维护所有数据，存储在aListOfSTRINGs
• 每个新aListOfSTRINGs追加都以恒定成本添加O(1)到非重新洗牌、线性增长、恒定顺序存储中 -aListOfListsOfSTRINGs
• 与其支付非常高的内存 I/O 成本来洗牌存储，aListOfListsOfSTRINGs不如维护一个aListOfORDINALs（无论是普通数组list还是数组，只要有新成员加入，numpy只需附加一个）len( aListOfListsOfSTRINGs )aListOfSTRINGs
• 享受非常快速和非常高效的就地体验aListOfORDINALs.shuffle()，远低于23 [s]Py2.7 或< 50 [s]Py3.5
• 以超快的速度访问所有str-s以获得实际的-s
  aListOfListsOfSTRINGs[aListOfORDINALs[Nth_L_inLoLoStr]][Nth_str_inLoStr]O(1)str