Я пишу в OCaml, пытаясь дать (несколько) эффективную реализацию простой факторизации.Я считаю, что лучшее представление числа 2 или более в списке экспонентов.Для простоты с консингом я сделаю это в порядке убывания простых чисел.Таким образом, 2 будет [1] и 3 будет [1; 0], а 4 будет [2] и 5 [1; 0; 0].
Я думал об использовании идеи сита, чтобы взять число n и найти все возможные делители между 2 и sqrt(n).Затем разделите на любой делитель и рекурсивно.Тем не менее, каждая реализация, о которой я могу думать, кажется, включает в себя многократный поиск по списку, и это кажется просто излишне неэффективным.Схема моего решения лучше всего изложена в этом коде
let rec pf n =
if (n=2) then ([1], 0)
else let sq = int_of_float ( (float_of_int n) ** 0.5 ) in
let primes = getPrimes sq in
match earliestDiv n primes with
| None -> n::(zero_list (n-1))
| Some (x, i) -> let subproblem pf (n/x) in
increment subproblem i
Вспомогательные функции здесь будут:
getPrimes, который принимает int и возвращает список всех простыхчисла, меньшие или равные ему. earliestDiv, который принимает int n и список целых чисел lst, возвращает опцию int * int, соответствующую самому раннему числу в lstкоторый делит n.Это будет первая координата кортежа;вторая координата вернет индекс этого простого числа x в списке простых чисел.increment будет принимать список и индекс int и увеличивать на 1 число, находящееся в индексе.
Все эти вспомогательные функции продолжают создавать списки и проходить через списки, и так далее.И на самом деле, я часто чувствую, что делаю это в функциональном программировании.У меня часто возникает ощущение, что я без необходимости перебираю списки, тогда как в императивных языках я буду писать более эффективный код.Возможно, это просто в моей голове, и когда я пишу на императивных языках, я реже замечаю, сколько ресурсов идет на некоторые операции со списком, которые я использую.Но если мне не хватает какого-то важного метода, который может помешать повторному сканированию списков, мне было бы любопытно услышать его.
Вопрос: нужно ли многократно создавать и повторять списки, чтобы написать эту функцию?