随机访问 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) 将 return 元组列表如下：

[(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)' 会 return:

(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)

因此，与其必须执行 next() 10 次才能获得第 10 个组合，我希望能够通过一次调用检索第 10 次迭代 returned 的元组。

问题

是否有任何其他组合函数以这种方式设计用于处理庞大的数据集？如果没有，是否有实现这种行为的内存节省算法的好方法？

Answer 1

除了 itertools.combinations 不是 return 列表 - 它 return 是一个迭代器。这里：

>>> 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)

等等。它非常节省内存：每次调用只生成一对。

当然是可以编写一个 return 是 n'th 结果的函数，但是在打扰之前（这会更慢并且更多参与），你确定你不能只使用设计的方式使用 combinations() （即迭代它，而不是强迫它产生一个巨大的列表）？

Answer 2

所以你有 44906 件物品。但是请注意，如果您按照示例中构建组合的方式构建组合，那么将有 44905 个组合，其中 large[0] 作为第一个数字。此外，i <= 44905 的组合 i 看起来像 (large[0], large[i]).

对于 44905 < i <= 89809，它看起来像 (large[1],large[i-44904])。

如果我没记错的话，这个模式应该继续 (large[j],large[i-(exclusive lower bound for j)+1])。你可以检查我的数学，但我很确定它是正确的。无论如何，您可以迭代找到这些下限（因此对于 j=0，它是 0，对于 j=1，它是 44905，等等）迭代应该很容易，因为您只需添加下一个降序数字：44905、44905+44904， 44905+44904+44903...

Answer 3

对于定义明确的创建对顺序，第一个和第二个元素的索引应与序列的 n 和长度相关。如果找到它们，您将能够实现常量时间性能，因为索引列表是 O(1) 操作。

伪代码如下所示：

def find_nth_pair(seq, n):
    idx1 = f1(n, len(seq))  # some formula of n and len(seq)
    idx2 = f2(n, len(seq))  # some formula of n and len(seq)
    return (seq[idx1], seq[idx2])

您只需要找到 idx1 和 idx2 的公式。

Answer 4

如果你想随机访问任何组合你可以使用这个函数来return叉积的相应下三角表示的索引

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 )

Answer 5

我从三角形排列开始，找到索引为 row 和 col[= 的列表成员的下标 k 29=]。然后我逆转了这个过程，从 k.

推导出 row 和 col
对于包含 N 项的列表 large，令

b = 2*N - 1

现在，要获得列表中的第 k 个组合...

row = (b - math.sqrt(b*b - 8*k)) // 2 col = k - (2*N - row + 1)*row / 2 kth_pair = large[row][col]

这允许您访问组合列表的任何成员而无需生成该列表。

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

Random access over all pair-wise combinations of large list in Python

python

combinations

list

combinatorics

large-data