一种减少和限制集合组合搜索内存使用的算法

Question

我希望减少和限制用于比较集合中所有项目组合的内存占用，在这些组合中，集合可以增长到任意大小。我正在考虑将集合分割成更小的部分，但是由于所有的组合都是必需的，我看不出如何做到这一点而不需要内存中的所有组合。

如果我有A，B，C，D，E，F项，我需要比较所有不同的组合

  A B C D E F
A  
B x
C x x
D x x x
E x x x x
F x x x x x

诸若此类。这些集合通常是100到10,000个文档，其中的元数据需要使用各种启发式方法进行检查。

目前，我正在实现这一目标(不需要一次将所有项加载到内存中)，方法是在两个相同的嵌套数据库查询中迭代两次，每次使用一个游标在组合的两个维度上迭代。这在理论上是无限的，而且内存很少，但感觉有点浪费，因为我将查询每一项N+1时间(其中N是集合的大小)。当然，它强调了数据库。

这是当前的简单算法：

• 为set准备查询
• 而cursor.next A：
  • 为set准备查询，不包括A
  • 而cursor.next B：
    • A与B比较

​

​

这导致了AB，AC，AD，AE，AF，BA，BC，BD等序列，我只在内存中同时保存了两个文档，但是它有两个问题。首先，内部查询发生N次；如果我没有在查询中排除A，那将是相同的查询重新运行N次，这似乎是浪费。第二个问题是排列，所以我所做的工作是所需的两倍，并且不得不去推断结果。

我考虑了缓存项目，随着我的进展，但意识到它将只是增长到最终包含所有项目，无论如何，以完成所有组合。因此，这就引出了一个基本的想法，就是只选择一次整个集合到内存中，然后从一个数组中扫描组合。这很简单，但当然不是可伸缩的。

因此，是否有一个算法可以对集合中所有不同对的组合执行比较，方法是在任何时候仅使用集合的分区，这可以保证包含所有组合？

我不能天真地想出一个。如果你把它分成两半，你仍然需要在某个时候加载两个子集的组合。也许“所有的可能性”和“所有的公平”，但这只会减少一半的可伸缩性问题。

  B D F
B 
D x  
F x x  

然后

  A C E
A  
C x  
E x x 

但这错过了一半的组合。

我有一种感觉，理论上是不可能的，但不知道是否有一个聪明的数学诀窍。或者我错过了一些很明显的东西。

更新-问题编辑和希望澄清后，初步意见。

M给了我预生成组合对的“索引”的想法，然后我可以查询每一对。

我最初希望实现MicSim所说的批量大小中间地带的“甜蜜点”。因此，不是原子地在一个极端加载每一对，也不是在另一端加载整个集合，而是一些固定大小的批处理方法，以保持处理占用空间不变。

Answer 1

========================================== 更新

如果我正确理解了这个问题。为了减少内存使用，没有方法non-overlapping，将集合划分为独立的子集，因为按照定义，所有的东西都必须与其他的东西进行比较。因此，没有这样的切割可以分割集合。但是，通过使用组合，可以将影响降到最低，在每个实例的内存中只有2个活动文档(在每个实例中只有2个活动文档)，并且当下一个组合实际上引用不同的文档时更新文档(实际上很少有引用以前组合中的2个不同文档的，从一个组合到下一个，平均只有一个文档引用更改)。另外，通过使用下面的组合方法，process 可以在某个点停止并将最后的组合保存在磁盘上，并且在以后的某个时候从上恢复进程。因此，它可以是有效的，但在某种意义上仍然存在一种N+1 problem。关于组合方法，请参见下面的原始答案。

==================================================

有一些算法可以一个接一个地系统地生成组合，在这种情况下，您不需要同时将所有组合存储在内存中，而是在每个时刻只有一个活动。

该算法的工作方式是以一个组合作为输入，然后返回下一个组合(如按字典顺序排列)，直到最后一个组合到达。

从2中选择n (其中n >= 2 )的初始组合是[0,1]

注意：，如果n < 2没有从集合中选择2元素的组合，则使用小于2元素。

后续算法是(在python中)：

def next_combination( item, n, k ):
    MIN = 0
    MAX = k-1
    j = n-k
    i = MAX
    index = -1
    # find index to move
    while(MIN<=i and i<=MAX):
        if item[i] < j+i:
            index = i
            break
        i -= 1
    # adjust next indexes after the moved index
    if MIN<=index and index<=MAX:
        curr = item[index]+1
        j = n-k+index
        if curr == j:
            item[index] = curr
        elif curr < j:
            i = index
            while(MIN<=i and i<=MAX):
                item[i] = curr
                curr += 1
                i += 1
    else:
        # last item
        item = None
    return item

您使用的方法如下：

comb = [0, 1] # first combination
doc1 = None
doc2 = None
prevcomb = None
while (comb):
    # process combination
    # eg:
    # doc1 = docs.get(comb[0]) if (not prevcomb) or (prevcomb[0]!=comb[0]) else doc1
    # doc2 = docs.get(comb[1]) if (not prevcomb) or (prevcomb[1]!=comb[1]) else doc2
    # compare(doc1, doc2)
    # when finished, compute next combination untill last
    prevcomb = comb[:] # copy
    comb = next_combination(comb, n, 2) # get next combination in order

k=2，n=6在线测试

note2上述算法的时间复杂度是有效的，实际上是一种CAT算法(即每组合取常数平均时间)来生成整组组合。

note3对于特殊情况有更快的算法，例如n是小的。其中一种算法仅在32bit或64bit无符号整数上使用智能按位操作(因此仅适用于n <= 64)

note4上面的算法(对于python)也可以调整为使用iterator模式或generator模式(即yield)，但是在任何语言中都可以很容易地实现，即使是那些不支持生成器的语言。

note5 for k=2组合算法也可以使用嵌套循环来实现(因为在这种情况下它们是重合的)，即：

def next_combination2(n):
    for i in range(n-1):
        for j in range(i+1, n):
            yield [i, j]

note6如果使用另一种语言，请让我知道在可能的情况下用另一种语言重新发布算法(例如: php，javascript，c)