Медленная хвостовая рекурсия в F # - PullRequest
Новая
       23

Медленная хвостовая рекурсия в F #

4 голосов
/ 28 марта 2011

У меня есть функция F #, которая возвращает список чисел, начиная с 0 в шаблоне пропуска n, выберите n, пропустите n, выберите n ... до предела. Например, эта функция для входа 2 вернет [2, 3, 6, 7, 10, 11...].

Изначально я реализовал это как нерекурсивную функцию, как показано ниже: 

let rec indicesForStep start blockSize maxSize =
    match start with
    | i when i > maxSize -> []
    | _ -> [for j in start .. ((min (start + blockSize) maxSize) - 1) -> j] @ indicesForStep (start + 2 * blockSize) blockSize maxSize

Считая, что хвостовая рекурсия желательна, я переопределил ее, используя список аккумуляторов следующим образом: 

let indicesForStepTail start blockSize maxSize =
    let rec indicesForStepInternal istart accumList =
        match istart with
        | i when i > maxSize -> accumList
        | _ -> indicesForStepInternal (istart + 2 * blockSize) (accumList @ [for j in istart .. ((min (istart + blockSize) maxSize) - 1) -> j])
    indicesForStepInternal start []

Однако, когда я запускаю это в fsi под Mono с параметрами 1, 1 и 20000 (т.е. должно возвращать [1, 3, 5, 7...] до 20000), хвостовая рекурсивная версия значительно медленнее, чем первая версия (на 12 секунд по сравнению с к югу от второго).

Почему хвостовая рекурсивная версия медленнее? Это из-за конкатенации списков? Это оптимизация компилятора? Реально ли я это реализовал?

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

Ответы [ 3 ]

8 голосов
/ 28 марта 2011

Как указывает Дейв, проблема в том, что вы используете оператор @ для добавления списков. Это более значительная проблема производительности, чем хвостовая рекурсия. Фактически, хвостовая рекурсия на самом деле не слишком ускоряет программу (но она заставляет ее работать на больших входах, где стек переполняется).

Причина, по которой ваша вторая версия медленнее, заключается в том, что вы добавляете более короткий список (созданный с помощью [...]) в более длинный список (accumList). Это медленнее, чем добавление более длинного списка в более короткий список (потому что операция должна копировать первый список).

Вы можете исправить это, собрав элементы в аккумуляторе в обратном порядке, а затем поменяв их местами, прежде чем вернуть результат: 

let indicesForStepTail start blockSize maxSize =
    let rec indicesForStepInternal istart accumList =
        match istart with
        | i when i > maxSize -> accumList |> List.rev
        | _ -> 
           let acc = 
             [for j in ((min (istart + blockSize) maxSize) - 1) .. -1 .. istart -> j] 
             @ accumList
           indicesForStepInternal (istart + 2 * blockSize) acc
    indicesForStepInternal start []

Как вы можете видеть, этот список имеет более короткий список (сгенерированный с использованием [...]) в качестве первого аргумента @, и на моей машине он имеет производительность, аналогичную нерекурсивно-рекурсивной версии. Обратите внимание, что понимание [ ... ] генерирует элементы в обратном порядке - так что они могут быть обращены обратно в конце.

Вы также можете написать все более красиво, используя синтаксис F # seq { .. }. Вы можете полностью избежать использования оператора @, поскольку он позволяет вам выдавать отдельные элементы, используя yield, и выполнять хвостово-рекурсивные вызовы, используя yield!: 

let rec indicesForStepSeq start blockSize maxSize = seq {
    match start with
    | i when i > maxSize -> ()
    | _ -> 
      for j in start .. ((min (start + blockSize) maxSize) - 1) do
        yield j
      yield! indicesForStepSeq (start + 2 * blockSize) blockSize maxSize }

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

РЕДАКТИРОВАТЬ С поправкой от Daniel, версия Seq на самом деле немного быстрее!

7 голосов
/ 28 марта 2011

В F # тип списка реализован как односвязный список. Из-за этого вы получаете различную производительность для x @ y и y @ x, если x и y имеют разную длину. Вот почему вы видите разницу в производительности. (x @ y) имеет время выполнения X.length. 

// e.g.
let x = [1;2;3;4]
let y = [5]

Если вы сделали x @ y, то x (4 элемента) будет скопировано в новый список, а его внутренний следующий указатель будет установлен на существующий список y. Если вы сделали y @ x, то y (1 элемент) будет скопирован в новый список, а его следующий указатель будет установлен на существующий список x.

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

let indicesForStepTail start blockSize maxSize =
    [ 
        for block in start .. (blockSize * 2) .. (maxSize - 1) do
            for i in block .. (block + blockSize - 1) do
                yield i
    ]
6 голосов
/ 28 марта 2011

Похоже, что добавление в список является проблемой. Append - это в основном операция O (N) для размера первого аргумента. Накапливаясь слева, эта операция занимает время O (N ^ 2).

То, как это обычно делается в функциональном коде, заключается в том, чтобы накапливать список в обратном порядке (накапливая справа), а затем в конце вернуть обратный список.

Первая версия, которая у вас есть, позволяет избежать проблемы добавления, но, как вы указали, не является хвостовой рекурсивностью.

В F #, вероятно, самый простой способ решить эту проблему - с помощью последовательностей. Это не очень функциональный вид, но вы можете легко создать бесконечную последовательность, следуя вашему шаблону, и использовать Seq.take, чтобы получить интересующие вас элементы.

...