Можно ли создавать перестановки параллельно? - PullRequest
Новая
       15

Можно ли создавать перестановки параллельно?

0 голосов
/ 11 ноября 2018

Я пытаюсь выяснить, могу ли я ускорить генерацию перестановок.В частности, я использую 8 из [az], и я хотел бы использовать 8 из [a-zA-Z] и 8 из [a-zA-Z0-9].Что, я знаю, быстро займет много времени и пространства.

Даже просто перестановка длины 8 из строчных символов ASCII занимает некоторое время и генерирует гигабайты.Моя проблема в том, что я не понимаю основной алгоритм, и поэтому я не могу понять, могу ли я разделить проблему на более мелкие задачи, чем смогу объединиться позже.

Сценарий Python, которым я былиспользование для генерации списка перестановок: 

import string
import itertools
from itertools import permutations

comb = itertools.permutations(string.ascii_lowercase, 8)

f = open('8letters.txt', 'w')
for x in comb:
        y = ''.join(x)
        f.write(y + '\n')

f.close()

Кто-нибудь знает, как разбить это на подзадачи и собрать их позже?Возможно ли это вообще?

Я мог бы просто попробовать (возможно) более быстрый способ сделать это, но у меня проблемы с C ++ и его std :: next_permutation (), поэтому я не могу это проверитьэто может даже немного ускорить процесс.

Если я могу разделить его на 16 задач и запустить на 16 процессорах Xeon, а затем объединить результаты, это было бы здорово.

1 Ответ

0 голосов
/ 11 ноября 2018

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

Вы хотите иметь перестановку без замены , поэтому проблема не является тривиальной факторизацией. Если нужно выбрать только 8 букв из набора 26, 52 и 62, можно сделать наивную грубую вещь: распараллелить первую букву, позволить потоку просто создать хвост с заменой и отбросить сгенерированные строки, содержащие дубликаты. Но если вы хотите выбрать 25 из 26 букв, это становится действительно расточительным.

Учитывая эту идею, мы можем добиться большего! Мы распараллеливаем первую букву строки и затем генерируем все перестановки с семью элементами из набора, исключая букву, с которой мы начали. Таким образом, мы можем иметь 26 задач (или 52 или 62) и все еще использовать алгоритм. Это может выглядеть так: 

# Use whatever chars you want as the set.
chars = set(string.ascii_lowercase)

# We iterate through all the possible heads. This exact loop will be
# parallelized in the end.
for head in chars:
    # Exclude the head from the set.
    remaining_chars = chars - set(head)

    for tail in itertools.permutations(remaining_chars, 7):
        string = head + ''.join(tail)

        # Store the string in your list/file.

Чтобы использовать несколько ядер, мы используем пул. Для этого нам сначала понадобится функция для отображения. Это немного выше, немного переработано: 

def make_strings(head):
    remaining_chars = chars - set(head)
    strings = [
        head + ''.join(tail)
        for tail in itertools.permutations(remaining_chars, 7)]

    return strings

Теперь где-то еще мы можем создать пул и позволить ему отображаться по головам: 

with multiprocessing.Pool() as pool:
    all_strings = pool.map(make_strings, chars)

Пул получил только необходимые свойства __enter__ и __exit__ с Python 3, поэтому я предполагаю, что мы используем это.

Как только это будет сделано, сведите список списков в простой список строк: 

strings = [
    string
    for sub_list in all_strings
    for string in sub_list]

Поскольку 26 - нечетное число для 16 ядер, мы могли бы подумать о создании головок с itertools.permutation(remaining_chars, 2) и последующем использовании вычитания набора для генерации последних 6 цифр.

Это полный рабочий скрипт для Python 3, который суммирует все: 

import itertools
import multiprocessing
import string


chars = set(string.ascii_lowercase)


def make_strings(head):
    remaining_chars = chars - set(head)
    strings = [
        head + ''.join(tail)
        for tail in itertools.permutations(remaining_chars, 3)]

    return strings


def main():
    with multiprocessing.Pool() as pool:
        all_strings = pool.map(make_strings, chars)

    strings = [
        string
        for sub_list in all_strings
        for string in sub_list]

    print(strings[:100])


if __name__ == '__main__':
    main()
...