0

How can I concatenate two sequences of lists (either lists of lists or vectors of lists) in constant time (independent of their size)?

JAre
  • 175
  • 5

1 Answers1

2

I'm not sure you can avoid some size dependent time cost as you'll need to iterate over one list or the other to join them together. If you know your new list is shorter than the list you are adding to then you can just push them to the front:

(let ((l '(4 5 6 7))
      (n '(2 3)))
  (cl-map 'nil (lambda (x) (push x l)) n)
  l) ==> (3 2 4 5 6 7)

That said I tend to favour the dash functions and just -concat:

(let ((l '(4 5 6 7))
      (n '(2 3)))
          (-concat n l)))

which according to disassemble ends up with almost the same byte code but probably because it can optimise the simple example.

stsquad
  • 4,626
  • 28
  • 45
  • Currently I'm using `nconc`. It should only iterate over the first list (A) to find its cdr. So it adds the long resulting list (B) to the tail of the short one (A). Then I set the variable that points to (B) to (A). The problem with this approach is that it mess up the order. I want (A) to be (B)s tail. Maybe there is a way to save (B) tail in a separate variable - add (A) to it and set (B) tail to (A) tail ? – JAre Jan 14 '21 at 13:53
  • 1
    @JAre: do you have specific ordering requirements? One common idiom is to build up a list with push and then finally nreverse the list at the end. You could always track start and end points for each list in some sort of structure and then manually tweak the list with setcdr but then you might start to question your data structures and what you are trying to achieve. – stsquad Jan 14 '21 at 14:43