F# с помощью кэша последовательности правильно
Я не думаю, что кто-то упоминал об этом: использование alloca в функции будет препятствовать или отключать некоторые оптимизации, которые могли бы быть применены в функции, так как компилятор не может знать размер фрейма стека функции.
Например, общая оптимизация компиляторами C заключается в том, чтобы исключить использование указателя кадра внутри функции, вместо этого осуществляется доступ к кадру относительно указателя стека; так что есть еще один регистр для общего пользования. Но если в функции вызывается alloca, разница между sp и fp будет неизвестна для части функции, поэтому такая оптимизация не может быть выполнена.
Учитывая редкость его использования и его теневое состояние в качестве стандартной функции, разработчики компилятора вполне могут отключить любую оптимизацию, чтобы могла вызвать проблемы с alloca, если бы потребовалось больше, чем немного усилий, чтобы заставить его работать с alloca.
ОБНОВЛЕНИЕ: Так как локальные массивы переменной длины были добавлены в C и C ++, и так как они представляют очень похожие проблемы генерации кода для компилятора как alloca, я вижу, что «редкость статус использования и тенистости »не относится к основному механизму; но я все еще подозреваю, что использование alloca или VLA ведет к компрометации процесса генерации кода внутри функции, которая их использует. Буду рад любым отзывам дизайнеров компиляторов.
3 ответа
Seq.cache кэширует экземпляр IEnumerable , так что каждый элемент в последовательности вычисляется только один раз. В вашем случае, однако, вы кэшируете последовательность, возвращаемую функцией, и каждый раз, когда вы вызываете функцию, вы получаете новую кэшированную последовательность, которая не приносит вам никакой пользы. Я не думаю, что кэширование - действительно правильный подход к вашей проблеме, как вы ее обозначили; вместо этого вам, вероятно, следует изучить мемоизацию.
Если вместо определения функции, дающей простые числа меньше, чем n , вы хотите определить бесконечную перечислимую последовательность простых чисел, то кеширование имеет больше смысла. Это будет выглядеть примерно так:
let rec upFrom i =
seq {
yield i
yield! upFrom (i+1)
}
let rec primes =
seq {
yield 2
yield!
upFrom 3 |>
Seq.filter (fun p -> primes |> Seq.takeWhile (fun j -> j*j <= p) |> Seq.forall (fun j -> p % j <> 0))
}
|> Seq.cache
Я не сравнивал производительность этого метода с вашим.
Я понял, как решить мою проблему с помощью свертки, но не решил использовать seq.cache.
let primesNot1 n =
{2 .. n}
|> Seq.fold (fun primes i ->
if primes |> Seq.for_all (fun o -> i % o <> 0) then
List.append primes [i]
else
primes) [2]
Вы смотрели LazyList? Похоже, он предназначен для решения той же проблемы. Он находится в PowerPack.