как вставить в середину списка, будучи удобным для хвостового вызова, но без ущерба для производительности?

Итак, у меня есть эта функция, которая кажется не дружественной к хвостовому вызову, верно?

let rec insertFooInProperPosition (foo: Foo) (bar: list<Foo>): list<Foo> =
    match bar with
    | [] -> [ foo ]
    | head::tail ->
        if (foo.Compare(head)) then
            foo::bar
        else
            head::(insertFooInProperPosition foo tail)

Затем я пытаюсь понять, как использовать аккумулятор, чтобы последнее, что делает функция, — это сам вызов, и у меня получается следующее:

let rec insertFooInProperPositionTailRec (foo: Foo) (headListAcc: list<Foo>) (bar: list<Foo>): list<Foo> =
    match bar with
    | [] -> List.concat [headListAcc;[ foo ]]
    | head::tail ->
        if (foo.Compare(head)) then
            List.concat [headListAcc; foo::bar]
        else
            insertFooInProperPosition foo (List.concat [headListAcc;[head]]) tail

let rec insertFooInProperPosition (foo: Foo) (bar: list<Foo>): list<Foo> =
    insertFooInProperPositionTailRec foo [] bar

Однако, насколько я понимаю, использование List.concat сделало бы эту функцию намного менее эффективной, верно? Итак, как мне правильно выполнить это преобразование?


recursion f# tail-recursion tail-call-optimization tail-call
person user1623521    schedule 17.01.2018    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Ваше решение выглядит нормально, если требуется использование рекурсии. Однако эту задачу можно решить без рекурсии (и немного быстрее).

Для объединения двух списков необходимо скопировать первый список, а его последний элемент должен указывать на первый элемент второго списка. Это O(N), где N — размер первого списка. Растущий список в хвосте требует нескольких конкатенаций, в результате чего список обхода для каждого N, что делает сложность квадратичной (надеюсь, я здесь).

Вместо рекурсивного подхода, который добавляет элементы в список, более быстрый подход, вероятно, состоял бы в том, чтобы найти индекс вставки, а затем скопировать все элементы перед ним за один раз, а затем объединить его с новым элементом и остальной частью списка. Для этого требуется всего три прохода по списку, поэтому O (N).

let insertFooInProperPosition (foo : Foo) (bar : Foo list) : Foo list =
    bar
    |> List.tryFindIndex (fun v -> v.Compare foo)
    |> function | None -> List.append bar [ foo ]
                | Some i -> let before, after = List.splitAt i bar
                            List.concat [ before; [ foo ]; after ]
person Alex Netkachov    schedule 17.01.2018
comment
Благодарность! но, тем не менее, три прохода по списку кажутся несколько чрезмерными, учитывая, что первая версия (не дружественная к хвостовому вызову) выполняла только один проход! :'-( - person user1623521; 17.01.2018
comment
не совсем, потому что он возвращается из рекурсии, что тоже считается. - person Alex Netkachov; 17.01.2018
comment
рекурсия считается потреблением памяти, но не совсем производительностью O(x), верно? Кстати, что вы думаете о моей альтернативе? - person knocte; 17.01.2018
comment
рекурсия считается потреблением памяти - если она не оптимизирована хвостом, то да, требуется выделение кадра стека. Также, если его нужно вызывать для каждого элемента, это O (длина списка). - person Alex Netkachov; 17.01.2018

arrow_upward
1
arrow_downward

К сожалению, вы не можете построить список F# от начала до конца (если вы не используете функции, внутренние для библиотеки F# Core, которые используют мутацию под капотом). Поэтому лучшая идея, вероятно, состоит в том, чтобы создать новый список из старого, добавляя следующие элементы по мере продвижения и вставляя foo в нужном месте. В конце новый список переворачивается, чтобы получить тот же порядок, что и старый список:

let insertFoo (foo : Foo) bar =
    let rec loop acc = function
        | [] -> prep (foo :: acc) []
        | x :: xs ->
            if foo.Compare x
            then prep (x :: foo :: acc) xs
            else loop (x :: acc) xs
    and prep acc = function
        | [] -> acc
        | x :: xs -> prep (x :: acc) xs
    loop [] bar |> List.rev

Я думаю, @knocte был быстрее с эквивалентным решением…

person dumetrulo    schedule 17.01.2018
comment
Я думаю, вам не нужно and, если вы поставите prep перед loop? - person knocte; 17.01.2018
comment
Ничего особенного… без and пришлось бы переместить prep выше loop… - person dumetrulo; 17.01.2018

arrow_upward
1
arrow_downward

Решение @AlexAtNet выглядит неплохо, но если вы все еще хотите рекурсию, вы можете избежать такого большого количества вызовов concat следующим образом:

let rec insertFooInProperPositionTailRec (foo: Foo)
                                         (headListAcc: list<Foo>)
                                         (bar: list<Foo>)
                                         : list<Foo> =
    match bar with
    | [] -> List.rev (foo::headListAcc)
    | head::tail ->
        if (foo.Compare(head)) then
            let newAcc = List.rev headListAcc
            [ yield! newAcc
              yield! foo::bar ]
        else
            let newAcc = head::headListAcc
            insertFooInProperPositionTailRec foo newAcc tail

let rec insertFooInProperPosition (foo: Foo) (bar: list<Foo>): list<Foo> =
    insertFooInProperPositionTailRec foo [] bar

Не уверен, что он более эффективен, чем у @AlexAtNet, ммм...

person knocte    schedule 17.01.2018
comment
да, накопление списка из головы, а затем его обращение - хороший трюк, использование стека - еще одна альтернатива, которая делает его очень близким к тому, что происходит в решении без оптимизации хвоста. - person Alex Netkachov; 17.01.2018