Re: Collecting like-labelled sublists of a list

On 2008-07-29, Cortez <relativeflux@xxxxxxxxxxxxx> wrote:
I need to traverse a list of lists, where each sublist is labelled by
a number, and collect together the contents of all sublists sharing
the same label. So if I have the list -

((0 a b) (1 c d) (2 e f) (3 g h) (1 i j) (2 k l) (4 m n) (2 o p) (4 q
r) (5 s t))

Note that this is basically like join of a database onto itself,
where the number is the join key.

where the first element of each sublist is the label, I need to
produce -

((a b) (c d i j) (e f k l o p) (g h) (m n q r) (s t))

I do this with the following -

(defun test (list)
(loop for j in list
for index = (first j)
for k = (rest j)
with indices = nil
if (not (member index indices))
do (pushnew index indices)
and collect k into res
else
do (nconc (nth index res) k)
finally (return res)))

I suspect that there is a more efficient and elegant way of doing
this, however. Any suggestions welcome.

If you want efficiency for situations when such lists are large,
you probably want to use hashing to implement the join.

If the labels are within a small numeric range, like 0 to 99, you could use an
array instead of hashing:

(defun join (list)
(let ((array (make-array '(100))))
(dolist (sublist list (coerce (remove nil array) 'list))
(destructuring-bind (numeric-label &rest items) sublist
(setf (aref array numeric-label)
(append (aref array numeric-label) items))))))

Change APPEND to NCONC for the destructive version.

Brief background: this is part of a program I've written for reading
data from SDIF files, a binary format which stores sound description
data. The labelled lists represent partials in spectral analysis data
(partial-index, time, frequency).

So the labels are bounded, since they represent partials, and there are only so
many partials in the spectral analysis.
.

Relevant Pages

  • Re: Ordered lists, and how to break one up while still validating.
    ... an ordered list are not *mere labels* by the following consideration: ... I looked at the HTML spec and they do say UL is for data where the order ... It then goes on to say that ordered lists are rendered with numbers, ...
    (alt.html)
  • Re: This Crashes RosAsm
    ... They have posted Lists of Labels. ... I perfectely know how RosAsm works. ... I can't fix a bug that does not exist. ...
    (alt.lang.asm)
  • Re: Collecting like-labelled sublists of a list
    ... The labelled lists represent partials in spectral analysis data ... Of course you get the sublists in random order, ... Sorry, do you mean the order of the labels, or the order of the elements inside each sublist? ...
    (comp.lang.lisp)
  • Re: Another Mailing Label Question!
    ... Although you could convert such a list directly to labels, ... you're much better off having it as a data source. ... > I am still trying to get a real handle on mailing lists - this time I ...
    (microsoft.public.word.newusers)
  • Re: newbie wants help: Splitting delimited lines
    ... (defun split-line (split-char line count) ... > "split a line into an alist of length count with labels" ... small lists are quite efficient. ...
    (comp.lang.lisp)