map part of the vector efficiently in clojure

Question

I wonder how this can be done in Clojure idiomatically and efficiently:

1) Given a vector containing n integers in it: [A₀ A₁ A₂ A₃ ... A_n]

2) Increase the last x items by 1 (let's say x is 100) so the vector will become: [A₀ A₁ A₂ A₃ ... (A_n-99 + 1) (A_n-98 + 1)... (A_n-1 + 1) (A_n + 1)]

One naive implementation looks like:

(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]

In this implementation, basically you just map the entire vector to another vector by examine each item to see if it needs to be increased.

However, this is an O(n) operation while I only want to change the last x items in the vector. Ideally, this should be done in O(x) instead of O(n).

I am considering using some functions like split-at/concat to implement it like below:

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

However, I am not sure if this implementation is O(n) or O(x). I am new to Clojure and not really sure what the time complexity will be for operations like concat/split-at on persistent data structures in Clojure.

So my questions are:

1) What the time complexity here in second implementation?

2) If it is still O(n), is there any idiomatic and efficient implementation that takes only O(x) in Clojure for solving this problem?

Any comment is appreciated. Thanks.

Update:

noisesmith's answer told me that split-at will convert the vector into a list, which was a fact I did not realised previously. Since I will do random access for the result (call nth after processing the vector), I would like to have an efficient solution (O(x) time) while keeping the vector instead of list otherwise nth will slow down my program as well.

double checking your question, I was surprised to see that the implementation of split-at not only doesn't work in O(n) time (expected because it is implemented on non-associative datastructures), but it also walks the first (count - n) elements (or first n arguments in your version, actually inc-first) twice! — noisesmith

noisesmith noisesmith · Accepted Answer · 2013-12-09T04:24:20

Concat and split-at both turn the input into a seq, effectively a linked-list representation, O(x) time. Here is how to do it with a vector for O(n) performance.

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]

This will fail on input that is not associative (like seq / lazy-seq) because there is no O(1) access time in non-associative types.

map part of the vector efficiently in clojure

2 Answers