组合数（n选k）的并行化和效率优化

Question

最近我一直在尝试用不同语言的单词组合成“短语”，但我发现有些地方需要更专业的意见。

先定义一些常量：

深度（n）平均为6-7

输入集长度约为160个唯一单词。

1. 内存 - 生成160个单词的n排列会浪费很多空间。我可以通过将其写入磁盘来滥用数据库，但这会影响性能，因为我需要不断等待IO。另一个技巧是像生成器对象一样实时生成组合。
2. 时间 - 如果我没错，n choose k 很快就会变得非常大，类似于这个公式 factorial(n) / (factorial(depth) * (factorial(n-depth))) 这意味着输入集很快就会变得非常庞大。

我的问题是：

考虑到我有一个函数 f(x)，它接收一个组合并应用一个具有代价的计算，例如

func f(x) {
    if query_mysql("text search query").value > 15 {
        return true
    }
    return false 
}

如何高效处理和执行大量组合的函数？

附加问题，能否并发生成组合？

更新：我已经知道如何常规生成组合，更多的是让它变得高效。

- Jakob Bowyer

---

在计算过程中，“深度”是否保持不变？因此，对于算法的一次运行，您的输出是160个长度输入中所有“depth = 6”的单词组合或范围为“[1,6]”的所有单词组合？ - Matti Lyra

@MattiLyra 理想情况下，我希望深度从[n..2]开始，但现在先专注于一个，为了清晰起见，删除了一行。 - Jakob Bowyer

好吧，这将为你提供一种并行化组合的方法，将n=3, n=4 ... n=n中的每个运行在并行上，因为它们彼此之间没有依赖关系。 - Matti Lyra

@MattiLyra 如果从一个组合中得到的结果始终在下一个组合中，那么可能会进行浪费计算。 - Jakob Bowyer

我不知道是谁投票关闭了这个问题。这个问题在SO上完全没有问题。 - amit

Answer 1

一种方法是先计算可以获得多少并行性，基于你所拥有的线程数。设线程数为T，按以下方式分配工作：

• 根据某些全序排序对元素进行排序。
• 寻找最小数字d，使得Choose(n,d) >= T。
• 查找所有'深度'(确切地说是d)的组合(通常比深度d低得多，可以在一个核心上计算)。
• 现在，将工作分配给你的T个核心，每个核心都得到一组'前缀'(每个前缀c都是大小为d的组合)，对于每种情况，在总排序中找到所有'smallest'元素比max(c)大的后缀。

这种方法也可以很好地转化为map-reduce范式。

map(words): //one mapper
   sort(words) //by some total ordering function
   generate all combiations of depth `d` exactly // NOT K!!!
   for each combination c produced:
       idx <- index in words of max(c) 
       emit(c,words[idx+1:end])
reduce(c1, words): //T reducers
   combinations <- generate all combinations of size k-d from words
   for each c2 in combinations:
      c <- concat(c1,c2)
      emit(c,f(c))

- amit

Answer 2

使用众所周知的算法之一来生成组合。Chase的Twiddle算法是最著名且完全适用的算法之一。它在数组中捕获状态，因此如果需要，可以重新启动或种子化。

请参见从n个元素中返回所有k个元素的组合的算法以获取更多信息。

您可以按照自己的节奏遍历列表，使用最少的内存和无磁盘IO。与计算机运算的1秒左右相比，生成每个组合所需的时间微不足道。

如果您具备必要的技能，这种算法（以及许多其他算法）很容易适应并行执行。

- david.pfx

---

这根本不回答问题。 - Jakob Bowyer

那么你应该提出更好的问题。如果你想要一个解释如何使用MapReduce或Hadoop的答案，那就明确地说出来。 - david.pfx

如果你学会了阅读，我就说，我已经知道如何生成组合，但当在数组中存储状态时，我也会耗尽内存。 - Jakob Bowyer

如果你检查算法，所需的状态是N+2个整数。由于分配162个整数时不会耗尽内存，我必须假设你正在使用错误的算法。有了正确的算法，剩下的就很容易了。 - david.pfx