Ошибка производительности F #?

Question

let test1fun x = [for i in 1..x-> i]

let test2fun x y= [for i in 1..x
                    do for i in 1..y-> i]

let  singlesearcher i =
    let rec searcher j agg =
        if j > i 
        then agg 
        else searcher (j+1) (i::agg)
    searcher 1 []


let  doublesearcher i j =
    let rec searcher k l agg =
        if k > i 
        then searcher 1 (l+1) agg
        else if l > j 
             then agg
             else searcher (k+1) l ((k,l)::agg)
    searcher 1 1 []

выполнение вышеуказанного с #time и 10000 для всех входов дает

list comprehension/singlesearcher-> negligable
cross product -> 320
list comprehension crossproduct -> 630

Почему понимание вложенного списка более чем вдвое превышает функциональную версию?

Answer 1

Да. Понимание списка обычно медленнее, чем непосредственное использование списка или массива F #. (На моей машине я также нахожу похожее время с вами.)

Давайте посмотрим, как они реализованы. Версия для понимания списка на самом деле довольно сложна:

1. последовательность / IEnumerable<int> создается с использованием синтаксиса понимания. Это просто ленивая последовательность, здесь мало времени.

2. , затем эта последовательность преобразуется в F # List с помощью чего-то вроде Seq.toList. Фактическое время проводится здесь. Здесь выполняется много кода типа HasNext MoveNext и switch (state). С таким большим количеством вызовов функций вы не можете ожидать этого быстро.

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

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