Ответ 1

Нет функции Seq.tail в основной библиотеке F # (UPDATE: Да, см. комментарии), поэтому я предполагаю, что вы используете функцию Seq.tail из FSharpx.Collections. Если вы используете другую реализацию Seq.tail, это, вероятно, похожее - и это почти наверняка является причиной ваших проблем, потому что это не O (1), как вы думаете. Получение хвоста Список - это O (1) из-за того, как реализуется List (как серия cons-ячеек). Но получение хвоста Seq приводит к созданию нового Seq из исходного перечислимого, отбрасывая один элемент из него и возвращая остальные его элементы. Когда вы повторите цикл accum во второй раз, вы вызываете Seq.tail на этом "skip 1 then return" seq. Итак, теперь у вас есть Seq, который я назову S2, который запрашивает S1 для IEnumerable, пропускает первый элемент S1 и возвращает остальную часть. S1, когда его запрашивает первый элемент, запрашивает S0 (исходный Seq) для перечислимого, пропускает свой первый элемент, а затем возвращает остальную часть. Таким образом, для S2, чтобы пропустить два элемента, ему пришлось создать два сегмента. Теперь при следующем запуске, когда вы запрашиваете Seq.tail S2, вы создаете S3, который запрашивает S2 для IEnumerable, который запрашивает S1 для IEnumerable, который запрашивает S0 для IEnumerable... и так далее. Это эффективно O (N ^ 2), когда вы думали, что пишете операцию O (N).

Я боюсь, что у меня нет времени, чтобы найти решение для вас; использование List.tail не поможет, поскольку вам нужна бесконечная последовательность. Но, возможно, просто знать о Seq.tail gotcha достаточно, чтобы вы начали, поэтому я отправлю этот ответ сейчас, даже если он не завершен.

Если вам нужна дополнительная помощь, прокомментируйте этот ответ, и я вернусь к нему, когда у меня будет время, но это может быть не несколько дней, поэтому, надеюсь, другие также ответят на ваш вопрос.

Ответ 2

Выполнение записи F # очень возможно, но требует некоторых знаний о шаблонах, которые имеют высокую относительную стоимость процессора в жесткой петле. Я рекомендую использовать такие инструменты, как ILSpy, чтобы найти скрытые служебные данные.

Например, можно представить, что F # переводит это выражение в эффективный цикл:

[3..2..(int (sqrt (float n)))] 
|> List.tryFind (fun i -> n%i=0)
|> Option.isNone

Однако в настоящее время этого нет. Вместо этого он создает List, который охватывает диапазон с использованием собственных операторов и передает его на List.tryFind. Это дорого по сравнению с фактической работой, которую нам нравится делать (операция модуля). ILSpy декомпилирует код выше:

public static bool is_prime(int _arg1)
{
  switch (_arg1)
  {
  case 2:
    return true;
  default:
    return _arg1 >= 2 && _arg1 % 2 != 0 && ListModule.TryFind<int>(new [email protected](_arg1), SeqModule.ToList<int>(Operators.CreateSequence<int>(Operators.OperatorIntrinsics.RangeInt32(3, 2, (int)Math.Sqrt((double)_arg1))))) == null;
  }
}

Эти операторы не так эффективны, как они могут быть (AFAIK в настоящее время улучшается), но независимо от того, насколько эффективно выделяет List, а затем поиск не будет бить цикл for.

Это означает, что is_prime не так эффективен, как мог бы быть. Вместо этого можно было сделать что-то вроде этого:

let is_prime = function
  | 1                 -> false
  | 2                 -> true
  | v when v % 2 = 0  -> false
  | v ->
    let stop = v |> float |> sqrt |> int
    let rec loop vv =
      if vv <= stop then
        (v % vv) <> 0 && loop (vv + 2)
      else
        true
    loop 3

Эта версия is_prime полагается на оптимизацию хвостового вызова в F #, чтобы развернуть цикл в эффективный цикл (вы можете увидеть это с помощью ILSpy). ILSpy декомпилирует цикл таким образом:

while (vv <= stop)
{
  if (_arg1 % vv == 0)
  {
    return false;
  }
  int arg_13_0 = _arg1;
  int arg_11_0 = stop;
  vv += 2;
  stop = arg_11_0;
  _arg1 = arg_13_0;
}

Этот цикл не выделяет память и представляет собой довольно эффективный цикл. Некоторые видят некоторые нечувствительные задания, но, надеюсь, JIT: er устранить их. Я уверен, что is_prime можно улучшить еще дальше.

При использовании Seq в коде исполнения нужно иметь в виду, что он ленив и не использует memoization по умолчанию (см. Seq.cache). Поэтому можно легко закончить повторение одной и той же работы (см. Ответ @rmunn).

Кроме того, Seq не особенно эффективен из-за того, как IEnumerable/IEnumerator разработаны. Лучшими параметрами являются, например, потоки Nessos (доступны для nuget).

В случае, если вы заинтересованы, я сделал быструю реализацию, которая опирается на простой Push-поток, который кажется прилично совершенным:

// Receiver<'T> is a callback that receives a value.
//  Returns true if it wants more values, false otherwise.
type Receiver<'T> = 'T -> bool
// Stream<'T> is function that accepts a Receiver<'T>
//  This means Stream<'T> is a push stream (as opposed to Seq that uses pull)
type Stream<'T>   = Receiver<'T> -> unit

// is_prime returns true if the input is prime, false otherwise
let is_prime = function
  | 1                 -> false
  | 2                 -> true
  | v when v % 2 = 0  -> false
  | v ->
    let stop = v |> float |> sqrt |> int
    let rec loop vv =
      if vv <= stop then
        (v % vv) <> 0 && loop (vv + 2)
      else
        true
    loop 3

// tryFind looks for the first value in the input stream for f v = true.
//  If found tryFind returns Some v, None otherwise
let tryFind f (s : Stream<'T>) : 'T option =
  let res = ref None
  s (fun v -> if f v then res := Some v; false else true)
  !res

// diagonals generates a tuple stream of all diagonal values
//  The first value is the side length, the second value is the diagonal value
let diagonals : Stream<int*int> =
  fun r ->
    let rec loop side v =
      let step  = side - 1
      if r (side, v + 1*step) && r (side, v + 2*step) && r (side, v + 3*step) && r (side, v + 4*step) then
        loop (side + 2) (v + 4*step)
    if r (1, 1) then loop 3 1

// ratio computes the streaming ratio for f v = true
let ratio f (s : Stream<'T>) : Stream<float*'T> =
  fun r ->
    let inc r = r := !r + 1.
    let acc   = ref 0.
    let count = ref 0.
    s (fun v -> (inc count; if f v then inc acc); r (!acc/(!count), v))

let result =
  diagonals
  |> ratio (snd >> is_prime)
  |> tryFind (fun (r, (_, v)) -> v > 1 && r < 0.1)