Многопоточный расчет по отсортированным комбинациям алфавита в C

Question

Я хочу многопоточно использовать алгоритм «грубой силы».

У меня есть функция bool check(const char *s, size_t n), которая проверяет, является ли строка s размером n паролем или нет.

Эта функция вызывается для всех комбинаций строк, которые возможны с моим алфавитом (около 90 символов в алфавите).

Я был в состоянии сделать это в одном потоке, но теперь я хочу его многопоточно. Я также хочу, чтобы мои потоки к каждому имели почти такое же количество работы. Я не хочу, чтобы один поток должен был тестировать 1B комбинации, а другой только 1k).

Я думал о разделении нагрузки на «партии» комбинаций. Каждая партия будет иметь индекс start и индекс stop, поэтому нить, имеющая пакет, должна проверять все комбинации между start и stop.

То, что я называю индекс комбинации является лексикографическое индекс, например, с алфавитом [A, B, C]:

index combination 
1  A 
2  B 
3  C 
4  AA 
5  AB 
6  AC 
7  BA 
8  BB 
...  ... 

Например, поток, который будет назначен пакет с start=4 и stop=7 будет тестировать комбинации AA, AB, AC, BA.

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

Есть ли еще один быстрый способ разделить работу между потоками?

Answer 1

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

Вместо этого вы можете начать 90 потоков, дать каждой ветке начальную букву для работы, и каждый поток рассматривает слова, состоящие из первой буквы, которую он дал, плюс все комбинации оставшихся букв.