Использование функционального программирования для эффективного вычисления простых чисел - PullRequest
Новая
       1

Использование функционального программирования для эффективного вычисления простых чисел

4 голосов
/ 19 марта 2012

Я знакомлюсь с F #, перебираю Project Euler и решаю некоторые проблемы. Многие из ранних проблем состоят из простых чисел. Осмотревшись, я нашел следующее решение: 

let primesL =
    let rec prim n sofar = 
        seq { if (sofar |> List.forall (fun i->n%i <>0L)) then
                  yield n
                  yield! prim (n+1L) (n::sofar)
              else
                  yield! prim (n+1L) sofar  }
    prim 2L []

Это хорошо работает, но затем я генерирую все простые числа до 2000000: 

let smallPrimes = primesL |> Seq.takeWhile (fun n->n<=2000000)

Это займет возраст . Совершенно очевидно, что что-то делается в O (N ^ 2) или в худшем случае.

Я знаю, что могу написать императивную версию и реализовать какое-то сито , но я хочу придерживаться функционального кода. Если бы я хотел императив, я бы остался с C #.

Что мне не хватает?

Ответы [ 5 ]

7 голосов
/ 19 марта 2012

Вместо того, чтобы писать длинный ответ здесь, я отсылаю вас к Великой работе Мелиссы О'Нил о сите Эратосфена .

5 голосов
/ 19 марта 2012

Возможно, вы захотите сравнить свой подход с моим вариантом решения задачи Эйлера 10 

let rec primes = 
    Seq.cache <| seq { yield 2; yield! Seq.unfold nextPrime 3 }
and nextPrime n =
    if isPrime n then Some(n, n + 2) else nextPrime(n + 2)
and isPrime n =
    if n >= 2 then
        primes 
        |> Seq.tryFind (fun x -> n % x = 0 || x * x > n)
        |> fun x -> x.Value * x.Value > n
    else false

Он чисто функциональный, использует кэширование последовательности, оптимизировано для проверки простоты;Кроме того, он дает очень полезную isPrime n функцию в качестве побочного результата.

И, будучи применен к исходной задаче 

let problem010 () =
    primes
    |> Seq.takeWhile ((>) 2000000)
    |> (Seq.map int64 >> Seq.sum)

, он завершается за приличные 2,5 с .Это не слишком быстро, но было достаточно хорошо, чтобы использовать эту последовательность primes в нескольких моих других решениях Project Euler (пока 27, 35, 37, 50, 58, 69, 70, 77).

Относительно того, что вам не хватает в вашем решении - из вашего кода я считаю, что вы строите совершенно новую последовательность при каждом внутреннем вызове на prim, то есть для каждого естественного, в то время как мой подход использует single последовательность для уже найденных простых чисел, и только перечисляет свой кэшированный экземпляр при создании каждого следующего простого числа.

1 голос
/ 19 марта 2012

Что вам действительно нужно, так это сито - я написал довольно быстрое сито F # здесь:

F # проблема распараллеливания при вычислении совершенных чисел?

1 голос
/ 19 марта 2012

Во-первых, это равно O(n^2) - помните, что вы используете List.forall на каждой итерации.

Во-вторых, если вы часто используете генератор, вам следует кэшировать результаты (чтобы каждое простое число вычислялось только один раз): 

let primesL =
    let rec prim n sofar = 
        seq { if (sofar |> List.forall (fun i -> n % i <> 0UL)) then
                  yield n
                  yield! prim (n + 1UL) (n::sofar)
              else
                  yield! prim (n + 1UL) sofar }
    prim 2UL []
    |> Seq.cache
0 голосов
/ 19 марта 2012

Используйте « критерий примитивности Миллера – Рабина » для более чем большого простого числа

...