Производительность seq<int> vs Lazy<LazyList <int >> в F#
Существует хорошо известное решение для генерации бесконечного потока чисел Хэмминга (т.е. всех натуральных чисел n где n = 2^i * 3^j * 5^k). Я реализовал это двумя разными способами в F#. Первый метод использует seq<int>, Решение элегантное, но производительность ужасная. Второй метод использует пользовательский тип, где хвост оборачивается Lazy<LazyList<int>>, Решение неуклюже, но производительность потрясающая.
Может кто-нибудь объяснить, почему производительность с помощью seq<int> это так плохо и есть ли способ это исправить? Благодарю.
Способ 1 с использованием seq<int>,
// 2-way merge with deduplication
let rec (-|-) (xs: seq<int>) (ys: seq<int>) =
let x = Seq.head xs
let y = Seq.head ys
let xstl = Seq.skip 1 xs
let ystl = Seq.skip 1 ys
if x < y then seq { yield x; yield! xstl -|- ys }
elif x > y then seq { yield y; yield! xs -|- ystl }
else seq { yield x; yield! xstl -|- ystl }
let rec hamming: seq<int> = seq {
yield 1
let xs = Seq.map ((*) 2) hamming
let ys = Seq.map ((*) 3) hamming
let zs = Seq.map ((*) 5) hamming
yield! xs -|- ys -|- zs
}
[<EntryPoint>]
let main argv =
Seq.iter (printf "%d, ") <| Seq.take 100 hamming
0
Способ 2 с использованием Lazy<LazyList<int>>,
type LazyList<'a> = Cons of 'a * Lazy<LazyList<'a>>
// Map `f` over an infinite lazy list
let rec inf_map f (Cons(x, g)) = Cons(f x, lazy(inf_map f (g.Force())))
// 2-way merge with deduplication
let rec (-|-) (Cons(x, f) as xs) (Cons(y, g) as ys) =
if x < y then Cons(x, lazy(f.Force() -|- ys))
elif x > y then Cons(y, lazy(xs -|- g.Force()))
else Cons(x, lazy(f.Force() -|- g.Force()))
let rec hamming =
Cons(1, lazy(let xs = inf_map ((*) 2) hamming
let ys = inf_map ((*) 3) hamming
let zs = inf_map ((*) 5) hamming
xs -|- ys -|- zs))
[<EntryPoint>]
let main args =
let a = ref hamming
let i = ref 0
while !i < 100 do
match !a with
| Cons (x, f) ->
printf "%d, " x
a := f.Force()
i := !i + 1
0
3 ответа
Ганеш прав в том, что вы оцениваете последовательность несколько раз. Seq.cache поможет улучшить производительность, но вы получите гораздо лучшую производительность из LazyList потому что базовая последовательность вычисляется только один раз, а затем кэшируется, поэтому ее можно пройти намного быстрее. На самом деле, это хороший пример того, где LazyList следует использовать более нормального seq,
Похоже, что при использовании Seq.map Вот. Я считаю, что компилятор выделяет замыкание каждый раз, когда он вызывается там. Я изменил твой seq основанный код для использования seq-выражения там вместо этого, и это примерно на 1/3 быстрее, чем оригинал для первых 40 чисел в последовательности:
let rec hamming: seq<int> = seq {
yield 1
let xs = seq { for x in hamming do yield x * 2 }
let ys = seq { for x in hamming do yield x * 3 }
let zs = seq { for x in hamming do yield x * 5 }
yield! xs -|- ys -|- zs
}
Моя библиотека ExtCore включает в себя lazyList построитель вычислений, который работает так же, как seqтак что вы можете упростить ваш код следующим образом:
// 2-way merge with deduplication
let rec (-|-) (xs: LazyList<'T>) (ys: LazyList<'T>) =
let x = LazyList.head xs
let y = LazyList.head ys
let xstl = LazyList.skip 1 xs
let ystl = LazyList.skip 1 ys
if x < y then lazyList { yield x; yield! xstl -|- ys }
elif x > y then lazyList { yield y; yield! xs -|- ystl }
else lazyList { yield x; yield! xstl -|- ystl }
let rec hamming : LazyList<uint64> = lazyList {
yield 1UL
let xs = LazyList.map ((*) 2UL) hamming
let ys = LazyList.map ((*) 3UL) hamming
let zs = LazyList.map ((*) 5UL) hamming
yield! xs -|- ys -|- zs
}
[<EntryPoint>]
let main argv =
let watch = Stopwatch.StartNew ()
hamming
|> LazyList.take 2000
|> LazyList.iter (printf "%d, ")
watch.Stop ()
printfn ""
printfn "Elapsed time: %.4fms" watch.Elapsed.TotalMilliseconds
System.Console.ReadKey () |> ignore
0 // Return an integer exit code
(ПРИМЕЧАНИЕ: я также сделал ваш (-|-) функция универсальная и модифицированная hamming использовать 64-битные целые числа без знака, потому что 32-битные целые числа со знаком переполняются через некоторое время). Этот код проходит через первые 2000 элементов последовательности на моей машине за ~450 мс; первые 10000 элементов занимают ~3500мс.
Ваш seq за hamming переоценивается с самого начала для каждого рекурсивного вызова. Seq.cache некоторая помощь:
let rec hamming: seq<int> =
seq {
yield 1
let xs = Seq.map ((*) 2) hamming
let ys = Seq.map ((*) 3) hamming
let zs = Seq.map ((*) 5) hamming
yield! xs -|- ys -|- zs
} |> Seq.cache
Однако, как вы указываете LazyList все еще намного лучше на больших входах, даже если каждая отдельная последовательность кэшируется.
Я не совсем уверен, почему они отличаются более чем на небольшой постоянный фактор, но, возможно, лучше просто сосредоточиться на создании LazyList менее уродливо Написание чего-то, чтобы преобразовать это в seq делает обработку намного приятнее:
module LazyList =
let rec toSeq l =
match l with
| Cons (x, xs) ->
seq {
yield x
yield! toSeq xs.Value
}
Затем вы можете использовать свой простой main непосредственно. Также необязательно использовать мутацию для обработки LazyList Вы могли бы просто сделать это рекурсивно.
Определение не выглядит так плохо, хотя lazy а также Force() сделайте его немного загроможденным. Это выглядит немного лучше, если вы используете .Value вместо .Force(), Вы также можете определить конструктор вычислений для LazyList похож на seq один, чтобы восстановить действительно хороший синтаксис, хотя я не уверен, что оно того стоит.
Вот базовая версия последовательности с лучшей производительностью.
let hamming =
let rec loop nextHs =
seq {
let h = nextHs |> Set.minElement
yield h
yield! nextHs
|> Set.remove h
|> Set.add (h*2) |> Set.add (h*3) |> Set.add (h*5)
|> loop
}
Set.empty<int> |> Set.add 1 |> loop