performance - 使用差分法在 Clojure 中实现序列推理

Question

我在 Haskell 中读到，你可以创建这样的序列:[1,3..9] 我用 Clojure 写了一个版本，虽然我喜欢没有状态的编程，但空间复杂度很大。执行此操作的更有效方法是什么？

编辑:如果您有兴趣了解解决方案，您可以 read my blog post .

用例:

(infer-n [1 2] 10)     => [1 2 3 4 5 6 7 8 9 10]
(infer-n [1 4 9] 10)   => [1 4 9 16 25 ... 100]
(infer-range [9 7] 1)  => [9 7 5 3 1]

代码:

(defn diffs
  "(diffs [1 2 5 12 29]) => (1 3 7 17)" 
  [alist]
  (map - (rest alist) alist))

(defn const-diff
  "Returns the diff if it is constant for the seq, else nil.
   Non-strict version." 
  [alist]
  (let [ds (diffs alist)
        curr (first ds)]
    (if (some #(not (= curr %)) ds)
      nil
      curr)))

(defn get-next
  "Returns the next item in the list according to the
   method of differences.
   (get-next [2 4]) => 6"
  [alist]
  (+ (last alist)
     (let [d (const-diff alist)]
       (if (= nil d)
         (get-next (diffs alist))
         d))))

(defn states-of
  "Returns an infinite sequence of states that the
   input sequence can have.
  (states-of [1 3]) => ([1 3]
                        [1 3 5]
                        [1 3 5 7]
                        [1 3 5 7 9]...)"
  [first-state]
  (iterate #(conj % (get-next %)) first-state))

(defn infer-n
  "Returns the first n items from the inferred-list.
   (infer-n [1 4 9] 10) => [1 4 9 16 25 36 49 64 81 100]" 
  [alist n]
  (take n (map first (states-of alist))))

(defn infer-range
  "(infer-range [10 9] 1) => [10 9 8 7 6 5 4 3 2 1]" 
  [alist bound]
  (let [in-range (if (>= bound (last alist))
                    #(<= % bound)
                    #(>= % bound))]
    (last (for [l (states-of alist) :while (in-range (last l))] l))))

Answer 1

助手

(defn diff [s] (map - (rest s) s))

基于有限差分法推断序列

(defn infer-diff [s]
  (->> (take (count s) (iterate diff s)) 
       (map last) reverse 
       (drop-while zero?) ;optional 
       (iterate (partial reductions +))
       (map last) rest 
       (concat s)))

例子

(take 10 (infer-diff [1 3]))
;=> (1 3 5 7 9 11 13 15 17 19)

(take 10 (infer-diff [1 4 9]))
;=> (1 4 9 16 25 36 49 64 81 100)

解释

(def s (list 1 4 9))

(take (count s) (iterate diff s))
;=> ((1 4 9)
;    ( 3 5 )
;    (  2  ))

(map last *1)
;=> (9 5 2)

(reverse *1)
;=> (2 5 9)

这个 (2 5 9) 连续一阶差分金字塔切片是您确定序列其余部分所需的全部内容。

(reductions + *1)
;=> (2 7 16) and the next in the sequence is at the end: 16

(reductions + *1)
;=> (2 9 25) and the next in the sequence is at the end: 25

(reductions + *1)
;=> (2 11 36) and the next in the sequence is at the end: 36