Профилирование F # для выполнения рекурсивных функций

Question

Я решил использовать F #, чтобы решить вторую проблему в первый день появления кода 2018 (циклическое суммирование и поиск первой повторной суммы) выразительным образом, но производительности не хватает, и я не могу найтипричина замедления.

Проблема решена, как в Python 3

Для заданного ввода с ~ 140 000 суммирования этот код выполняется за несколько секунд.

data = list(map(int, '''
+1
-1
'''.strip().splitlines()))
from itertools import cycle, accumulate
class superset(set):
    def add(self, other):
        super().add(other)
        return other

def mapwhile(func, pred, iterable):
    for i in iterable:
        if not pred(i):
            yield func(i)
            return
        yield func(i)

def last(iterable):
    return list(iterable)[-1]

s = superset([0])
print(last(mapwhile(s.add, lambda x: x not in s, accumulate(cycle(data)))))

Проблема решена, как в F #

Я добавил условную точку останова в выражение соответствия ко времени каждой тысячной i, кажется, этот код выполняет ~ 100 сум / сек и не будетприйти к решению даже через час.Резкое замедление на нелепый порядок по величине.

let input = @"
+1
-1
"
let cycle xs = seq { while true do yield! xs }
let accumusum xs = Seq.scan(fun acc elem -> acc + elem) 0 xs

let rec findfreqcycle i (s:int Set) (data:int seq) = 
    let head, tail = Seq.head data, Seq.tail data
    match s.Contains(head) with
    | false -> findfreqcycle (i+1) (s.Add(head)) (tail)
    | true ->  head


let data = input.Trim().Split('\n') |> Seq.map int |> Seq.toList |> cycle
accumusum data |> findfreqcycle 0 Set.empty

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

Единственное отличие состоит в том, что функция, которая фактически находит первое повторяющееся суммирование, рекурсивна в примере F #.Профилирование памяти указывает на почти постоянное использование памяти, а хвостовая рекурсия активна.

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

Answer 1

Я решил дать реализацию с использованием Seq.scan и Seq.pick попробовать в соответствии с ответом Томаса, и получил этот результат.Он был прав, это не здорово.С другой стороны, он выполняется за ~ 0,3 секунды.

let cycle xs = seq { while true do yield! xs }    
let accumusum xs = Seq.scan(fun acc elem -> acc + elem) 0 xs

let tryfind (sum, s:int Set) =
    match s.Contains(sum) with
    | true -> Some(sum)
    | false -> None

let scanstate (sum, s:int Set) el =
    el, s.Add(sum)

let findfreqcycle (data:int seq) =
    let seen = Seq.scan scanstate (Seq.head data, Set.empty) (Seq.tail data)
    Seq.pick tryfind seen

let data = cycle <| (input.Trim().Split('\n') |> Seq.map int |> Seq.toList)
accumusum data |> findfreqcycle

Answer 2

У OP уже есть принятый ответ, но я подумал, что предлагаю несколько вариантов.

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

Обычно мы fold собираем состояние, но fold не позволяет нам выйти рано.Вот почему было предложено использовать scan, который является потоковым fold + pick, который позволяет досрочно завершить работу.

Альтернативой является кодирование fold, которое позволяет создавать ярлыки, когда состояниедостигнуто: val foldAndCheck: (a' -> 'b -> CheckResult<'a, 'c>) -> 'a -> 'b seq -> 'c option.fold похож на цикл for, который агрегирует все значения, foldAndCheck похож на цикл for, который агрегирует значения до некоторой точки и затем возвращает результат.

Тогда он может выглядеть примерно так:

type [<Struct>] CheckResult<'T, 'U> =
  | Continue of c:'T
  | Done     of d:'U

// val foldAndCheck: (a' -> 'b -> CheckResult<'a, 'c>) -> 'a -> 'b seq -> 'c option
let foldAndCheck f z (s : _ seq) =
  let f = OptimizedClosures.FSharpFunc<_, _, _>.Adapt f
  use e = s.GetEnumerator ()
  let rec loop s =
    if e.MoveNext () then
      match f.Invoke (s, e.Current) with
      | Continue ss -> loop ss
      | Done     rr -> Some rr 
    else
      None
  loop z

let cycle xs = seq { while true do yield! xs }

let run (input : string) =
  let folder s v = if Set.contains v s then Done v else Continue (Set.add v s)
  input.Trim().Split('\n') 
  |> Seq.map int 
  |> cycle
  |> Seq.scan (+) 0
  |> foldAndCheck folder Set.empty

При запуске на моем компьютере я получаю такие числа:

Result: Some 448
Took  : 280 ms
CC    : (31, 2, 1)

(CC - сборщик мусора в поколениях 0, 1 и 2)

Затем я создалпрограмма на F #, которая, на мой взгляд, эквивалентна программе на Python, так как использует изменяемый набор и функцию mapWhile:

let addAndReturn (set : HashSet<_>) =
  fun v ->
    set.Add v |> ignore
    v

let mapWhile func pred (s : _ seq) =
  seq {
    // F# for v in s ->
    //  doesn't support short-cutting. So therefore the use while
    use e = s.GetEnumerator ()
    let mutable cont = true
    while cont && e.MoveNext () do
      let v = e.Current
      if not (pred v) then
        cont <- false
        yield func v
      else
        yield func v
  }

let cycle xs = seq { while true do yield! xs }

let accumulate xs = Seq.scan (+) 0 xs

let last xs = Seq.last xs

let run (input : string) =
  let data = input.Trim().Split('\n') |> Seq.map int 
  let s = HashSet<int> ()

  data
  |> cycle
  |> accumulate
  |> mapWhile (addAndReturn s) (fun x -> s.Contains x |> not)
  |> last

Числа производительности:

Result: 448
Took  : 50 ms
CC    : (1, 1, 1)

Если мы говорим, что мы разрешаемmutation + seq решение может выглядеть следующим образом:

let cycle xs = seq { while true do yield! xs }

let run (input : string) =
  let s = HashSet<int> ()

  input.Trim().Split('\n')
  |> Seq.map int 
  |> cycle
  |> Seq.scan (+) 0
  |> Seq.find (fun v -> s.Add v |> not)

, который работает следующим образом:

Result: 448
Took  : 40 ms
CC    : (1, 1, 1)

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

Answer 3

Как упоминалось в комментариях, Seq.tail ужасно неэффективно, особенно если вы используете его в цикле, как вы делаете.Причина в том, что он создает новую последовательность, которая выполняет итерации по исходной последовательности и пропускает первый элемент (поэтому после 1000 итераций вам нужно пройти более 1000 последовательностей, каждая из которых пропускает один элемент).

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

let rec findfreqcycle sum (s:int Set) input data = 
    match data with 
    | x::xs when s.Contains (sum + x) -> (sum + x)
    | x::xs -> findfreqcycle (sum + x) (s.Add (sum + x)) input xs
    | [] ->  findfreqcycle sum s input input

let data = input.Trim().Split('\n') |> Seq.map int |> Seq.toList 
findfreqcycle 0 Set.empty data data

Я изменил его так, чтобы он использовал сопоставление с шаблоном (в списках).Я также изменил код так, чтобы он занимал конечный список и, когда он доходит до конца, он запускается снова.Как следствие, он также суммирует числа на лету (вместо использования Seq.scan - это не сработало бы здесь, потому что я не использую бесконечные списки).

На входе от Pastebin я получаюрезультат 448 примерно за 0,17 секунды.