随机访问Python中大型列表的所有成对组合

Question

背景:

我有44906项清单:large = [1, 60, 17, ...].我还有一台内存有限的个人电脑(8GB),运行Ubuntu 14.04.4 LTS.

目标:

我需要以large内存效率的方式找到所有成对组合,而不事先填充所有组合的列表.

问题和我到目前为止所做的:

当我使用itertools.combinations(large, 2)并尝试将其分配到列表时,我的内存会立即填满,而且性能会非常慢.这样做的原因是,两两组合的数量是这样n*(n-1)/2,其中n是列表中元素的个数.

n=44906出来的组合数量44906*44905/2 = 1008251965.包含这么多条目的列表太大而无法存储在内存中.我希望能够设计一个函数,以便我可以插入一个数字i来查找i此列表中数字的成对组合,以及以某种方式动态计算此组合的方法,而无需参考1008251965元素列表不可能存储在内存中.

我正在尝试做的一个例子:

假设我有一个数组 small = [1,2,3,4,5]

在我有代码的配置中,itertools.combinations(small, 2)将返回一个元组列表:

[(1, 2), # 1st entry
 (1, 3), # 2nd entry
 (1, 4), # 3rd entry
 (1, 5), # 4th entry
 (2, 3), # 5th entry
 (2, 4), # 6th entry 
 (2, 5), # 7th entry
 (3, 4), # 8th entry
 (3, 5), # 9th entry
 (4, 5)] # 10th entry

调用这样的函数:`find_pair(10)'将返回:

(4, 5)

给出了可能数组中的第10个条目,但没有预先计算整个组合爆炸.

问题是,我需要能够进入组合的中间,而不是每次从头开始,这似乎是迭代器的作用:

>>> from itertools import combinations
>>> it = combinations([1, 2, 3, 4, 5], 2)
>>> next(it)
(1, 2)
>>> next(it)
(1, 3)
>>> next(it)
(1, 4)
>>> next(it)
(1, 5)

因此,我希望能够通过一次调用检索第10次迭代返回的元组,而不必执行next()10次以获得第10个组合.

问题

是否有任何其他组合函数以这种方式处理大型数据集？如果没有,是否有一种很好的方法来实现这种行为的内存节省算法？

Answer 1

除了itertools.combinations不返回列表 - 它返回一个迭代器.这里:

>>> from itertools import combinations
>>> it = combinations([1, 2, 3, 4, 5], 2)
>>> next(it)
(1, 2)
>>> next(it)
(1, 3)
>>> next(it)
(1, 4)
>>> next(it)
(1, 5)
>>> next(it)
(2, 3)
>>> next(it)
(2, 4)

等等.它的内存效率非常高:每次调用只生成一对.

当然,这是可以编写返回函数n'th的结果,但与困扰(这将是更慢和更复杂)之前,你肯定你不能只使用combinations()它的方式设计中使用(即迭代它,而不是强迫它生成一个巨大的列表)？

Answer 2

如果您想要随机访问任何组合，您可以使用此函数返回叉积的相应下三角表示的索引

def comb(k):         
        row=int((math.sqrt(1+8*k)+1)/2)    
        column=int(k-(row-1)*(row)/2)  
        return [row,column]

例如使用你的小数组

small = [1,2,3,4,5]
length = len(small)
size = int(length * (length-1)/2)
for i in range(size):
    [n,m] = comb(i)
    print(i,[n,m],"(",small[n],",",small[m],")")

会给

0 [1, 0] ( 2 , 1 )
1 [2, 0] ( 3 , 1 )
2 [2, 1] ( 3 , 2 )
3 [3, 0] ( 4 , 1 )
4 [3, 1] ( 4 , 2 )
5 [3, 2] ( 4 , 3 )
6 [4, 0] ( 5 , 1 )
7 [4, 1] ( 5 , 2 )
8 [4, 2] ( 5 , 3 )
9 [4, 3] ( 5 , 4 )

显然，如果您的访问方法正确，其他方法会更实用。

另请注意，该comb函数与问题的大小无关。

正如 @Blckknght 在评论中所建议的，以获得与 itertools 版本更改为相同的顺序

for i in range(size):
        [n,m] = comb(size-1-i) 
        print(i,[n,m],"(",small[length-1-n],",",small[length-1-m],")")  


0 [4, 3] ( 1 , 2 )
1 [4, 2] ( 1 , 3 )
2 [4, 1] ( 1 , 4 )
3 [4, 0] ( 1 , 5 )
4 [3, 2] ( 2 , 3 )
5 [3, 1] ( 2 , 4 )
6 [3, 0] ( 2 , 5 )
7 [2, 1] ( 3 , 4 )
8 [2, 0] ( 3 , 5 )
9 [1, 0] ( 4 , 5 )