使用记忆化在 Clojure 中实现 Levenshtein

Question

这是使用递归的 Clojure 的最小 Levenshtein（编辑距离）实现：

(defn levenshtein [s1, i1, s2, i2]
  (cond
    (= 0 i1) i2
    (= 0 i2) i1
    :else
    (min (+ (levenshtein s1 (- i1 1) s2 i2) 1)
         (+ (levenshtein s1 i1 s2 (- i2 1)) 1)
         (+ (levenshtein s1 (- i1 1) s2 (- i2 1)) (if (= (subs s1 i1 (+ i1 1)) (subs s2 i2 (+ i2 1))) 0 1))
         )
    )
  )

(defn levenshteinSimple [s1, s2]
  (levenshtein s1, (- (count s1) 1), s2, (- (count s2) 1)))

可以这样使用：

(println (levenshteinSimple "hello", "hilloo"))
(println (levenshteinSimple "hello", "hilloo"))
(println (levenshteinSimple "bananas", "bananas"))
(println (levenshteinSimple "ananas", "bananas"))

并打印：

如何将 memoize 添加到此实现中以提高性能？

请注意：我是 Clojure 初学者。这些是我在 Clojure 中的第一行

Answer 1

最简单的方法就是使用 memoize 函数。它需要一个函数，并且 return 是一个记忆函数：

(let [mem-lev (memoize levenshteinSimple]
  (println (mem-lev "hello", "hilloo"))
  (println (mem-lev "hello", "hilloo"))
  (println (mem-lev "bananas", "bananas"))
  (println (mem-lev "ananas", "bananas")))

mem-lev 会记住你给它的每个参数和你的函数 returns 的结果，如果它已经看到你给的参数，return 会缓存结果它。

请注意，这不会导致递归调用被记忆化，但任何递归调用都不太可能从记忆化中受益。

这也不会导致您的原始函数被记忆。在这个例子中，只有 mem-lev 会被记忆。如果你真的想要记忆你的全局函数，你可以将你的定义更改为：

(def levenshteinSimple
  (memoize
    (fn [s1, s2]
      ...

但我不建议这样做。这会导致函数本身保持状态，这是不理想的。它还会在程序运行期间保持该状态，如果滥用可能会导致内存问题。

（作为一个很好的练习，尝试编写您自己的 memoize 版本。我通过这样做学到了很多东西）。

使用记忆化在 Clojure 中实现 Levenshtein

Levenshtein implementation in Clojure with memoization

clojure

memoization

levenshtein-distance