F # Idiomatic Performance

Question

Я использую Упражнение для изучения F # .Задачей Nth Prime было построить Сито Эратосфена .В модульном тесте вы искали 1 001-е простое число, которое составляет 104 743.

Я изменил фрагмент кода, который я запомнил из F # Для Fun и Profit для работы в пакетном режиме (нужно 10 тыс. Простых чисел, а не 25), и сравнил его с моей собственной обязательной версией.Существует значительная разница в производительности:

(BenchmarkDotNet v0.11.2)

Существует ли эффективный способ сделать это идиоматически?Мне нравится F #.Мне нравится, сколько времени экономит использование библиотек F #.Но иногда я не вижу эффективного идиоматического маршрута.

Вот идиоматический код:

// we only need to check numbers ending in 1, 3, 7, 9 for prime
let getCandidates seed = 
    let nextTen seed ten = 
        let x = (seed) + (ten * 10)
        [x + 1; x + 3; x + 7; x + 9]
    let candidates = [for x in 0..9 do yield! nextTen seed x ]
    match candidates with 
    | 1::xs -> xs  //skip 1 for candidates
    | _ -> candidates


let filterCandidates (primes:int list) (candidates:int list): int list = 
    let isComposite candidate = 
        primes |> List.exists (fun p -> candidate % p = 0 )
    candidates |> List.filter (fun c -> not (isComposite c))

let prime nth : int option = 
    match nth with 
        | 0 -> None
        | 1 -> Some 2
        | _ ->
            let rec sieve seed primes candidates = 
                match candidates with 
                | [] -> getCandidates seed |> filterCandidates primes |> sieve (seed + 100) primes //get candidates from next hunderd
                | p::_ when primes.Length = nth - 2 -> p //value found; nth - 2 because p and 2 are not in primes list
                | p::xs when (p * p) < (seed + 100) -> //any composite of this prime will not be found until after p^2
                    sieve seed (p::primes) [for x in xs do if (x % p) > 0 then yield x]
                | p::xs -> 
                    sieve seed (p::primes) xs


            Some (sieve 0 [3; 5] [])

А вот и императив:

type prime = 
    struct 
        val BaseNumber: int
        val mutable NextMultiple: int
        new (baseNumber) = {BaseNumber = baseNumber; NextMultiple = (baseNumber * baseNumber)}
        //next multiple that is odd; (odd plus odd) is even plus odd is odd
        member this.incrMultiple() = this.NextMultiple <- (this.BaseNumber * 2) + this.NextMultiple; this 
    end

let prime nth : int option = 
    match nth with 
    | 0 -> None
    | 1 -> Some 2
    | _ ->
        let nth' = nth - 1 //not including 2, the first prime
        let primes = Array.zeroCreate<prime>(nth')
        let mutable primeCount = 0
        let mutable candidate = 3 
        let mutable isComposite = false
        while primeCount < nth' do

            for i = 0 to primeCount - 1 do
                if primes.[i].NextMultiple = candidate then
                    isComposite <- true
                    primes.[i] <- primes.[i].incrMultiple()

            if isComposite = false then 
                primes.[primeCount] <- new prime(candidate)
                primeCount <- primeCount + 1

            isComposite <- false
            candidate <- candidate + 2

        Some primes.[nth' - 1].BaseNumber

Answer 1

Таким образом, в целом, при использовании функциональных идиом, вы, вероятно, ожидаете, что будете немного медленнее, чем при использовании императивной модели, потому что вам нужно создавать новые объекты, что занимает намного больше времени, чем изменение уже существующего объекта.

Для этой проблемы особенно тот факт, что при использовании списка F # тот факт, что вам нужно повторять список простых чисел каждый раз, является потерей производительности по сравнению с использованием массива.Следует также отметить, что вам не нужно генерировать список кандидатов отдельно, вы можете просто зациклить и добавить 2 на лету.Тем не менее, наибольший выигрыш в производительности, вероятно, заключается в использовании мутации для хранения ваших nextNumber.

type prime = {BaseNumber: int; mutable NextNumber: int}
let isComposite (primes:prime list) candidate = 
    let rec inner primes candidate =
        match primes with 
        | [] -> false
        | p::ps ->
            match p.NextNumber = candidate with
            | true -> p.NextNumber <- p.NextNumber + p.BaseNumber*2
                      inner ps candidate |> ignore
                      true
            | false -> inner ps candidate
    inner primes candidate


let prime nth: int option = 
    match nth with 
    | 0 -> None
    | 1 -> Some 2
    | _ -> 
            let rec findPrime (primes: prime list) (candidate: int) (n: int) = 
                match nth - n with 
                | 1 -> primes
                | _ -> let isC = isComposite primes candidate
                       if (not isC) then
                           findPrime ({BaseNumber = candidate; NextNumber = candidate*candidate}::primes) (candidate + 2) (n+1)
                       else
                           findPrime primes (candidate + 2) n
            let p = findPrime [{BaseNumber = 3; NextNumber = 9};{BaseNumber = 5; NextNumber = 25}] 7 2
                    |> List.head
            Some(p.BaseNumber)

. Пройдя через #time, я получу около 500 мсек для запуска prime 10001.Для сравнения, ваш «императивный» код занимает около 250 мс, а ваш «идоматический» код - около 1300 мс.

Answer 2

На первый взгляд вы не сравниваете равные понятия.Конечно, я говорю не о функционале против императива, а о понятиях, лежащих в основе самих алгоритмов.

В вашей вики-справке это сказано лучше:

Это ключевое отличие решетки отиспользование пробного деления для последовательной проверки каждого числа кандидатов на делимость на каждое простое число.

Другими словами, сила Решета Эратосфена заключается в том, чтобы не использовать пробное деление.Еще один wiki ref :

Пробное разделение является наиболее трудоемким, но самым простым для понимания алгоритмом целочисленной факторизации.

И фактически то, что вы 'Вы делаете в вашем фильтре.

let isComposite candidate =  
    primes |> List.exists (fun p -> candidate % p = 0 )