Как я могу найти все возможные комбинации строки?Использование CUDA

Question

Я пытаюсь ускорить мой алгоритм, используя CUDA, чтобы найти все возможные комбинации строк.Как лучше всего этого добиться?
пример:

abc

дает:

a
b
c
ab
ac
bc

У меня пока ничего нет.я не прошу кодя просто спрашиваю лучший способ сделать это?алгоритм?псевдокод?возможно обсуждение?

Answer 1

Преимущество использования CUDA заключается в большом параллелизме с потенциально тысячами потоков с небольшими накладными расходами. Для этого вам нужно найти способ разделить проблему на маленькие куски, не слишком полагаясь на связь между потоками. В этой задаче у вас есть n символов, и каждый может присутствовать или отсутствовать в каждой выходной строке. Это дает 2^n всего выходных строк. (Вы удалили пустую строку и исходную строку из своего списка ... если это желаемый результат, то у вас есть 2^n - 2 всего выходных строк.)

В любом случае, один из способов разделить работу по созданию строк - назначить каждой потенциальной выходной строке номер и заставить каждый поток вычислить выходные строки для определенного диапазона чисел. Преобразование числа в выходную строку легко, если вы посмотрите на двоичное представление каждого числа. Каждая двоичная цифра в n -битном числе соответствует символу в строке длиной n. Таким образом, для вашего примера число 5 или 101 в двоичном коде отображается на строку "ac". Перечисленные вами строки будут созданы путем вычисления отображений для чисел от 1 до 6 следующим образом:

1      c
2      b
3      bc
4      a
5      ac
6      ab

Вы можете вычислить 7, чтобы получить abc или 0, чтобы получить пустую строку, если хотите.

Если вы не делаете это для слов длиннее дюжины или около того символов, я не уверен, что это будет намного быстрее, хотя. Если вы делаете это для слов длиннее 25 или около того символов, вы можете столкнуться с ограничениями памяти, поскольку вы будете спорить сотни мегабайт.

Answer 2

Я буду очень, очень удивлен, если CUDA - правильное решение этой проблемы.

Однако я бы написал ядро, чтобы найти все подстроки длины n, и запустил бы ядро ​​в цикле для каждогозначение n от 0 до длины строки.Таким образом, каждый поток в ядре будет иметь точно такие же инструкции (ни один из потоков не будет сидеть без дела, пока другие заканчивают работу).

Каждый поток "найдет" одну подстроку, поэтому вы также можете иметь поток iнайти подстроку, начинающуюся с индекса i в строке.Обратите внимание, что для каждой длины подстроки требуется различное количество потоков.

, поэтому для n = 1:

thread 0: a
thread 1: b
thread 2: c

и для n = 2:

thread 0: ab
thread 1: bc