性能 – 组合(n选择k)并行化和效率

最近我一直在使用单词的组合来制作不同语言的“短语”,我注意到了一些我可以用更专业的输入做的事情.

为此定义一些常量,

深度(n)平均为6-7

输入集的长度约为160个唯一字.

>内存 – 生成160个单词的n个排列会占用大量空间.我可以通过将数据库写入磁盘来滥用数据库,但随后我需要不断等待IO才能获得性能.另一个技巧是像生成器对象一样动态生成组合
>时间 – 如果我没错,那么选择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 
}

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

奖金问题,可以同时生成组合吗？

更新：我已经知道如何按常规生成它们,更多的是使其高效.

一种方法是首先根据您获得的线程数计算您可以获得多少并行度.让线程数为T,并按如下方式拆分工作：

>根据一些总排序对元素进行排序.
>找到最小数d,使得选择(n,d)> = T.
>找到’深度'(确切地)d的所有组合(通常远低于深度d,并且可在一个核心上计算).
>现在,将工作分散到你的T核心,每个核心获得一组’前缀'(每个前缀c是大小为d的组合),并且对于每种情况,找到它们的“最小”元素“更大”的所有后缀根据总排序比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))