Можно ли улучшить время выполнения этого генератора простых чисел?

Question

Моя первоначальная цель при написании этого заключалась в том, чтобы оставить минимальный след. Я могу с уверенностью сказать, что эта цель была достигнута. К сожалению, это оставляет меня с довольно медленной реализацией. Чтобы генерировать все простые числа ниже 2 миллионов, это занимает около 8 секунд на чипе Intel 3Ghz.

Есть ли способ улучшить время выполнения этого кода с минимальной жертвой небольшого объема памяти? В качестве альтернативы, я собираюсь сделать это неправильно, глядя на нее с функциональной точки зрения?

КОД

/// 6.5s for max = 2,000,000 
let generatePrimeNumbers max =  
    let rec generate number numberSequence = 
     if number * number > max then numberSequence else 
     let filteredNumbers = numberSequence |> Seq.filter (fun v -> v = number || v % number <> 0L) 
     let newNumberSequence = seq { for i in filteredNumbers -> i } 
     let newNumber = newNumberSequence |> Seq.find (fun x -> x > number) 
     generate newNumber newNumberSequence     
    generate 2L (seq { for i in 2L..max -> i }) 

Update

Я отлажены алгоритм и удалось сбрить 2 секунды, но двойное потребление памяти.

/// 5.2s for max = 2,000,000 
let generatePrimeNumbers max =  
    let rec generate number numberSequence = 
     if number * number > max then numberSequence else 
     let filteredNumbers = numberSequence |> Seq.filter (fun v -> v = number || v % number <> 0L) |> Seq.toArray |> Array.toSeq 
     let newNumber = filteredNumbers |> Seq.find (fun v -> v > number) 
     generate newNumber filteredNumbers     
    generate 2L (seq { for i in 2L..max -> i }) 

Update

Видимо, я использовал старый компилятор. С последней версией мой первоначальный алгоритм занимает 6.5 с, а не 8. Это довольно улучшилось.

Answer 1

Tomas Petricek's function довольно быстро, но мы можем сделать это немного быстрее.

Сравните следующие:

let is_prime_tomas n = 
    let ms = int64(sqrt(float(n))) 
    let rec isPrimeUtil(m) = 
     if m > ms then true 
     elif n % m = 0L then false 
     else isPrimeUtil(m + 1L) 
    (n > 1L) && isPrimeUtil(2L) 

let is_prime_juliet n = 
    let maxFactor = int64(sqrt(float n)) 
    let rec loop testPrime tog = 
     if testPrime > maxFactor then true 
     elif n % testPrime = 0L then false 
     else loop (testPrime + tog) (6L - tog) 
    if n = 2L || n = 3L || n = 5L then true 
    elif n <= 1L || n % 2L = 0L || n % 3L = 0L || n % 5L = 0L then false 
    else loop 7L 4L 

is_prime_juliet имеет немного чуть-чуть быстрее, внутренний цикл. Его хорошо известный премьер-генерирующая стратегия, которая использует «тумблер», чтобы пропустить, не являющиеся простые числа с шагом 2 или 4. Для сравнения:

> seq { 2L .. 2000000L } |> Seq.filter is_prime_tomas |> Seq.fold (fun acc _ -> acc + 1) 0;; 
Real: 00:00:03.628, CPU: 00:00:03.588, GC gen0: 0, gen1: 0, gen2: 0 
val it : int = 148933 

> seq { 2L .. 2000000L } |> Seq.filter is_prime_juliet |> Seq.fold (fun acc _ -> acc + 1) 0;; 
Real: 00:00:01.530, CPU: 00:00:01.513, GC gen0: 0, gen1: 0, gen2: 0 
val it : int = 148933 

Моей версии о 2.37x быстрее, и его также довольно близко до скорости самых быстрых императивных версий. Мы можем сделать это еще быстрее потому что нам не нужно фильтровать список 2L .. 2000000L, мы можем использовать ту же стратегию, чтобы создать более оптимальную последовательность возможных простых чисел, прежде чем применить наш фильтр:

> let getPrimes upTo = 
    seq { 
     yield 2L; 
     yield 3L; 
     yield 5L; 
     yield! (7L, 4L) |> Seq.unfold (fun (p, tog) -> if p <= upTo then Some(p, (p + tog, 6L - tog)) else None) 
    } 
    |> Seq.filter is_prime_juliet;; 
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0 

val getPrimes : int64 -> seq<int64> 

> getPrimes 2000000L |> Seq.fold (fun acc _ -> acc + 1) 0;; 
Real: 00:00:01.364, CPU: 00:00:01.357, GC gen0: 36, gen1: 1, gen2: 0 
val it : int = 148933 

Мы упал с 1,530 до 01,364, поэтому мы получили около 1,21 раза больше скорости. Потрясающие!

Answer 2

Я написал императивную версию, которая быстрее. Может быть невозможно написать Сито Эратосфена чистым функциональным способом для достижения такой же скорости, так как у вас должно быть двоичное состояние для каждого числа.

let generatePrimes max= 
    let p = Array.create (max+1) true 
    let rec filter i step = 
     if i <= max then 
      p.[i] <- false 
      filter (i+step) step 
    {2..int (sqrt (float max))} |> Seq.map (fun i->filter (i+i) i) |> Seq.length |> ignore 
    {2..max} |> Seq.filter (fun i->p.[i]) |> Seq.toArray 

Answer 3

Просто для забавы, давайте посмотрим на this page.

pi (x) - основная функция подсчета, она возвращает количество простых чисел ниже x. Вы можете приблизить пи (х), используя следующие неравенства:

(x/log x)(1 + 0.992/log x) < pi(x) < (x/log x)(1 + 1.2762/log x) 
// The upper bound holds for all x > 1 

р (х) основная функция п-го, которая может быть аппроксимирована с помощью:

n ln n + n ln ln n - n < p(n) < n ln n + n ln ln n 
// for n >= 6 

Имея это в виду, here is a very fast generator, вычисляющий первые n простых чисел, где каждый элемент с индексом i равен p(i). Таким образом, если мы хотим ограничить наш массив на штрихах ниже 2000000, мы используем UpperBound неравенство для простого подсчета функции:

let rec is_prime (primes : int[]) i testPrime maxFactor = 
    if primes.[i] > maxFactor then true 
    else 
     if testPrime % primes.[i] = 0 then false 
     else is_prime primes (i + 1) testPrime maxFactor 

let rec prime_n (primes : int[]) primeCount testPrime tog = 
    if primeCount < primes.Length then 
     let primeCount' = 
      if is_prime primes 2 testPrime (float testPrime |> sqrt |> int) then 
       primes.[primeCount] <- testPrime 
       primeCount + 1 
      else 
       primeCount 
     prime_n primes primeCount' (testPrime + tog) (6 - tog) 

let getPrimes upTo = 
    let x = float upTo 
    let arraySize = int <| (x/log x) * (1.0 + 1.2762/log x) 
    let primes = Array.zeroCreate (max arraySize 3) 
    primes.[0] <- 2 
    primes.[1] <- 3 
    primes.[2] <- 5 

    prime_n primes 3 7 4 
    primes 

Круто! Итак, как быстро? На моем 3.2GHz четырехъядерный процессор, я получаю следующее FSI:

> let primes = getPrimes 2000000;; 
Real: 00:00:00.534, CPU: 00:00:00.546, GC gen0: 0, gen1: 0, gen2: 0 

val primes : int [] = 
    [|2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 
    73; 79; 83; 89; 97; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151; 
    157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233; 
    239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317; 
    331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419; 
    421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 479; 487; 491; 499; 503; 
    509; 521; 523; 541; ...|] 

> printfn "total primes: %i. Last prime: %i" (primes.Length - 1) primes.[primes.Length - 1];; 
total primes: 149973. Last prime: 2014853 

Так что это все простые числа около 2 миллионов человек в менее чем полсекунды :)

Answer 4

Императив версия размещена Инь очень быстро. На моей машине это также около 0,5 сек. Однако, если вы хотите, чтобы написать простое функциональное решение, которое вы можете просто написать следующее:

let isPrime(n) = 
    let ms = int64(sqrt(float(n))) 
    let rec isPrimeUtil(m) = 
    if m > ms then true 
    elif n % m = 0L then false 
    else isPrimeUtil(m + 1L) 
    (n > 1L) && isPrimeUtil(2L) 

[ 1L .. 2000000L ] |> List.filter isPrime 

Это просто проверяет, является ли число простым для всех чисел 1 Milion. Он не использует сложные алгоритмы (на самом деле смешно, что самое простое решение часто бывает достаточно хорошим!).На моей машине ваша обновленная версия работает около 11 секунд, и это длится около 2 секунд.

Более интересно, это очень легко распараллелить. Если вы используете PLINQ, вы можете написать версию ниже, и она будет работать почти в 2 раза быстрее на двухъядерном процессоре. Это означает, что на четырехъядерном процессоре это может быть так же быстро, как и самое быстрое решение из всех ответов здесь, но с минимальными усилиями по программированию :-) (конечно, использование четырех ядер не является экологическим, но .. хорошо)

[ 1L .. 2000000L ] |> PSeq.ofSeq |> PSeq.filter isPrime |> List.ofSeq 

Функции PSeq являются оболочками для PLINQ, которые я создал для своей книги (это делает использование PLINQ из F # более естественным). Они доступны в .

Answer 5

EDIT: обновленная версия ниже, использует меньше памяти и быстрее

Иногда это хорошо, чтобы быть в состоянии мутировать вещи. Вот, по общему признанию, весьма императивный вариант, который торгует памятью для скорости. Поскольку в этом потоке оказалось, что в F # есть хорошая коллекция простых генераторных функций, я подумал, что было бы неплохо добавить мой в любом случае. Использование BitArray проверяет память.

open System.Collections 

let getPrimes nmax = 
    let sieve = new BitArray(nmax+1, true) 
    let result = new ResizeArray<int>(nmax/10) 
    let upper = int (sqrt (float nmax)) 
    result.Add(2) 

    let mutable n = 3 
    while n <= nmax do 
     if sieve.[n] then 
      if n<=upper then 
       let mutable i = n 
       while i <= nmax do sieve.[i] <- false; i <- i + n 
      result.Add n 
     n <- n + 2 
    result 

Обновление:

Код выше может быть оптимизирована далее: так как она использует только нечетные индексы в сите, то BitArray может быть уменьшена до половины размера путем индексации нечетных п, как 2т + 1. Новая версия также быстрее:

let getPrimes2 nmax = 
    let sieve = new BitArray((nmax/2)+1, true) 
    let result = new ResizeArray<int>(nmax/10) 
    let upper = int (sqrt (float nmax)) 
    if nmax>1 then result.Add(2) //fixes a subtle bug for nmax < 2 

    let mutable m = 1 
    while 2*m+1 <= nmax do 
     if sieve.[m] then 
      let n = 2*m+1 
      if n <= upper then 
       let mutable i = m 
       while 2*i < nmax do sieve.[i] <- false; i <- i + n 
      result.Add n 
     m <- m + 1 
    result 

Timing (Intel Core Duo 2,33 ГГц):

> getPrimes 2000000 |> Seq.length;; 
Real: 00:00:00.037, CPU: 00:00:00.046, GC gen0: 0, gen1: 0, gen2: 0 
val it : int = 148933 
> getPrimes2 2000000 |> Seq.length;; 
Real: 00:00:00.026, CPU: 00:00:00.031, GC gen0: 0, gen1: 0, gen2: 0 
val it : int = 148933