Hi.
I need a fast way to combine elements of a large list as follows:
Input:
((a (a0 a1 a2))
(b (b1 b2))
(a (a4 a1))
(c nil)
(b (b4))
etc)
output:
((a (a1 a1 a2 a4))
(b (b1 b2 b4))
(c nil))
any help would be appreciated. I am using a rather simple approach of
sorting the input list, and then walking through it combining elements
from the top. For a 3800 element list, it is taking around 40
seconds. I expect that there is a faster way.
Here is the code for the function I am using:
(defun combine (l)
(setq *temp* nil)
(setf l (sort l #'(lambda (x y)
(string< (first x) (first y)))))
(setq cn (first (first l)))
(setq *temp* (first l))
(mapcar #'(lambda (x)
(let ((n (first x))
(v (second x)))
(if (equal cn n)
(setf (second *temp* (union v (second *temp*))))
(progn
(setf *temp* (push (list n v) *temp*))
(setf cn n)))))
l)
*temp*)
Thanks in advance.
--
Roy Masrani Alberta Research Council
·······@skyler.arc.ab.ca Advanced Computing and Engineering Dept.
ph: (403) 297-2354 Calgary, Alberta
fax: (403) 297-2339 Canada T2E 7H7
In article <···················@janus.arc.ab.ca>, ·······@skyler.arc.ab.ca (Roy Masrani) writes:
|> Input:
|> ((a (a0 a1 a2))
|> (b (b1 b2))
|> (a (a4 a1))
|> (c nil)
|> (b (b4))
|> etc)
|>
|> output:
|> ((a (a1 a1 a2 a4))
|> (b (b1 b2 b4))
|> (c nil))
|>
|> any help would be appreciated. I am using a rather simple approach of
|> sorting the input list, and then walking through it combining elements
|> from the top. For a 3800 element list, it is taking around 40
|> seconds. I expect that there is a faster way.
Assuming that the ordering doesn't matter, and that the keys (here a,b,c) are suitable
as keys for a hashtable, then that's what I'd use:
(defun combine (l)
(flet ((add-to-hash (pair hash)
(let ((key (car pair))
(newval (cadr pair)))
(setf (gethash key hash)
(append (gethash key hash) newval)))))
(let ((hash (make-hash-table :test #'eq))
(result nil))
(mapc #'(lambda (x) (add-to-hash x hash)) l)
(maphash #'(lambda (key val)
(push (list key (delete-duplicates val :test #'eq))
result))
hash)
result)))
Maybe dolist is more efficient than mapc in your lisp. And of course, this can
probably all be written as one (if not fewer) LOOP form :-)
One tip: in the example you gave, you are using *temp* and cn as local variables.
Bind them with let to avoid interference with any special variables of the same
names.
Dan
·······@cs.uni-sb.de
Newsgroups: comp.lang.lisp
From: ·······@skyler.arc.ab.ca (Roy Masrani)
Date: 6 Apr 93 3:36pm PST
I need a fast way to combine elements of a large list as follows:
Input:
((a (a0 a1 a2))
(b (b1 b2))
(a (a4 a1))
(c nil)
(b (b4))
etc)
output:
((a (a1 a1 a2 a4))
(b (b1 b2 b4))
(c nil))
any help would be appreciated. I am using a rather simple approach of
sorting the input list, and then walking through it combining elements
from the top. For a 3800 element list, it is taking around 40
seconds. I expect that there is a faster way.
There were some bugs in your code. Here it is with a few fixes. It
takes 9 seconds to run in a 3800 element list in MCL 2.0 on a Mac IIsi.
Could you be running the code interpreted???
(defun combine (l)
(let* ((list (sort l #'string< :key #'car))
(temp (list (car list)))
(cn (caar list)))
(mapcar #'(lambda (x)
(let ((n (first x))
(v (second x)))
(if (eq cn n) ; if cn and n always interned syms, use eq
(setf (second (car temp)) (union v (second (car temp))))
(progn
(push (list n v) temp) ; could just (push x temp)
(setf cn n)))))
list)
temp))
Here's a simple hash table version. It takes 2.8 seconds on the same
list, but conses a tad more. I'm sure some of the gurus can speed it
up for you even more...
(defun combine2 (l)
(let ((ht (make-hash-table :size (length l)))
(result '()))
(dolist (elt l)
(let ((item (gethash (car elt) ht)))
(setf (gethash (car elt) ht)
(if (null item)
(cadr elt)
(union item (cadr elt))))))
(maphash #'(lambda (key val)
(push (list key val) result))
ht)
result))
Just so you know what I measured, here's what I used to create the
input:
(defun make-input (m n)
(loop repeat m
collect (list (intern (format nil "A~D" (random m)))
(delete-duplicates
(loop repeat n
collect (intern (format nil "B~D" (random n))))))))
(make-input 3800 5)
In article <···················@janus.arc.ab.ca> you write:
>I need a fast way to combine elements of a large list as follows:
>
>Input:
>((a (a0 a1 a2))
> (b (b1 b2))
> (a (a4 a1))
> (c nil)
> (b (b4))
> etc)
>
>output:
>((a (a1 a1 a2 a4))
> (b (b1 b2 b4))
> (c nil))
>
>Roy Masrani Alberta Research Council
>·······@skyler.arc.ab.ca Advanced Computing and Engineering Dept.
Here's a solution which uses a nested hash table (a hash table whose
elements are hash tables). It is trivial to sort the resulting list,
sorting the values associated with the elements and the key:
mark
(defun walk-list (list)
(loop for (key values) in list
with table = (make-hash-table :test #'equal :size (length list))
and stored-value
finally (return (hash-to-list-key table))
do (setq stored-value (gethash key table))
unless stored-value
do (setf stored-value (make-hash-table :test #'equal)
(gethash key table) stored-value)
do (walk-values stored-value values)))
(defun walk-values (stored-value values)
(loop for val in values
do (setf (gethash val stored-value) t)))
(defun hash-to-list-key (table &key sort)
(when (non-empty-hash-table table)
(loop for key being the hash-key in table using (hash-value value)
collect (list key (value-to-list value)))))
(defun value-to-list (table &key sort)
(loop for key being the hash-key in table
collect key))
? (walk-list '((a (a0 a1 a2))
(b (b1 b2))
(a (a4 a1))
(c nil)
(b (b4))))
((C NIL) (A (A0 A2 A4 A1)) (B (B1 B2 B4)))