Python中对列表中的列表进行洗牌的有效方法

7

这似乎是一个以前应该已经问过的问题,但我找不到。以下是我的问题。

数据:
- 一个主list(长度约为16,000,000),其中包含最多500个项目的子列表str

目标:
- 高效地对主列表中的每个子列表进行洗牌。

我已经尝试了直接使用for-loop、列表推导式、pandas Series.apply()pandaralleldask dataframe的.apply().map_partition()方法。

for-loop需要大约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 是解决这个问题的方法!


2
你尝试过Pandas的Sample方法吗?https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.DataFrame.sample.html - alan.elkin
还有一件事:有时候,采样索引而不是主列表中的项目非常有用(并且更有效),这样您就可以通过洗牌后的索引访问列表。 - alan.elkin
1
我将尝试抽样并汇报结果。谢谢!希望提高速度所带来的收益可以抵消在列表和数据帧之间转换的成本。 - TerryH
1个回答

2
@TerryH - 你根本不需要对 `aListOfSTRINGs` 的 RAM 内存内容进行洗牌,只需生成一个 `np.random.permutation(len(aListOfListsOfSTRINGs[ith]))` 就足够了,以创建一个临时的、每个列表成本为仅约260 [us],花费尽可能少的时间,一个新的随机顺序,适合于第ith个 `aListOfSTRINGs` 的间接访问其 `str` 成员。(为什么要移动RAM I/O昂贵的数据,以便稍后有序“读取”它们,当在缓存服务块上使用组件的间接寻址ALAP“读取”时,根本不需要触摸任何数据?) 对于希望实现并行化的真实成本,您可以参考 帖子,其中包含交互式图形工具。
根据@user2357112支持Monica在下面的评论中所说,洗牌的目的是在aListOfSTRINGs内部进行,而不是aListOfListsOfSTRINGs上进行。请原谅我的错误。

"我能否更快地实现洗牌"

可以。很多。使用足够好的工具,可以实现150倍的速度提升 - 可以在2.5 [s]以下完成。

"... 我怎样可以使它的洗牌操作更有效率?"

原文:The in-place .shuffle() takes less than ~ 23 [s] on list( L ) over 16,000,000 items in plain Py2.7 tools
翻译:在普通的Py2.7工具中,就地执行的.shuffle()在对包含1600万个项目的list(L)上仅需要不到23秒。
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()方法在普通Py3.5工具中对包含1600万个项目的list(L)进行处理需要约48秒的时间。
$ 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-array,在有新成员aListOfSTRINGs进入时只需添加一个len(aListOfListsOfSTRINGs)
  • 享受非常快速和高效的原地aListOfORDINALs.shuffle(),在Py2.7下小于23秒或在Py3.5下小于50秒
  • 访问所有的str,方法为
    aListOfListsOfSTRINGs[aListOfORDINALs[Nth_L_inLoLoStr]][Nth_str_inLoStr],超快速地以O(1)的代价获取实际的str

你似乎把任务搞混了 - 这个问题是关于执行大约1600万次洗牌操作的,每次洗牌都会洗一个子列表。这不是关于洗牌大约1600万个元素的外部列表的问题。 - user2357112
正如上面的评论所建议的那样,任务是对16m个小列表进行洗牌,而不是对16m个项目的列表进行洗牌。然而,如果使用numpy进行洗牌更快,那么我可以尝试对索引数组进行洗牌,然后通过索引选择洗牌后的列表。 - TerryH
@TerryH - 你根本不需要对aListOfSTRINGs的RAM内存内容进行.shuffle()操作,只需生成一个np.random.permutation(len(aListOfListsOfSTRINGs[ith]))即可创建一个新的随机顺序,大小适合于第ith个aListOfSTRINGsstr成员的间接访问,每个列表的成本仅为**O(1)** ~ **260 [us]**,尽快花费,而无需将RAM I/O昂贵的数据移动到稍后某处以“读取”顺序,直到从缓存服务块中使用组件的间接寻址ALAP“读取”时才需要触摸任何数据。 - user3666197

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接