Оптимизировать фильтрацию бесконечной строки в Haskell

Question

Я решаю проблему в HackerRank, в которой мне нужно посчитать количество букв 'a' в первых n элементах бесконечной строки повторяющихся последовательностей, например "abc" для "abcabcabcabc...".

Я реализовал следующую функцию, используя списочные выражения:

repeatedString s n = length $ [x | x <- take (fromInteger n) (cycle s), x == 'a']

Где s - это повторяющаяся последовательность, а n - это количество элементов, извлекаемых из бесконечной строки.

Но HackerRank жалуется на то, что некоторые тесты не были выполнены в установленные сроки.

Вопросы:

• Какие здесь узкие места?
• Как я могу определить их для подобных случаев?
• Можете ли вы указать на более эффективный способ сделать это?

Заранее большое спасибо!

РЕДАКТИРОВАТЬ: уточненные параметры функции.

Answer 1

Вам не нужно явно подсчитать количество a с. Что вы можете сделать:

1. посчитать количество 'a' с в c;
2. проверить, сколько раз вы делаете полный цикл s (путем деления n на длину s);
3. вычисляет, сколько символов испускается в последнем (незавершенном) цикле s;
4. подсчитайте количество 'a' с в этой части.
5. суммируйте количество 'a' с полных циклов и число 'a' с неполного цикла.

Таким образом, программа выглядит следующим образом:

repeatedString :: String -> Int -> Int
repeatedString s n = (length (filter ('a' ==) s) * div n (length s)) + …

с … той частью, которую вам необходимо заполнить и которая имеет дело с последним (неполным) циклом.

Даже если n огромен, алгоритм все равно будет работать в O (| s |) .