我试图通过使用CUDA来查找字符串的所有可能组合来加速我的算法.我能做到这一点的最佳方式是什么？
例:
abc
得到:
a
b
c
ab
ac
bc
到目前为止我什么都没有.我不是要求代码.我只想问最好的方法吗？一个算法？伪代码？也许是讨论？
使用CUDA的优点是大量并行性,可能有数千个线程,开销很小.为此,您必须找到一种方法将问题分成小块,而不必过多依赖线程之间的通信.在这个问题中,您有n字符,每个字符都可以在每个输出字符串中存在或不存在.这会产生2^n总输出字符串.(你已经从列表中删除了空字符串和原始字符串...如果这是所需的结果,那么你有2^n - 2总输出字符串.)
在任何情况下,分割创建字符串的工作的一种方法是为每个潜在的输出字符串分配一个数字,并让每个线程计算一定数量范围的输出字符串.如果查看每个数字的二进制表示,则从数字到输出字符串的映射很容易.n-bit编号中的每个二进制数字对应于长度字符串中的字符n.因此,对于您的示例,数字5或101二进制映射到字符串"ac".您列出的字符串将通过计算从1到6的数字的映射来创建,如下所示:
1 c
2 b
3 bc
4 a
5 ac
6 ab
如果需要,您可以计算7得到abc或0获得空字符串.
除非你为超过十几个字符的单词做这个,否则我不确定这会更快.如果您对超过25个字符的单词执行此操作,则可能会开始遇到内存限制,因为您将进行数百兆字节的争论.