При генерации простых чисел в F #, почему «Сито эротена» так медленно в этой конкретной реализации?
IE,
Что я здесь не так делаю? Должно ли это быть со списками, последовательностями и массивами и с тем, как работают ограничения?
Итак, вот настройка: я пытаюсь сгенерировать некоторые простые числа. Я вижу, что существует миллиард текстовых файлов с миллиардом простых чисел. Вопрос не в том, почему ... вопрос в том, как парни, использующие python, вычисляют все простые числа ниже 1 000 000 в миллисекундах наэта почта... и что я делаю не так со следующим кодом F #?
let sieve_primes2 top_number =
let numbers = [ for i in 2 .. top_number do yield i ]
let sieve (n:int list) =
match n with
| [x] -> x,[]
| hd :: tl -> hd, List.choose(fun x -> if x%hd = 0 then None else Some(x)) tl
| _ -> failwith "Pernicious list error."
let rec sieve_prime (p:int list) (n:int list) =
match (sieve n) with
| i,[] -> i::p
| i,n' -> sieve_prime (i::p) n'
sieve_prime [1;0] numbers
С таймером в FSI я получаю 4,33 секунды процессора на 100000 ... после этого все просто взрывается.