performance - 组合(n 选择 k)并行化和效率

Question

最近，我一直在使用单词组合来制作不同语言的“短语”，并且我注意到一些事情我可以在更多专家的帮助下完成。

为此定义一些常量，

深度 (n) 平均为 6-7

输入集的长度约为 160 个不同的单词。

1. 内存 - 生成 160 个单词的 n 个排列会浪费大量空间。我可以通过将数据库写入磁盘来滥用数据库，但是由于我需要不断地等待 IO，因此我的性能受到了影响。另一个技巧是像生成器对象一样动态生成组合
2. 时间 - 如果我没有错 n 选择 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 
}

如何在大量组合上有效地处理和执行此功能？

加分题，可以并发生成组合吗？

更新:我已经知道如何以常规方式生成它们，更多的是提高效率。

Answer 1

一种方法是首先根据您拥有的线程数计算您可以获得多少并行度。设线程数为T，按如下方式拆分工作:

• 根据某种总体顺序对元素进行排序。
• 找到满足 Choose(n,d) >= T 的最小数 d。
• 找到“深度”(准确)d 的所有组合(通常远低于深度 d，并且可在一个核心上计算)。
• 现在，将工作分散到您的 T 核心，每个核心都获得一组“前缀”(每个前缀 c 是大小 d 的组合)，并且对于每个case，根据总序找出所有“最小”元素比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))