William James
5/1/2015 7:28:00 PM
Carl L. Gay wrote:
> 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'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))
Gauche Scheme:
(use srfi-1 :only (lset-union))
(define (combine stuff)
(define (update table k v)
(hash-table-update! table k (cut lset-union eq? v <>) '()))
(let1 ht (make-hash-table)
(dolist (kv stuff) (apply update ht kv))
(hash-table-map ht list)))
(combine
'((a (a0 a1 a2))
(b (b1 b2))
(a (a4 a1))
(c ())
(b (b4))))
===>
((a (a2 a0 a4 a1)) (b (b2 b1 b4)) (c ()))
--
Viewed at its most abstract level, a fundamental agenda is thus to influence
the European-derived peoples of the United States to view concern about their
own demographic and cultural eclipse as irrational and as an indication of
psychopathology. --- Kevin MacDonald; "The Frankfurt School of Social Research
and the Pathologization of Gentile Group Allegiances"