4
\$\begingroup\$

I wrote a function split-seq-by-n which accepts a sequence and a number and splits the sequence into subsequences of length n (the last subsequence getting the remaining elements). It works on all subclasses of 'sequence, among others 'string, 'cons, 'vector etc.

;; Splits sequence into subsequences of length n
(defun split-seq-by-n (seq n)
  (labels ((seq-split (seq n &optional acc orig-n)
         (cond ((zerop (length seq)) (nreverse acc))
           ((zerop n) (seq-split seq 
                          orig-n
                          (cons (subseq seq 0 0) acc)
                          orig-n))
           (t (seq-split (subseq seq 1)
                      (1- n) 
                      (cons (concatenate (class-of seq) 
                             (if acc (car acc) (subseq seq 0 0))
                             (list (elt seq 0)))
                        (cdr acc))
                      orig-n)))))
    (seq-split seq n nil n)))

Any comments, improvements, critiques welcome.

\$\endgroup\$
4
\$\begingroup\$

It looks okay for a recursion exercise, but it's naive code. Not usable in 'production'.

  • it conses like mad. It creates a lot of intermediate garbage. Splitting a string involves making lots of smaller strings.
  • for lists it is not efficient, too
  • CONCATENATE in loops or recursive functions is a code smell
  • the recursive implementation with the subroutine is good style in a functional language, but makes it hard to debug in the real world. For example, how do you TRACE the internal function?
  • Common Lisp does not guarantee tail call optimization (TCO). Individual implementations do support it. Still, for general portable code it might be preferable to code loop.
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

When writing functions for manipulating sequences, it's typically easier to write a version that handles the list case specially, and then uses the generic sequence functions for everything else (since they'll probably be fine for vectors). Taking that approach, I'd write the following code. The main interface, split-seq-by-n takes the sequence and the n, and calls either split-list-by-n (optimized for lists) or split-sequence-by-n (which works for generic sequences, and so is probably efficient for vectors):

(defun split-seq-by-n (sequence n)
  (if (listp sequence) 
      (split-list-by-n sequence n)
      (split-sequence-by-n sequence n)))

(defun split-sequence-by-n (sequence n)
  (loop 
     :with length := (length sequence)
     :for start :from 0 :by n :below length
     :collecting (subseq sequence start (min length (+ start n)))))

(defun split-list-by-n (list n)
  (do ((nn (1- n) (1- nn))
       (part '())
       (parts '()))
      ((endp list) 
       (nreverse (if (endp part) parts
                     (list* (nreverse part) parts))))
    (push (pop list) part)
    (when (zerop nn)
      (push (nreverse part) parts)
      (setf part '()
            nn n))))

Since the generic sequence functions should be fine for sequences that support random indexing, split-sequence-by-n is pretty straightforward. The only bit that's a little complex it caching the length at first so that we have a maximum value for the end value in subseq. split-list-by-n is a bit more complex. It iterates over the list just once, allocating only as much new structure as is strictly necessary.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ that's nice. I particularly like your use of list* instead of cons. \$\endgroup\$ – Wojciech Gac Mar 11 '14 at 23:37
  • \$\begingroup\$ @WojciechGac When I'm working with conses as lists, I use first, rest, and list*. When I'm working with them as trees, I use car, cdr, and cons. \$\endgroup\$ – Joshua Taylor Mar 11 '14 at 23:55
1
\$\begingroup\$

@coredump, here's a slightly simplified version of the splitter. It does more or less the same things as your version, except for the :sharedp keyword:

(defun emptyp (sequence)
  (typecase sequence
    (null  t)
    (array (zerop (length sequence)))
    (otherwise nil)))

(defun partition (sequence n)
  (let* ((tail (subseq sequence n))
         (head (if (emptyp tail)
                   sequence
                   (subseq sequence 0 n))))
    (values head tail)))

(defun split (sequence n &key (last :undersized) (result-type 'list))
  (let ((raw-seq (mapcar (lambda (x) (coerce x result-type)) 
                         (loop
                            with head
                            until (emptyp sequence)
                            do
                              (multiple-value-setq (head sequence)
                                (partition sequence n))
                            collect head))))
    (if (< (length (car (last raw-seq))) n)
        (ecase last
          (:undersized
           raw-seq)
          (:oversized
           (multiple-value-bind (regular oversized)
               (partition raw-seq (- (length raw-seq) 2))
             (append regular 
                     (list (apply #'(lambda (x y) 
                                      (concatenate result-type x y)) oversized)))))
          (:truncated
           (multiple-value-bind (regular oversized)
               (partition raw-seq (1- (length raw-seq)))
             (values regular (coerce (car oversized) result-type)))))
        raw-seq)))
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Your code works but has some efficieny problems, as already pointed out by Rainer Joswig ("it conses like mad"). Now that you posted a modified version I added some details at the end of the answer.

Alternative approach

I like Joshua Taylor's answer because it is both efficient and simple. However, I'd like to take another approach and define split-n efficiently (by, e.g. avoiding whenever possible needless memory allocation) while providing more control to the programmer over the function's behavior (like standard functions and macros in Common Lisp generally do; e.g. eof-error-p in read-line, :test, :key and :from-end arguments, etc.).

All the following code can be found here.

Design

This was unexpected:

the last subsequence getting the remaining elements

I agree that this behavior might be desirable, but I think the expected property of the split function would be to return sequences having no more than n elements. We can see that this is the behavior of serapeum:batches, which is another interesting implementation to read.

I'd rather have split-n let me choose what to do with the remaining parts. That's why I add a :last argument which may take the following values:

  • :undersized: have a last group with fewer elements
  • :oversized: join the remaining elements with the preceding group (what you want)
  • :truncated: discard the remaining elements and return them as another value

The default value when no argument is given, or when T or NIL are given, would be what I consider the least suprising option, namely :undersized. I think :truncate should be asked for explicitely because it changes the expected return values.

Moreover, the function can be used in more circumstances if we have a way to allow (resp. disallow) the resulting parts from sharing data with the original sequence. This can be controlled by a boolean :sharedp argument (see e.g. CL-PPCRE).

For example, splitting an array into sub-arrays of n elements could possibly return displaced arrays: any modification to the original element would be visible in the corresponding sub-array, and inversely.

Likewise, it may be desirable that an original list and the splitted lists share a common tail: imagine a queue where a producer adds elements to the end of the queue, and a consumer function extracts elements by batches of n elements; the following call:

(split-n queue n :last :truncated :sharedp t)

... would grab a lists of sequences of size n, and the remaining elements returned as a second value would be the new head of the queue, the tail being left untouched.

Finally, we may want to control the type of the output sequence, as suggested in comments. For now, the accepted result type is either list or vector. We could also pass a function designator so that we can feed directly a consumer with the subsequences instead of collecting them first (see do-batches in the pasted code).

Return values

split-n returns 2 values:

  1. a list of non-empty subsequences of sequence

    • if :last is :undersized, the only subsequence that may not have exactly n elements is the last subsequence; if so, it contains 1 or more elements but less than n.
    • if :last is :oversized, all subsequences but the last have exactly n elements; the last subsequence can contain fewer or more than n elements (fewer if n is larger than the size of the original sequence; more if the size is larger but not exactly divisible by n).
    • if :last is :truncated, all returned subsequences have exactly n elements
  2. A generalized boolean which indicates whether there were remaining elements:

    • if NIL, the original sequence was evenly split.
    • otherwise, the value depends on the :last argument:

      • if :truncated, the secondary value is a list of at most n-1 elements not included in the primary list.
      • otherwise, the secondary value is the size of the last element in the primary sequence: it is necessarly lower than n when :last is :undersized, and different than n when :last is :oversized.

Remarks

In a previous version, I used serapeum:collecting but since we are interested in having different possible return types (list or vectors), I wrote little helper functions to collect elements.

(defparameter *pouch* nil)

(defun queue-collector ()
  (let ((q (serapeum:queue)))
    (cons
     (lambda (x) (serapeum:enq x q))
     (lambda () (serapeum:qlist q)))))

(defun vector-collector (size)
  (let ((v (make-array size :fill-pointer 0 :adjustable nil)))
    (cons
     (lambda (x) (vector-push x v))
     (lambda () v))))

(defun take (value &optional (cons *pouch*))
  (funcall (car cons) value))

(defun loot (&optional (cons *pouch*))
  (funcall (cdr cons)))

(defun call-while-hoarding (function &key (result-type 'list) size)
  (let ((*pouch* (ecase result-type
                        (list (queue-collector))
                        (vector (if size
                                    (vector-collector size)
                                    (unbounded-vector-collector))))))
    (funcall function)))

(defmacro hoarding ((&rest args) &body body)
  ;; parse: name is optional
  (let* ((name-p (not (keywordp (first args))))
         (args (if name-p (cdr args) args))
         (name (when name-p (car args))))
    `(funcall #'call-while-hoarding
            (lambda ()
              ,@(if name
                    `((let ((,name *pouch*)) ,@body))
                    body))
            ,@args)))

The hoarding macro binds a new collector in the special variable *pouch*, which is a cons of two closures: one to collect elements, the other to retrieve all collected elements. Those closures are respectively called by helper functions, take and loot.

Contrary to serapeum:collecting, collectors can be named and specialized on the return type. Unfortunately, the return-type option is not as smart as the one for map which accepts type specifier with element types and sizes. Here, the expected size can be specified too, but no check is done to ensure that (loot) returns a collection of the expected size (we can call (loot) multiple times, after all).

Main function

(defun split-n (sequence n
                 &key last sharedp (result-type 'list)
                 &aux (size (length sequence)))
  (check-type sequence sequence)
  (check-type n (integer 1 *))
  ;; let the value be checked by "hoarding"
  ;; (check-type result-type (member list vector))
  (ecase last
    ((nil t) (setf last :undersized))
    ((:truncated :oversized :undersized) last))
  (let ((slice
          (etypecase sequence
            (vector
             (let* ((type (array-element-type sequence))
                    (beg 0)
                    (end n)
                    (copy (if sharedp
                              (lambda (b e)
                                (make-array (- e b)
                                            :displaced-to sequence
                                            :displaced-index-offset b
                                            :element-type type))
                              (lambda (b e)
                                (subseq sequence b e)))))
               (lambda (&optional tail)
                 (if tail
                     (when (< beg size)
                         (funcall copy beg size))
                     (prog1 (funcall copy beg end)
                       (setf beg end
                             end (+ n end)))))))
            (list
             (let ((copy
                     (if sharedp #'identity #'copy-list))
                   (current sequence))
               (lambda (&optional tail)
                 (when current
                   (if tail
                       (funcall copy current)
                       (prog1 (subseq current 0 n)
                         (setf current (nthcdr n current)))))))))))
    (multiple-value-bind (count remainder) (truncate size n)
      (hoarding (:result-type result-type
                 :size (ecase last
                         (:undersized (+ count (signum remainder)))
                         (:oversized count)
                         (:truncated count)))
        (dotimes (_ (ecase last
                      (:undersized count)
                      (:oversized (1- count))
                      (:truncated count)))
          (take (funcall slice)))
        (let ((residual (funcall slice t)))
          (case last
            ((:undersized :oversized)
             (when residual (take residual))
             (values (loot)
                     (cond
                       ((zerop remainder) nil)
                       ((eq last :undersized) remainder)
                       (t (min size (+ remainder n))))))
            (:truncated (values (loot)
                                residual))))))))

Tests

Edit: I ran exhaustive tests and fixed a lot of corner cases. Also, you can see that I factorized lists and arrays in a single method. Test results have been updated.

Firt, enable tracing:

(trace split-n)

Then, we run it for some combinations of inputs:

(with-open-file (*trace-output*
                     #P"/tmp/pastebin" :direction :output :if-exists :supersede)
      (dolist (last '(:undersized :oversized :truncated))
        (dolist (shared '(nil t))
          (dolist (type '(vector list))
            (dolist (input (list #() '()
                                 #(1) '(1)
                                 '(a b c) #(a b c)
                                 '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)
                                 #(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)
                                 "something in a string"))
              (dolist (n '(1 2 3 4 5 6 7 8))
                (split-n input n :last last :sharedp shared :result-type type)
                (terpri *trace-output*)))))))

Results are available on pastebin.

(edit) Back to your code

I go back to your original question as well as your answer. Even though the code is readable and well organized, you are doing some nasty things maybe without realizing it:

  • SUBSEQ always create a copy of the input sequence. You create copies for the head and the tail in partition, for example. Imagine a sequence of thousand elements splitted by groups of 10: it might be inevitable to allocate 100 subsequences, but this is not what happens because you needlessly copy many more sequences at each step:

    1. partition into a head, a sequence of 10 elements, and a tail, a sequence of 990 elements.
    2. parition that copy into a head, and the next tail, a sequence of 980 elements.
    3. .... repeat the process: how many times are elements being copied? Half a million times? You accidentally wrote code with quadratic complexity impacting both time and memory.
  • In the :oversized case, you still partition and append lists; here, you could use nconc instead of append. Since you just created the list and nobody else has a reference to it, why not mutate it?

  • In the same place, you write:

     (apply #'(lambda (x y) (concatenate result-type x y)) oversized)
    

    IMHO the lambda is not really useful and the thing could be written:

     (concatenate result-type (first oversized) (second oversized))
    

    But still, you took a sequence, split it in parts, then extract the last two elements and join them, which is quite some work. This is not catastrophic eiter, but since truncate can give you the size in advance you can avoid doing unnecessary work.

  • By the way, you remove 2 from n in order to get the last two subsequences: did you check what happens when splitting "abcd" by 10 using the :oversized mode?

Your code is readable and the major efficiency hit comes from repeatedly calling subseq. I'd suggest trying to write the most over-engineered, gold-plated solution you can do, just as an exercise. This will force you to consider all possible corner cases and see if you can refactor things a little more. Good luck!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Great writeup! The only thing I was missing is perhaps to also add a result-type parameter like with standard map to control the type of the returned sequence. \$\endgroup\$ – ferada Aug 6 '15 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.