Haskell -> F #: Сито Тернера

Question

Я читал о различных алгоритмах просеивания, когда наткнулся на своего рода улучшенную версию Сита Эратосфена, называемого Ситом Эйлера. Согласно Wikipedia , в Haskell есть реализация немного другой версии идеи (называемой сеткой Тернера).

Теперь я пытаюсь понять, что именно делает данный фрагмент кода, и я думаю, что получил его, но теперь я хотел перевести код на F # и действительно не знаю, с чего начать. Мое главное беспокойство заключается в том, что, похоже, нет функции для «вычитания» двух последовательностей.

Вот код:

import Data.OrdList (minus)

primes = euler [2..]
euler (p : xs) = p : euler (xs `minus` map (*p) (p : xs))

Как это будет реализовано в F #? Это вообще возможно?

Answer 1

Если вы хотите вычислять такие вещи, как слияния / различия бесконечных списков, как это делает Haskell, вам на ум приходит тип LazyList (находится внутри блока питания F #).

Это делает для очень подробного кода, как перевод ниже:

#r "FSharp.PowerPack.dll"

//A lazy stream of numbers, starting from x
let rec numsFrom x = LazyList.consDelayed x (fun () -> numsFrom (x+1))

//subtracts L2 from L1, where L1 and L2 are both sorted(!) lazy lists
let rec lazyDiff L1 L2 =
    match L1,L2 with
        | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1<x2 ->
            LazyList.consDelayed x1 (fun () -> lazyDiff xs1 L2)
        | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1=x2 ->
            lazyDiff xs1 L2
        | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1>x2 ->
            lazyDiff L1 xs2
        | _ -> failwith "Should not occur with infinite lists!"

let rec euler = function
    | LazyList.Cons(p,xs) as LL ->
        let remaining = lazyDiff xs (LazyList.map ((*) p) LL)
        LazyList.consDelayed p (fun () -> euler remaining)
    | _ -> failwith "Should be unpossible with infinite lists!"

let primes = euler (numsFrom 2)

с

> primes |> Seq.take 15 |> Seq.toList;;
val it : int list = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47]

Обратите внимание, что я добавил два предложения failwith, чтобы компилятор не жаловался на неполное совпадение, даже если мы знаем, что все списки в расчете (лениво) бесконечны.

Answer 2

Во-первых, следует сказать, что сито Эйлера для простых чисел не является «улучшенной версией Эратосфенского сита», поскольку его производительность во всех смыслах намного хуже, чем у любой другой версии сито Эратосфена: Haskell Вики об алгоритмах простых чисел - Эйлер

Далее следует сказать, что код @ cfem, использующий LazyList's, является точным, хотя и подробным переводом версии сита Эйлера, которую вы дали, хотя в нем отсутствует незначительное улучшение только просеивания нечетных чисел по ссылке выше.

Следует отметить, что в действительности нет смысла внедрять сито Эйлера, поскольку оно сложнее и медленнее, чем поиск простых чисел с помощью Trial Division Optimized (TDO), в отношении выполнения делений только по найденным простым числам вплоть до квадрата. корень числа кандидатов, проверенного на простое число согласно: Haskell Wiki по алгоритмам простых чисел - TDO .

Это сито Trial Division Optimized (TDO) может быть реализовано в F # с использованием LazyList's (со ссылкой на FSharp.PowerPack.dll) как:

let primesTDO() =
  let rec oddprimes =
    let rec oddprimesFrom n =
      if oddprimes |> Seq.takeWhile (fun p -> p * p <= n) |> Seq.forall (fun p -> (n % p) <> 0)
      then LazyList.consDelayed n (fun() -> oddprimesFrom (n + 2))
      else oddprimesFrom (n + 2)
    LazyList.consDelayed 3 (fun() -> oddprimesFrom 5)
  LazyList.consDelayed 2 (fun () -> oddprimes)

Может быть реализовано с использованием последовательностей в той же форме, что и:

let primesTDOS() =
  let rec oddprimes =
    let rec oddprimesFrom n =
      if oddprimes |> Seq.takeWhile (fun p -> p * p <= n) |> Seq.forall (fun p -> (n % p) <> 0)
      then seq { yield n; yield! oddprimesFrom (n + 2) }
      else oddprimesFrom (n + 2)
    seq { yield 3; yield! (oddprimesFrom 5) } |> Seq.cache
  seq { yield 2; yield! oddprimes }

Версия последовательности немного быстрее, чем версия LazyList, потому что она избегает некоторых накладных расходов при вызове, поскольку LazyList основана на кэшированных последовательностях. Оба используют внутренний объект, который представляет кешированную копию простых чисел, найденных до сих пор, автоматически кэшируемых в случае LazyList и Seq.cache в случае последовательностей. Любой может найти первые 100 000 простых чисел примерно за две секунды.

Теперь сито Эйлера может иметь оптимизацию просеивания нечетных чисел и может быть выражено с использованием LazyList следующим образом, при этом исключен один случай совпадения, поскольку известно, что параметры входного списка бесконечны, а сопоставление сравнения упрощено. Также я добавил оператор '^', чтобы сделать код более читабельным:

let primesE = //uses LazyList's from referenced FSharp.PowerPack.dll version 4.0.0.1
  let inline (^) a ll = LazyList.cons a (LazyList.delayed ll) //a consd function for readability
  let rec eulers xs =
    //subtracts ys from xs, where xs and ys are both sorted(!) infinite lazy lists
    let rec (-) xs ys =
      let x,xs',ys' = LazyList.head xs,LazyList.tail xs,LazyList.tail ys
      match compare x ( LazyList.head ys) with
        | 0 -> xs' - ys' // x == y
        | 1 -> xs - ys' // x > y
        | _ -> x^(fun()->(xs' - ys)) // must be x < y
    let p = LazyList.head xs
    p^(fun() -> (((LazyList.tail xs) - (LazyList.map ((*) p) xs)) |> eulers))
  let rec everyothernumFrom x = x^(fun() -> (everyothernumFrom (x + 2)))
  2^(fun() -> ((everyothernumFrom 3) |> eulers))

Однако следует отметить, что время для вычисления 1899-го простого числа (16381) составляет примерно 0,2 и 0,16 секунды для primesTDO и primesTDOS, соответственно, в то время как это примерно 2,5 секунды, используя это primesE для ужасной производительности для Эйлера. сито более чем в десять раз, даже для этого небольшого диапазона. В дополнение к ужасной производительности, PrimeE не может даже вычислить простые числа до 3000 из-за еще худшего использования памяти, поскольку записывает быстро растущее число функций отложенного выполнения с увеличением найденных простых чисел.

Обратите внимание, что нужно соблюдать осторожность при повторном хронировании кода, как написано, поскольку LazyList является значением и имеет встроенное запоминание ранее найденных элементов, поэтому второе идентичное сканирование займет время, близкое к нулю; в целях синхронизации может быть лучше сделать PrimeE функцией, как в PrimeE (), чтобы работа каждый раз начиналась с начала.

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

Answer 3

С последовательностями вы становитесь намного более конкурентоспособными, сохраняя последовательность:

let rec euler s =
    seq {
        let s = Seq.cache s
        let p = Seq.head s
        yield p
        yield! minus (Seq.skip 1 s) (Seq.map ((*) p) s) |> euler
    }

Answer 4

Вы можете сделать это с помощью seq . И когда вы сделали минус , эйлер сам по себе такой же, как в Haskell.

let rec minus xs ys =
  seq {
    match Seq.isEmpty xs, Seq.isEmpty ys with
    | true,_ | _,true -> yield! xs
    | _ ->
       let x,y = Seq.head xs, Seq.head ys
       let xs',ys' = Seq.skip 1 xs, Seq.skip 1 ys
       match compare x y with
       | 0 -> yield! minus xs' ys'
       | 1 -> yield! minus xs ys'
       | _ -> yield x; yield! minus xs' ys
  }

let rec euler s =
  seq {
    let p = Seq.head s
    yield p
    yield! minus (Seq.skip 1 s) (Seq.map ((*) p) s) |> euler
  }

let primes = Seq.initInfinite ((+) 2) |> euler