Vector concatenation

[puzzler]

subvec is O(1) because it takes advantage of sharing. This is quite
useful.

Is there a way to write concatvec in an O(1) way, taking advantage of
sharing?
I suspect that the "obvious way" to concatenate vectors, i.e., (into
[] (concat v1 v2)), would be O(n).

[pmf]

There's lazy-cat, if that's an option for you..

[Meikel Brandmeyer]

Hi,

Am 30.11.2008 um 10:00 schrieb puzzler:
> Is there a way to write concatvec in an O(1) way, taking advantage of
> sharing?
> I suspect that the "obvious way" to concatenate vectors, i.e., (into
> [] (concat v1 v2)), would be O(n).

You may want to use the reduce with conj.

(reduce conj v1 v2)

This is O(count v2).

Sincerely
Meikel

[hoeck]

Another way would be to create a proxy of the vector class, eg:

(defn concat-vector [a b]
(proxy [clojure.lang.APersistentVector] []
(seq [] (concat a b))
(length [] (+ (count a) (count b)))
(cons [e] (conj (reduce conj a b) e))
(nth [i] (if (< i (count a)) (a i) (b (- i (count a)))))))

which threads the operations to the underlying vectors. Given this
simple clojure implementation, its only faster for big (~ more than
100 elements) vectors, and if you conj onto it, its doing the work of
concat anyway.

[Meikel Brandmeyer]

Hi,

On 30 Nov., 12:10, Meikel Brandmeyer <m...@kotka.de> wrote:
> (reduce conj v1 v2)

And as pointed out by Rich: (into v1 v2).

Sincerely
Meikel