algorithm - 在 clojure 中有效地映射向量的一部分

Question

我想知道如何在 Clojure 中以惯用的方式有效地完成此操作:

1) 给定一个包含 n 个整数的向量:[A₀ A₁ A₂ A₃ ... A_n]

2) 将最后的 x 项增加 1(假设 x 为 100)，因此向量将变为:[A₀ A₁ A₂ A₃ ... (A_n-99 + 1) (A_n-98 + 1)... (A _n-1 + 1) (A_n + 1)]

一个简单的实现如下:

(defn inc-last [x nums]
  (let [n (count nums)]
      (map #(if (>= % (- n x)) (inc %2) %2)
           (range n) 
           nums)))

(inc-last 2 [1 2 3 4]) 
;=> [1 2 4 5]

在此实现中，基本上您只需通过检查每个项目以查看它是否需要增加，将整个向量映射到另一个向量。

但是，这是一个复杂度为 O(n) 的操作，而我只想更改向量中的最后 x 个项目。理想情况下，这应该在 O(x) 而不是 O(n) 中完成。

我正在考虑使用像 split-at/concat 这样的函数来实现它，如下所示:

(defn inc-last [x nums]
  (let [[nums1 nums2] (split-at x nums)]
    (concat nums1 (map inc nums2))))

但是，我不确定这个实现是 O(n) 还是 O(x)。我是 Clojure 的新手，不确定 Clojure 中持久数据结构上的 concat/split-at 等操作的时间复杂度是多少。

所以我的问题是:

1)第二次实现的时间复杂度是多少？

2) 如果仍然是 O(n)，那么在 Clojure 中是否有任何只需要 O(x) 的惯用且高效的实现来解决这个问题？

任何意见表示赞赏。谢谢。

更新:

noisesmith 的回答告诉我 split-at 会将向量转换为列表，这是我之前没有意识到的事实。由于我将对结果进行随机访问(在处理向量后调用 nth)，我希望有一个有效的解决方案(O(x) 时间)，同时保留向量而不是列表，否则 nth 也会减慢我的程序。

Answer 1

Concat 和 split-at 都将输入转换为 seq，实际上是一个链表表示，时间复杂度为 O(x)。以下是如何使用向量实现 O(n) 性能。

user> (defn inc-last-n
        [n x]
        (let [count (count x)
              update (fn [x i] (update-in x [i] inc))]
          (reduce update x (range (- count n) count))))
#'user/inc-last-n
user> (inc-last-n 3 [0 1 2 3 4 5 6])
[0 1 2 3 5 6 7]

这将在非关联输入(如 seq/lazy-seq)上失败，因为在非关联类型中没有 O(1) 访问时间。