带有记忆的榆树中最长的公共子序列

Question

我想在 elm 中制作 LCS 算法的高效版本。我喜欢这个 ocaml 版本，但它使用副作用来缓存结果。

let lcs xs ys =
  let cache = Hashtbl.create 16 in
  let rec lcs xs ys =
    try Hashtbl.find cache (xs, ys) with
    | Not_found ->
        let result =
          match xs, ys with
          | [], _ -> []
          | _, [] -> []
          | x :: xs, y :: ys when x = y ->
              x :: lcs xs ys
          | _ :: xs_rest, _ :: ys_rest ->
              let a = lcs xs_rest ys in
              let b = lcs xs      ys_rest in
              if (List.length a) > (List.length b) then a else b
        in
        Hashtbl.add cache (xs, ys) result;
        result
  in
  lcs xs ys

在elm中使用memoization怎么办？

Answer 1

您可能想研究使用 Lazy package, which does automatic memoization, or the elm-lazy package，它使用显式记忆。

通过将内部递归函数包装在 Lazy 中，您可以减少求值次数。在我的 https://ellie-app.com/4hXx2X753wfa1/0 示例中，惰性版本大约有 300 Debug 个日志条目，非惰性版本大约有 700 个条目。

Answer 2

Gilbert Kennen 在 slack 上给了我一个似乎更好用的版本：

lcs : List a -> List a -> List a
lcs xs ys =
    lcsHelper xs ys ( 0, 0 ) Dict.empty
        |> Dict.get ( 0, 0 )
        |> Maybe.map Tuple.second
        |> Maybe.withDefault []


lcsHelper : List a -> List a -> ( Int, Int ) -> Dict ( Int, Int ) ( Int, List a ) -> Dict ( Int, Int ) ( Int, List a )
lcsHelper xs ys position memo =
    case ( Dict.get position memo, xs, ys ) of
        ( Nothing, x :: xRest, y :: yRest ) ->
            let
                nextYPos =
                    Tuple.mapSecond ((+) 1) position

                nextXPos =
                    Tuple.mapFirst ((+) 1) position

                newMemo =
                    memo
                        |> lcsHelper xs yRest nextYPos
                        |> lcsHelper xRest ys nextXPos

                best =
                    maxListTuple
                        (get nextXPos newMemo)
                        (get nextYPos newMemo)
                        |> consIfEqual x y
            in
                Dict.insert position best newMemo

        _ ->
            memo

get : ( Int, Int ) -> Dict ( Int, Int ) ( Int, List a ) -> ( Int, List a )
get position memo =
    Dict.get position memo |> Maybe.withDefault ( 0, [] )


maxListTuple : ( Int, List a ) -> ( Int, List a ) -> ( Int, List a )
maxListTuple ( xLen, xs ) ( yLen, ys ) =
    if yLen > xLen then
        ( yLen, ys )
    else
        ( xLen, xs )


consIfEqual : a -> a -> ( Int, List a ) -> ( Int, List a )
consIfEqual x y ( listLen, list ) =
    if x == y then
        ( listLen + 1, x :: list )
    else
        ( listLen, list )

它使用字典来缓存结果。

带有记忆的榆树中最长的公共子序列

longest common subsequence in elm with memoization

memoization

lcs

elm