我想减少并限制在比较集合中所有项目组合时使用的内存占用,因为集合可以增长到任何大小。我本来想把这一套分成更小的部分,但由于需要所有的组合,我不知道如何做到这一点,而不在某个时候需要记忆中的所有组合。
例如,如果我有项目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到10000个文档,具有要用各种启发式方法检查的元数据。
我目前正在实现这一点(不需要一次将所有项目加载到内存中),方法是在两个相同的嵌套数据库查询中对集合进行两次迭代,每个查询中使用一个游标在组合的两个维度上迭代。理论上,这在规模上是无限的,占用的内存很少,但感觉有点浪费,因为我将对每个项目进行N+1次查询(其中N是集合的大小)。当然,它有点强调数据库。
这就是目前的简单算法:
- 为集合准备查询
- 而cursor.next A:
- 为集合准备查询,不包括A
- 而cursor.next B:
- 比较A和B
这导致序列AB、AC、AD、AE、AF、BA、BC、BD等。我一次只在内存中保存两个文档,但它有两个问题。首先,内部查询发生N次。如果我没有在查询中排除A,那么这将是同一个查询重新运行N次,这看起来很浪费。第二个问题是排列,所以我要做的工作是需要的两倍,而且必须对结果进行重复数据消除。
我想过在前进的过程中缓存这些项目,但意识到它最终会包含所有项目,从而完成所有组合。因此,这就引出了一个完整的循环,即只需将整个集合一次选择到内存中,然后从一个数组中扫描组合。这很简单,但当然不可扩展。
那么,是否有一种算法可以通过在任何时候只使用集合的分区来对集合中不同对的所有组合进行比较,从而保证其总和覆盖所有组合
我天真地想不出一个。例如,如果你把它分成两半,你仍然需要在某个时候加载两个子集的组合。也许"万无一失"one_answers"平分秋色",但这只会使可扩展性问题减半。
B D F
B
D x
F x x
然后
A C E
A
C x
E x x
但这错过了一半的组合。
我觉得这在理论上是不可能的,但我想知道是否有一个聪明的数学技巧。或者我错过了一些非常明显的东西。
更新-问题经过编辑,希望在初步评论后澄清。
Nikos.M给了我预先生成组合对的"索引"的想法,然后我可以查询每一对。
我最初希望实现MicSim所说的批量大小中间地带的"最佳点"。因此,不是在一个极端原子性地加载每一对,也不是在另一端加载整个集合,而是一些固定大小的批处理方法,以保持处理足迹不变。
更新====================================
如果我理解正确的话。没有方法将集合划分为不重叠的独立子集,以减少内存使用,因为根据定义,所有内容都必须与其他内容进行比较。所以没有这样的割可以分割集合。然而,通过使用组合可以将影响最小化,在每个实例的内存中只有两个活动文档,当下一个组合实际引用不同的文档时更新文档(引用上一个组合中的两个不同文档实际上很少见,从一个组合到下一个,平均只有一个文档引用发生变化)。此外,通过使用以下组合方法,进程可以在某个时间点停止并将最后一个组合保存在磁盘上,然后在稍后的某个时间从上的该时间点恢复该进程。因此,它可以是有效的,但在某种意义上仍然存在一种N+1 problem
。关于组合方法,请参阅下面的原始答案。
=================================================
有一些算法可以系统地一个接一个地生成组合,其中您不需要一次将所有组合存储在内存中,而是在每个时刻只有一个活动组合。
该算法的工作原理是输入一个组合,然后返回下一个组合(如按字典顺序),直到到达最后一个。
从n
(其中n >= 2
)中选择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 的在线测试
注意2上述算法的时间复杂度是有效的,事实上它是一种CAT算法(即每个组合需要恒定的平均时间)来生成整个组合集。
note3对于特殊情况,例如n很小的情况,还有更快的算法。一种这样的算法仅对32bit
或64bit
无符号整数使用智能位运算(因此仅对于n <= 64
可能)
note4上述算法(针对python)也可以调整为使用iterator
模式或generator
模式(即yield
),但可以在任何语言中轻松实现,即使是那些不支持生成器的语言
注意5对于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)