Быстрее / эффективнее генерировать перестановки чтения из файла?

Question

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

Перестановка 'abc ... xyz' для длины (1 +)

До совпадения строк.

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

Answer 1

Скорее всего нет, потому что в этом случае вы были бы связаны с дисковым вводом-выводом, но небольшая часть вашего сгенерированного кода работала бы из кэша. Для генерации новой перестановки требуется около 10 операций, и это намного быстрее, чем чтение с диска

Answer 2

Переборы с грубой силой звучат ужасно (с точки зрения производительности).Можете привести несколько примеров, что сопоставитьString звучит так, как будто повторение будет разрешено (foo), но set не так много.

Чтобы быстрее сопоставить "стек" с "галсами", вы можете отсортировать оба и проверить, одинаковы ли они, что будет работать даже для строк, содержащих некоторые символы чаще:

 stack => ackst 
 tacks => ackst 

 hello => ehllo
 oloeh => ehloo 

Для множеств вы можете использовать регулярные выражения:

 "tacks".matches ("[stack]+") 

, если размер совпадает, но они не будут соответствовать строкам с повторяющимися символами.

Answer 3

Быстрее и эффективнее использовать алгоритм сопоставления строк , например Aho-Corasick.