I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
Lisp". I'm determined to master each chapter before progressing to the
next. Having said that, on page 56 there is the following problem:
3. Define a function that takes a list and returns a list indicating
the number of times each (eql) element appears, sorted from the most
common element to the least common.
> (occurences '(a b a d a c d c a)
((A . 4) (C. 2) (D. 2) (B. 1))
Well, this "simple" task has been driving me crazy! I must have spent
at least 10 hours working on it. Having said that, I SOLVED IT!!! :)
Here's my solution:
(setq input '(a b a d a c d c a))
(defun occurences (input-list)
(let ((sorted-list (sort (copy-sequence input-list) 'string<))
(a-list nil))
(setq a-list (occurences-make-alist () sorted-list))
(occurences-sort-alist a-list)))
(defun occurences-sort-alist (a-list)
(sort a-list 'occurences-greater))
(defun occurences-greater (node-1 node-2)
(> (cdr node-1) (cdr node-2)))
(defun occurences-make-alist (a-list sorted-list)
(let ((node nil)
(remainder nil))
(if (not (null sorted-list))
(progn
(setq node (occurences-get-token-cons sorted-list))
(setq remainder (occurences-remainder node sorted-list))
(setq a-list (append a-list node (occurences-make-alist a-list
remainder)))))
a-list))
(defun occurences-remainder (node sorted-list)
(if (null node)
sorted-list
(subseq sorted-list (cdr (car node)))))
(defun occurences-get-token-cons (sorted-list)
(if (null sorted-list)
nil
(progn
(let ((tok (car sorted-list)) (count 1))
(setq count (occurences-get-token-count tok count (cdr sorted-list)))
(list (cons tok count))))))
(defun occurences-get-token-count (token count input-list)
(if (eql token (car input-list))
(setq count (+ count (occurences-get-token-count token count (cdr
input-list)))))
count)
(occurences input)
;;; END
And, it works! :)
-Jason
I'm also learning Lisp, and I tried the same exercise about a month
ago. I came up with:
(defun occurences (list)
(let ((alist '()) (a-element '()))
(dolist (element list)
(setf a-element (assoc element alist))
(if a-element
(setf (cdr a-element) (+ (cdr a-element) 1))
(setf alist (cons (cons element 1) alist))))
(sort alist #'> :key #'cdr)))
Nice go at it. You aren't the only one puzzling over those exercises.
:)
From: Bill Atkins
Subject: Re: ANSI Common Lisp, Ch 3, Ex 3
Date:
Message-ID: <873bi1fm9n.fsf@rpi.edu>
"Jason" <·······@gmail.com> writes:
> I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
> Lisp". I'm determined to master each chapter before progressing to the
> next. Having said that, on page 56 there is the following problem:
>
> 3. Define a function that takes a list and returns a list indicating
> the number of times each (eql) element appears, sorted from the most
> common element to the least common.
>
>> (occurences '(a b a d a c d c a)
> ((A . 4) (C. 2) (D. 2) (B. 1))
>
> Well, this "simple" task has been driving me crazy! I must have spent
> at least 10 hours working on it. Having said that, I SOLVED IT!!! :)
>
> Here's my solution:
>
> (setq input '(a b a d a c d c a))
>
> (defun occurences (input-list)
> (let ((sorted-list (sort (copy-sequence input-list) 'string<))
> (a-list nil))
> (setq a-list (occurences-make-alist () sorted-list))
> (occurences-sort-alist a-list)))
>
> (defun occurences-sort-alist (a-list)
> (sort a-list 'occurences-greater))
>
> (defun occurences-greater (node-1 node-2)
> (> (cdr node-1) (cdr node-2)))
>
> (defun occurences-make-alist (a-list sorted-list)
> (let ((node nil)
> (remainder nil))
> (if (not (null sorted-list))
> (progn
> (setq node (occurences-get-token-cons sorted-list))
> (setq remainder (occurences-remainder node sorted-list))
> (setq a-list (append a-list node (occurences-make-alist a-list
> remainder)))))
> a-list))
>
> (defun occurences-remainder (node sorted-list)
> (if (null node)
> sorted-list
> (subseq sorted-list (cdr (car node)))))
>
> (defun occurences-get-token-cons (sorted-list)
> (if (null sorted-list)
> nil
> (progn
> (let ((tok (car sorted-list)) (count 1))
> (setq count (occurences-get-token-count tok count (cdr sorted-list)))
> (list (cons tok count))))))
>
> (defun occurences-get-token-count (token count input-list)
> (if (eql token (car input-list))
> (setq count (+ count (occurences-get-token-count token count (cdr
> input-list)))))
> count)
>
> (occurences input)
>
> ;;; END
>
> And, it works! :)
>
> -Jason
Congrats!
Here's an alternative way to do it:
(defun occurrences (list)
(let ((counts '()))
(dolist (item list)
(if (assoc item counts :test #'eql)
(incf (cdr (assoc item counts :test #'eql)))
(setf counts (acons item 1 counts))))
(sort counts #'> :key #'cdr)))
It iterates through its argument and builds an alist out of it,
leaving you with something like: '((A . 3) (B . 7) (C . 4))
The :key argument to sort can simplify your code - a custom function
to compare cdr's is no longer necessary.
Happy lisping,
Bill
Bill Atkins wrote:
> "Jason" <·······@gmail.com> writes:
>
> > I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
> > Lisp". I'm determined to master each chapter before progressing to the
> > next. Having said that, on page 56 there is the following problem:
> >
> > 3. Define a function that takes a list and returns a list indicating
> > the number of times each (eql) element appears, sorted from the most
> > common element to the least common.
> >
> >> (occurences '(a b a d a c d c a)
> > ((A . 4) (C. 2) (D. 2) (B. 1))
> >
> > Well, this "simple" task has been driving me crazy! I must have spent
> > at least 10 hours working on it. Having said that, I SOLVED IT!!! :)
> >
> > Here's my solution:
> >
> > (setq input '(a b a d a c d c a))
> >
> > (defun occurences (input-list)
> > (let ((sorted-list (sort (copy-sequence input-list) 'string<))
> > (a-list nil))
> > (setq a-list (occurences-make-alist () sorted-list))
> > (occurences-sort-alist a-list)))
> >
> > (defun occurences-sort-alist (a-list)
> > (sort a-list 'occurences-greater))
> >
> > (defun occurences-greater (node-1 node-2)
> > (> (cdr node-1) (cdr node-2)))
> >
> > (defun occurences-make-alist (a-list sorted-list)
> > (let ((node nil)
> > (remainder nil))
> > (if (not (null sorted-list))
> > (progn
> > (setq node (occurences-get-token-cons sorted-list))
> > (setq remainder (occurences-remainder node sorted-list))
> > (setq a-list (append a-list node (occurences-make-alist a-list
> > remainder)))))
> > a-list))
> >
> > (defun occurences-remainder (node sorted-list)
> > (if (null node)
> > sorted-list
> > (subseq sorted-list (cdr (car node)))))
> >
> > (defun occurences-get-token-cons (sorted-list)
> > (if (null sorted-list)
> > nil
> > (progn
> > (let ((tok (car sorted-list)) (count 1))
> > (setq count (occurences-get-token-count tok count (cdr sorted-list)))
> > (list (cons tok count))))))
> >
> > (defun occurences-get-token-count (token count input-list)
> > (if (eql token (car input-list))
> > (setq count (+ count (occurences-get-token-count token count (cdr
> > input-list)))))
> > count)
> >
> > (occurences input)
> >
> > ;;; END
> >
> > And, it works! :)
> >
> > -Jason
>
> Congrats!
>
> Here's an alternative way to do it:
>
> (defun occurrences (list)
> (let ((counts '()))
> (dolist (item list)
> (if (assoc item counts :test #'eql)
> (incf (cdr (assoc item counts :test #'eql)))
> (setf counts (acons item 1 counts))))
> (sort counts #'> :key #'cdr)))
>
I knew there was a better way to do this! :( I've only been exposed to
the most basic lisp constructs, and I'm still tending to approach
problems with a procedural mindset instead of a recursive 'data is
code' mindset. I'll learn though, I'll learn...
Thanks!
-Jason
"Jason" <·······@gmail.com> wrote in message ·····························@z34g2000cwc.googlegroups.com...
> I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
> Lisp". I'm determined to master each chapter before progressing to the
> next. Having said that, on page 56 there is the following problem:
>
> 3. Define a function that takes a list and returns a list indicating
> the number of times each (eql) element appears, sorted from the most
> common element to the least common.
>
>> (occurences '(a b a d a c d c a)
> ((A . 4) (C. 2) (D. 2) (B. 1))
>
> Well, this "simple" task has been driving me crazy! I must have spent
> at least 10 hours working on it. Having said that, I SOLVED IT!!! :)
Great!
> Here's my solution:
>
> (setq input '(a b a d a c d c a))
Ok, general consensus is to use the macro SETF over
the special form SETQ, since SETF is more general.
Also, using SET[*] at top level requires undefined
behaviour (although in every implementation I've seen
it works) so it's better to use DEFVAR or DEFPARAMETER
instead.
Lastly, top-level variables are special, they behave
differently than variables declared in a LET, so
it's good practice to give them special names the
standard being to surround them with asterisks.
(DEFVAR *INPUT* '(a b a d a c d c a))
> (defun occurences (input-list)
> (let ((sorted-list (sort (copy-sequence input-list) 'string<))
> (a-list nil))
> (setq a-list (occurences-make-alist () sorted-list))
> (occurences-sort-alist a-list)))
STRING< is a bad idea, it's defined to work on strings.
Try (OCCURENCES '(1 2 3 1 2 3 1 2 3 4)). Well done on
the COPY-SEQUENCE, you've been paying attention.
> (defun occurences-sort-alist (a-list)
> (sort a-list 'occurences-greater))
As another practice note: I prefer #' to '.
Makes it easier to spot the reference to
a function rather than just a quoted symbol.
OTOH, I no longer use #'(LAMBDA ...) just (LAMBDA ...)
> (defun occurences-greater (node-1 node-2)
> (> (cdr node-1) (cdr node-2)))
Others have pointed out that SORT takes an optional
key argument.
(SORT A-LIST #'> :KEY #'CDR)
> (defun occurences-make-alist (a-list sorted-list)
> (let ((node nil)
> (remainder nil))
> (if (not (null sorted-list))
> (progn
> (setq node (occurences-get-token-cons sorted-list))
> (setq remainder (occurences-remainder node sorted-list))
> (setq a-list (append a-list node (occurences-make-alist a-list
> remainder)))))
> a-list))
Just a performance note, if you are faced with a choice
of making a list bigger by using APPEND to add an element
to the end of the list or using CONS on the front, CONS
is almost always the winner because APPEND has to go all
the way through the list to find the end. If order is
important you can always REVERSE or NREVERSE the list
when you're done.
> (defun occurences-remainder (node sorted-list)
> (if (null node)
> sorted-list
> (subseq sorted-list (cdr (car node)))))
>
> (defun occurences-get-token-cons (sorted-list)
> (if (null sorted-list)
> nil
> (progn
> (let ((tok (car sorted-list)) (count 1))
> (setq count (occurences-get-token-count tok count (cdr sorted-list)))
> (list (cons tok count))))))
>
> (defun occurences-get-token-count (token count input-list)
> (if (eql token (car input-list))
> (setq count (+ count (occurences-get-token-count token count (cdr
> input-list)))))
> count)
>
> (occurences input)
>
> ;;; END
>
> And, it works! :)
Ok, my version :)
(defun occurences(list)
(let ((counts (make-hash-table :test #'eql)))
(dolist (item list) (incf (gethash item counts 0)))
(sort (loop for key being the hash-keys
in counts using (hash-value count)
collect (cons key count))
#'> :key #'cdr)))
If you haven't yet, download a copy of the hyperspec, you
can find one at www.lispworks.com , it's a wonderful resource.
--
Geoff
Geoffrey Summerhayes wrote:
>
> Ok, general consensus is to use the macro SETF over
> the special form SETQ, since SETF is more general.
>
I actually wrote this in ELisp. SETF seems to not be available in my
particular brand of Emacs. I can convert this to CLisp and run it on my
BSD box at home when I get the chance...
> Also, using SET[*] at top level requires undefined
> behaviour (although in every implementation I've seen
> it works) so it's better to use DEFVAR or DEFPARAMETER
> instead.
>
> Lastly, top-level variables are special, they behave
> differently than variables declared in a LET, so
> it's good practice to give them special names the
> standard being to surround them with asterisks.
>
> (DEFVAR *INPUT* '(a b a d a c d c a))
>
Thanks. I saw that mentioned in my book. I was not sure how strong a
convention that was. I'll keep this in mind. For now I'm just writing
toys, but when I build a real world program in Lisp I'll remember to be
kind to my fellow hackers.
> > (defun occurences (input-list)
> > (let ((sorted-list (sort (copy-sequence input-list) 'string<))
> > (a-list nil))
> > (setq a-list (occurences-make-alist () sorted-list))
> > (occurences-sort-alist a-list)))
>
> STRING< is a bad idea, it's defined to work on strings.
> Try (OCCURENCES '(1 2 3 1 2 3 1 2 3 4)). Well done on
> the COPY-SEQUENCE, you've been paying attention.
>
Again, this is an emacs elist issue. copy-list is not defined for me.
As for the strings, that was the first solution that worked. I'm still
learning what I have available.
Thanks for the helpful feedback!
-Jason
On 2006-03-02, Jason <·······@gmail.com> wrote:
> Geoffrey Summerhayes wrote:
>> Lastly, top-level variables are special, they behave differently
>> than variables declared in a LET, so it's good practice to give
>> them special names the standard being to surround them with
>> asterisks.
>>
>> (DEFVAR *INPUT* '(a b a d a c d c a))
>
> Thanks. I saw that mentioned in my book. I was not sure how strong a
> convention that was. I'll keep this in mind. For now I'm just
> writing toys, but when I build a real world program in Lisp I'll
> remember to be kind to my fellow hackers.
Remember also that one of your fellow hackers may be *you*, six months
(or years) from now. :)
-- L
in message <·····················@news20.bellglobal.com>, Geoffrey
Summerhayes (········@NhOoStPmAaMil.com') wrote:
> Ok, general consensus is to use the macro SETF over
> the special form SETQ, since SETF is more general.
SETF has the advantage that you can trample on memory without having any
clue as to who else is hanging on to a pointer to it; it's the LISP
equivalent of the old Basic POKE. Unless you only build little toy
systems it should be used with caution and discretion. Yes, copying a
huge lump of structure to change one pointer is inefficient, but it's
safe. Having different (i.e. 'not general') functions/macros to change
different sorts of pointers in different sorts of circumstances is a
good mental tool to help you think about whether you should be doing
what you're doing.
Of course there are times when RPLAC[A|D] is the right thing to do for
efficiency reasons; but explicitly having to call a known-to-be-
dangerous function is an effective guard against carelessness. SETF
happily translates to RPLAC[A|D] in places where that may not be in the
least safe, and because it's 'preferred' and 'more general' people tend
to use it carelessly.
--
·····@jasmine.org.uk (Simon Brooke) http://www.jasmine.org.uk/~simon/
;; Sending your money to someone just because they've erected
;; a barrier of obscurity and secrets around the tools you
;; need to use your data does not help the economy or spur
;; innovation. - Waffle Iron Slashdot, June 16th, 2002
Simon Brooke <·····@jasmine.org.uk> writes:
> in message <·····················@news20.bellglobal.com>, Geoffrey
> Summerhayes (········@NhOoStPmAaMil.com') wrote:
>
> > Ok, general consensus is to use the macro SETF over
> > the special form SETQ, since SETF is more general.
>
> SETF has the advantage that you can trample on memory without having any
> clue as to who else is hanging on to a pointer to it; it's the LISP
> equivalent of the old Basic POKE. Unless you only build little toy
> systems it should be used with caution and discretion.
If you are in the habit of using functions cluelessly, your choice of
which particular function you use to do it won't make much of a
difference. You must always write programs while being aware of the
implications of your actions. Avoiding SETF has very little didactic
value in Common Lisp.
Zach
"Simon Brooke" <·····@jasmine.org.uk> wrote in message
···················@gododdin.internal.jasmine.org.uk...
> in message <·····················@news20.bellglobal.com>, Geoffrey
> Summerhayes (········@NhOoStPmAaMil.com') wrote:
>
>> Ok, general consensus is to use the macro SETF over
>> the special form SETQ, since SETF is more general.
>
> SETF has the advantage that you can trample on memory without having any
> clue as to who else is hanging on to a pointer to it; it's the LISP
> equivalent of the old Basic POKE. Unless you only build little toy
> systems it should be used with caution and discretion. Yes, copying a
> huge lump of structure to change one pointer is inefficient, but it's
> safe. Having different (i.e. 'not general') functions/macros to change
> different sorts of pointers in different sorts of circumstances is a
> good mental tool to help you think about whether you should be doing
> what you're doing.
>
Whatever floats your boat, but IMO, it's more aimed at
treating the symptom than the disease.
I work in a multi-lingual shop so our rule is general,
"Thou shalt not f*ck with data thou dost not own, on pain
of being shunned, stoned, ridiculed and/or buying coffee
and donuts for everyone until told otherwise."
--
Geoff
"Jason" <·······@gmail.com> wrote in message
·····························@z34g2000cwc.googlegroups.com...
> I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
> Lisp". I'm determined to master each chapter before progressing to the
> next. Having said that, on page 56 there is the following problem:
>
> 3. Define a function that takes a list and returns a list indicating
> the number of times each (eql) element appears, sorted from the most
> common element to the least common.
>
>> (occurences '(a b a d a c d c a)
> ((A . 4) (C. 2) (D. 2) (B. 1))
>
Hey there i'm a newbie as well and here is my shot at it !
(defun occurences (input-list)
(labels ((occurences-helper (input-list result)
(if (null input-list) result
(let* ((current-item (car input-list))
(my-cons (assoc current-item result)))
(if (null my-cons)
(occurences-helper (cdr input-list) (acons
considered-item 1 result))
(rplacd my-cons (1+ (cdr my-cons)))
(occurences-helper (cdr input-list) result))))))
(sort (occurences-helper input-list nil)
#'(lambda (cons1 cons2) (> (cdr cons1) (cdr cons2))))))
Though i tried to make it tail-recursive, I'm pretty sure there must be some
smart way to do this avoiding recursion.
Sacha
"Sacha" <··@address.spam> writes:
> First post in this group and already messing up.
> here is what i intended to send
>
> (defun occurences (input-list)
> (labels ((occurences-helper (input-list result)
> (if (null input-list) result
> (let* ((current-item (car input-list))
> (my-cons (assoc current-item result)))
> (cond ((null my-cons) (occurences-helper (cdr input-list)
> (acons current-item 1 result)))
> (t
> (rplacd my-cons (1+ (cdr my-cons)))
I would use either
(setf (cdr my-cons) (1+ (cdr my-cons)))
or
(incf (cdr my-cons))
instead of the older RPLACD
> (occurences-helper (cdr input-list) result)))))))
> (sort (occurences-helper input-list nil)
> #'(lambda (cons1 cons2) (> (cdr cons1) (cdr cons2))))))
A simpler formulation of this takes advantage of somof the optional
arguments to sort:
(sort (occurences-helper input-list nil) #'> :key #'cdr)
SORT has direct support for this common idiom. (Or would that be called
a "pattern" nowadays?)
--
Thomas A. Russ, USC/Information Sciences Institute
>> (rplacd my-cons (1+ (cdr my-cons)))
> I would use either
>
> (setf (cdr my-cons) (1+ (cdr my-cons)))
> or
> (incf (cdr my-cons))
>
> instead of the older RPLACD
Thanks for your advice.
It certainly looks better using incf.
>> (occurences-helper (cdr input-list) result)))))))
>> (sort (occurences-helper input-list nil)
>> #'(lambda (cons1 cons2) (> (cdr cons1) (cdr cons2))))))
>
> A simpler formulation of this takes advantage of somof the optional
> arguments to sort:
> (sort (occurences-helper input-list nil) #'> :key #'cdr)
hehe i noticed that :key parameter in the hyperspec, and was too lazy to
really dive into it. Now look what i missed. This was pretty stupid of me.
Thanks again !
Sacha
Sacha wrote:
> "Jason" <·······@gmail.com> wrote in message
> ·····························@z34g2000cwc.googlegroups.com...
> > I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
> > Lisp". I'm determined to master each chapter before progressing to the
> > next. Having said that, on page 56 there is the following problem:
> >
> > 3. Define a function that takes a list and returns a list indicating
> > the number of times each (eql) element appears, sorted from the most
> > common element to the least common.
> >
> >> (occurences '(a b a d a c d c a)
> > ((A . 4) (C. 2) (D. 2) (B. 1))
> >
>
> Hey there i'm a newbie as well and here is my shot at it !
>
> (defun occurences (input-list)
> (labels ((occurences-helper (input-list result)
> (if (null input-list) result
> (let* ((current-item (car input-list))
> (my-cons (assoc current-item result)))
> (if (null my-cons)
> (occurences-helper (cdr input-list) (acons
> considered-item 1 result))
> (rplacd my-cons (1+ (cdr my-cons)))
> (occurences-helper (cdr input-list) result))))))
> (sort (occurences-helper input-list nil)
> #'(lambda (cons1 cons2) (> (cdr cons1) (cdr cons2))))))
>
> Though i tried to make it tail-recursive, I'm pretty sure there must be some
> smart way to do this avoiding recursion.
>
> Sacha
I'm newbie too, and here is my contribution in Scheme:
(define (occurence l0)
(let inner_occurence ((l1 l0) (res '()))
(cond ((null? l1) res)
(else (let* ((x (car l1))
(nb 1)
(y (let temp_occurence ((l2
(cdr l1)))
(cond ((null? l2) l2)
((eq? (car l2) x)
(set! nb (+ nb 1))
(temp_occurence
(cdr l2)))
(else (append (list
(car l2)) (temp_occurence (cdr l2))))))))
(inner_occurence y (let ((x (let
insert_occurence ((occ (cons x nb)) (r res))
(cond
((null? r) (list occ))
((< (cdr occ) (cdar r)) (cons (car r) (insert_occurence occ (cdr r))))
(else (append (list occ) r))))))
x)))))))
Jason wrote:
> > (occurences '(a b a d a c d c a)
> ((A . 4) (C. 2) (D. 2) (B. 1))
Another concise, but slow (~O(n^2)) approach would be:
(defun occurences (list)
(sort (mapcar (lambda (e)
(cons e (count e list)))
(remove-duplicates list))
#'>
:key #'cdr))
Jason wrote:
> I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
> Lisp". I'm determined to master each chapter before progressing to the
> next. Having said that, on page 56 there is the following problem:
>
> 3. Define a function that takes a list and returns a list indicating
> the number of times each (eql) element appears, sorted from the most
> common element to the least common.
>
>> (occurences '(a b a d a c d c a)
> ((A . 4) (C. 2) (D. 2) (B. 1))
nice task. A loop solution could look like this (but it is not very fast):
(defun occurences (list)
(loop for i in (remove-duplicates list)
collect (cons i (count i list)) into result
finally (return (sort result #'> :key #'cdr))))
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss wrote:
> Jason wrote:
>
> > I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
> > Lisp". I'm determined to master each chapter before progressing to the
> > next. Having said that, on page 56 there is the following problem:
> >
> > 3. Define a function that takes a list and returns a list indicating
> > the number of times each (eql) element appears, sorted from the most
> > common element to the least common.
> >
> >> (occurences '(a b a d a c d c a)
> > ((A . 4) (C. 2) (D. 2) (B. 1))
>
> nice task. A loop solution could look like this (but it is not very fast):
>
> (defun occurences (list)
> (loop for i in (remove-duplicates list)
> collect (cons i (count i list)) into result
> finally (return (sort result #'> :key #'cdr))))
>
This is so very terse! I'm amazed. I want to see this in action, but I
can't get line three to parse (clisp). It's telling me "*** - POSITION:
:START = 1 should not be greater than :END = 0".
-Jason
-Jason
"Jason" <·······@gmail.com> writes:
>> (defun occurences (list)
>> (loop for i in (remove-duplicates list)
>> collect (cons i (count i list)) into result
>> finally (return (sort result #'> :key #'cdr))))
>>
>
> This is so very terse! I'm amazed. I want to see this in action, but I
> can't get line three to parse (clisp). It's telling me "*** - POSITION:
> :START = 1 should not be greater than :END = 0".
Perhaps you have redefined COUNT ?
Try:
(defpackage :clean (:use :cl))
(in-package :clean)
(defun occurences (list)
(loop for i in (remove-duplicates list)
collect (cons i (count i list)) into result
finally (return (sort result #'> :key #'cdr))))
(occurences '(a b a d a c d c a))
--
__Pascal Bourguignon__ http://www.informatimago.com/
In a World without Walls and Fences,
who needs Windows and Gates?
Pascal Bourguignon wrote:
> "Jason" <·······@gmail.com> writes:
> >> (defun occurences (list)
> >> (loop for i in (remove-duplicates list)
> >> collect (cons i (count i list)) into result
> >> finally (return (sort result #'> :key #'cdr))))
> >>
> >
> > This is so very terse! I'm amazed. I want to see this in action, but I
> > can't get line three to parse (clisp). It's telling me "*** - POSITION:
> > :START = 1 should not be greater than :END = 0".
>
> Perhaps you have redefined COUNT ?
> Try:
I don't know what I did, but I opened a new clisp terminal, carefully
copied/pasted and now it works. Wow, /four/ lines of code just
accomplished what took me 41 lines of code!
I'm starting to really like this interesting parenthetically exuberant
language!
From: Bill Atkins
Subject: Re: ANSI Common Lisp, Ch 3, Ex 3
Date:
Message-ID: <87mzg91cuh.fsf@rpi.edu>
"Jason" <·······@gmail.com> writes:
> Pascal Bourguignon wrote:
>> "Jason" <·······@gmail.com> writes:
>> >> (defun occurences (list)
>> >> (loop for i in (remove-duplicates list)
>> >> collect (cons i (count i list)) into result
>> >> finally (return (sort result #'> :key #'cdr))))
>> >>
>> >
>> > This is so very terse! I'm amazed. I want to see this in action, but I
>> > can't get line three to parse (clisp). It's telling me "*** - POSITION:
>> > :START = 1 should not be greater than :END = 0".
>>
>> Perhaps you have redefined COUNT ?
>> Try:
>
> I don't know what I did, but I opened a new clisp terminal, carefully
> copied/pasted and now it works. Wow, /four/ lines of code just
> accomplished what took me 41 lines of code!
>
> I'm starting to really like this interesting parenthetically exuberant
> language!
It sounds like you're typing your Lisp code directly into CLISP (and
the code you submitted before looked like it had been written all at
once, rather than incrementally). Look into the SLIME environment
from Emacs and try writing your programs with that. Then you'll
_really_ like this language. When you start writing code
incrementally, you'll never want to leave Lisp.
Bill
Jason wrote:
> Pascal Bourguignon wrote:
>
>>"Jason" <·······@gmail.com> writes:
>>
>>>>(defun occurences (list)
>>>> (loop for i in (remove-duplicates list)
>>>> collect (cons i (count i list)) into result
>>>> finally (return (sort result #'> :key #'cdr))))
>>>>
>>>
>>>This is so very terse! I'm amazed. I want to see this in action, but I
>>>can't get line three to parse (clisp). It's telling me "*** - POSITION:
>>>:START = 1 should not be greater than :END = 0".
>>
>>Perhaps you have redefined COUNT ?
>>Try:
>
>
> I don't know what I did, but I opened a new clisp terminal, carefully
> copied/pasted and now it works. Wow, /four/ lines of code just
> accomplished what took me 41 lines of code!
Macroexpand the four lines and you will not feel so bad.
>
> I'm starting to really like this interesting parenthetically exuberant
> language!
>
You are new, you still see the parentheses. And you do not see the
punctuation in your current strongest language. After the parens
disappear go back and look at C or Java. A whole lot of bizarro
punctuation will have suddenly appeared in that "cleaner syntax".
I know, I spent some time lately translating C into Lisp. ewwwww.
kenny
ps. old-timers may want to note my new email address.
"Jason" <·······@gmail.com> writes:
> > >> (defun occurences (list)
> > >> (loop for i in (remove-duplicates list)
> > >> collect (cons i (count i list)) into result
> > >> finally (return (sort result #'> :key #'cdr))))
> I don't know what I did, but I opened a new clisp terminal, carefully
> copied/pasted and now it works. Wow, /four/ lines of code just
> accomplished what took me 41 lines of code!
>
> I'm starting to really like this interesting parenthetically exuberant
> language!
Yes, but as the original poster noted, this is a very slow solution.
Instead of a O(n log n) algorithm, this one is O(n^2), since the count
function traverses the list once for each unique element.
Lisp can be very powerful, with lots of nice built-in functions to do
neat things, but sometimes that power makes it simple to write
algorithms that are not efficient, mainly because the sources of
inefficiency are hidden from immediate view. That's the dark side.
--
Thomas A. Russ, USC/Information Sciences Institute
Beware the dark side, young Codewalker.
Jason <·······@gmail.com> wrote:
+---------------
| Frank Buss wrote:
| > loop solution could look like this (but it is not very fast):
| > (defun occurences (list)
| > (loop for i in (remove-duplicates list)
| > collect (cons i (count i list)) into result
| > finally (return (sort result #'> :key #'cdr))))
| >
|
| This is so very terse! I'm amazed.
+---------------
Well, it may be terse, but Frank was being kind when he said
"not very fast". In fact, for large input lists (of length N,
say) with many kinds of items (M, say), it can be dog slow!!
It's at *least* as bad as N * M, since it scans the *entire*
input list once for each kind of element. And it might be worse
than that, depending on the characteristics of your implementation's
REMOVE-DUPLICATES [but that's probably hash-based, and thus fast,
see below].
Note that the hash-table solutions you were given [such as Geoff's]
will take time closer to N + M, that is, N for populating the
hash table and M for dumping it.
For N small enough to fit on a screen, both will run blazingly
fast -- you'd never be able to tell the difference -- but for
N = 10000 and M = 1000, the former is ~900 *times* slower.
Of course, the SORT occurs in both, and probably adds an amount
of around M * (log M). If you *really* wanted to speed this up for
large inputs, you'd figure out how to count and sort simultaneously,
e.g., maybe use some kind of clever balanced tree to insert into,
or a pair of them, one indexed on the keys and one on the counts,
and rebalance both as needed.
Or something... ;-} ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Bill Atkins
Subject: Re: ANSI Common Lisp, Ch 3, Ex 3
Date:
Message-ID: <87zmk8b0pr.fsf@rpi.edu>
····@rpw3.org (Rob Warnock) writes:
> Jason <·······@gmail.com> wrote:
> +---------------
> | Frank Buss wrote:
> | > loop solution could look like this (but it is not very fast):
> | > (defun occurences (list)
> | > (loop for i in (remove-duplicates list)
> | > collect (cons i (count i list)) into result
> | > finally (return (sort result #'> :key #'cdr))))
> | >
> |
> | This is so very terse! I'm amazed.
> +---------------
>
> Well, it may be terse, but Frank was being kind when he said
> "not very fast". In fact, for large input lists (of length N,
> say) with many kinds of items (M, say), it can be dog slow!!
> It's at *least* as bad as N * M, since it scans the *entire*
> input list once for each kind of element. And it might be worse
> than that, depending on the characteristics of your implementation's
> REMOVE-DUPLICATES [but that's probably hash-based, and thus fast,
> see below].
>
> Note that the hash-table solutions you were given [such as Geoff's]
> will take time closer to N + M, that is, N for populating the
> hash table and M for dumping it.
>
> For N small enough to fit on a screen, both will run blazingly
> fast -- you'd never be able to tell the difference -- but for
> N = 10000 and M = 1000, the former is ~900 *times* slower.
>
> Of course, the SORT occurs in both, and probably adds an amount
> of around M * (log M). If you *really* wanted to speed this up for
> large inputs, you'd figure out how to count and sort simultaneously,
> e.g., maybe use some kind of clever balanced tree to insert into,
> or a pair of them, one indexed on the keys and one on the counts,
> and rebalance both as needed.
>
> Or something... ;-} ;-}
>
>
> -Rob
>
> -----
> Rob Warnock <····@rpw3.org>
> 627 26th Avenue <URL:http://rpw3.org/>
> San Mateo, CA 94403 (650)572-2607
I'm not sure you can beat O( M * log M ) for this - the sort operation
puts a definite limit on the improvements you can make. It's provable
that you can't do better than N * log N for a general-purpose sort of
of N elements. Even if you insert each element into a tree, each
insert would be O( log(M) ), repeated M times = O( M * log(M) ).
But I agree that hash tables are definitely the way to go.
- Bill
Bill Atkins wrote:
> ····@rpw3.org (Rob Warnock) writes:
>
> > Jason <·······@gmail.com> wrote:
> > +---------------
> > | Frank Buss wrote:
> > | > loop solution could look like this (but it is not very fast):
> > | > (defun occurences (list)
> > | > (loop for i in (remove-duplicates list)
> > | > collect (cons i (count i list)) into result
> > | > finally (return (sort result #'> :key #'cdr))))
> > | >
> > |
> > | This is so very terse! I'm amazed.
> > +---------------
> >
> > Well, it may be terse, but Frank was being kind when he said
> > "not very fast". In fact, for large input lists (of length N,
> > say) with many kinds of items (M, say), it can be dog slow!!
> > It's at *least* as bad as N * M, since it scans the *entire*
> > input list once for each kind of element. And it might be worse
> > than that, depending on the characteristics of your implementation's
> > REMOVE-DUPLICATES [but that's probably hash-based, and thus fast,
> > see below].
> >
> > Note that the hash-table solutions you were given [such as Geoff's]
> > will take time closer to N + M, that is, N for populating the
> > hash table and M for dumping it.
> >
> > For N small enough to fit on a screen, both will run blazingly
> > fast -- you'd never be able to tell the difference -- but for
> > N = 10000 and M = 1000, the former is ~900 *times* slower.
> >
> > Of course, the SORT occurs in both, and probably adds an amount
> > of around M * (log M). If you *really* wanted to speed this up for
> > large inputs, you'd figure out how to count and sort simultaneously,
> > e.g., maybe use some kind of clever balanced tree to insert into,
> > or a pair of them, one indexed on the keys and one on the counts,
> > and rebalance both as needed.
> >
> > Or something... ;-} ;-}
> >
> >
> > -Rob
> >
> > -----
> > Rob Warnock <····@rpw3.org>
> > 627 26th Avenue <URL:http://rpw3.org/>
> > San Mateo, CA 94403 (650)572-2607
>
> I'm not sure you can beat O( M * log M ) for this - the sort operation
> puts a definite limit on the improvements you can make. It's provable
> that you can't do better than N * log N for a general-purpose sort of
> of N elements. Even if you insert each element into a tree, each
> insert would be O( log(M) ), repeated M times = O( M * log(M) ).
>
> But I agree that hash tables are definitely the way to go.
>
> - Bill
Oh, hashtables... :) My book introduces them in chapter 4, right
*after* this task was presented. I think I shall return to this
question once I have finished my book, just to see how much of an
improvement I can make! It's nice to be able to occasionally benchmark
the learning process.
-Jason
From: Bill Atkins
Subject: Re: ANSI Common Lisp, Ch 3, Ex 3
Date:
Message-ID: <877j7c9jjb.fsf@rpi.edu>
"Jason" <·······@gmail.com> writes:
> Bill Atkins wrote:
>> ····@rpw3.org (Rob Warnock) writes:
>>
>> > Jason <·······@gmail.com> wrote:
>> > +---------------
>> > | Frank Buss wrote:
>> > | > loop solution could look like this (but it is not very fast):
>> > | > (defun occurences (list)
>> > | > (loop for i in (remove-duplicates list)
>> > | > collect (cons i (count i list)) into result
>> > | > finally (return (sort result #'> :key #'cdr))))
>> > | >
>> > |
>> > | This is so very terse! I'm amazed.
>> > +---------------
>> >
>> > Well, it may be terse, but Frank was being kind when he said
>> > "not very fast". In fact, for large input lists (of length N,
>> > say) with many kinds of items (M, say), it can be dog slow!!
>> > It's at *least* as bad as N * M, since it scans the *entire*
>> > input list once for each kind of element. And it might be worse
>> > than that, depending on the characteristics of your implementation's
>> > REMOVE-DUPLICATES [but that's probably hash-based, and thus fast,
>> > see below].
>> >
>> > Note that the hash-table solutions you were given [such as Geoff's]
>> > will take time closer to N + M, that is, N for populating the
>> > hash table and M for dumping it.
>> >
>> > For N small enough to fit on a screen, both will run blazingly
>> > fast -- you'd never be able to tell the difference -- but for
>> > N = 10000 and M = 1000, the former is ~900 *times* slower.
>> >
>> > Of course, the SORT occurs in both, and probably adds an amount
>> > of around M * (log M). If you *really* wanted to speed this up for
>> > large inputs, you'd figure out how to count and sort simultaneously,
>> > e.g., maybe use some kind of clever balanced tree to insert into,
>> > or a pair of them, one indexed on the keys and one on the counts,
>> > and rebalance both as needed.
>> >
>> > Or something... ;-} ;-}
>> >
>> >
>> > -Rob
>> >
>> > -----
>> > Rob Warnock <····@rpw3.org>
>> > 627 26th Avenue <URL:http://rpw3.org/>
>> > San Mateo, CA 94403 (650)572-2607
>>
>> I'm not sure you can beat O( M * log M ) for this - the sort operation
>> puts a definite limit on the improvements you can make. It's provable
>> that you can't do better than N * log N for a general-purpose sort of
>> of N elements. Even if you insert each element into a tree, each
>> insert would be O( log(M) ), repeated M times = O( M * log(M) ).
>>
>> But I agree that hash tables are definitely the way to go.
>>
>> - Bill
>
> Oh, hashtables... :) My book introduces them in chapter 4, right
> *after* this task was presented. I think I shall return to this
> question once I have finished my book, just to see how much of an
> improvement I can make! It's nice to be able to occasionally benchmark
> the learning process.
>
> -Jason
So here is my final solution:
(defun occurrences (list)
(let ((counts (make-hash-table :test #'eql))
(alist '()))
(dolist (item list)
(incf (gethash item counts 0)))
(maphash (lambda (k v) (setf alist (acons k v alist)))
counts)
(sort alist #'> :key #'cdr)))
I think it's reasonably clear and it ought to be pretty fast (provably
optimal, I think, since its time complexity is dominated by the sort,
whose complexity can't be reduced, as long as the implementation uses
an O(N log(N)) sorting algorithm). It should be O(N + M + Mlog(M));
the last term dominates, so the whole deal is O(Mlog(M)). Again, N is
the number of elements in the input and M is the number of distinct
elements in N.
Bill
Bill Atkins <············@rpi.edu> writes:
> "Jason" <·······@gmail.com> writes:
>
> So here is my final solution:
>
> (defun occurrences (list)
> (let ((counts (make-hash-table :test #'eql))
> (alist '()))
> (dolist (item list)
> (incf (gethash item counts 0)))
> (maphash (lambda (k v) (setf alist (acons k v alist)))
> counts)
> (sort alist #'> :key #'cdr)))
>
> I think it's reasonably clear and it ought to be pretty fast (provably
> optimal, I think, since its time complexity is dominated by the sort,
> whose complexity can't be reduced, as long as the implementation uses
> an O(N log(N)) sorting algorithm). It should be O(N + M + Mlog(M));
> the last term dominates, so the whole deal is O(Mlog(M)). Again, N is
> the number of elements in the input and M is the number of distinct
> elements in N.
It is optimal in the limiting case or just when comparing using the
big-O notation. I think you can make an information theoretic argument
to that effect.
As a practical matter, the winning algorithms differ only in what
structure they use for their dictionary for accumulating the count
information. There will be a cross-over point, based on the number of
unique keys which will determine whether the alist or the hash-table
implementation will be faster. It will vary from implementation to
implementation, depending on the relative speeds of ASSOC versus the
computation of the hash keys.
alists can be a good choice if they never get too long. They are also a
bit more flexible if you want to use a custom equality predicate.
--
Thomas A. Russ, USC/Information Sciences Institute
Bill Atkins <············@rpi.edu> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > Of course, the SORT occurs in both, and probably adds an amount
| > of around M * (log M). If you *really* wanted to speed this up for
| > large inputs, you'd figure out how to count and sort simultaneously,
| > e.g., maybe use some kind of clever balanced tree to insert into...
...
| I'm not sure you can beat O( M * log M ) for this - the sort operation
| puts a definite limit on the improvements you can make. It's provable
| that you can't do better than N * log N for a general-purpose sort of
| of N elements. Even if you insert each element into a tree, each
| insert would be O( log(M) ), repeated M times = O( M * log(M) ).
+---------------
Don't you mean N * log(M)? [N = input length, M = distinct kinds]
You have to do N searches/increments (with M inserts along the way),
so if a search is log(M) then just building the tree(s) is N * log(M)
[plus O(M) for inserts].
Hmmm... For *really* large N [that is, N >> M], even if one could
get some tree-insert method down to N * log(M) that's still larger
than the hash-table-plus-sort, which is N + M + (M * log(M), which
is just O(N) [for N>>M].
So... "Never mind..." ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
"Jason" <·······@gmail.com> writes:
> I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
> Lisp". I'm determined to master each chapter before progressing to the
> next. Having said that, on page 56 there is the following problem:
>
> 3. Define a function that takes a list and returns a list indicating
> the number of times each (eql) element appears, sorted from the most
> common element to the least common.
>
>> (occurences '(a b a d a c d c a)
> ((A . 4) (C. 2) (D. 2) (B. 1))
>
> Well, this "simple" task has been driving me crazy! I must have spent
> at least 10 hours working on it. Having said that, I SOLVED IT!!! :)
>
> Here's my solution:
>
> (setq input '(a b a d a c d c a))
> [...]
Here is how I'd do it:
- We will defer the sort requirement to some post-processing.
- We need to process a list sequentially.
We'll do it recursively (because it's simplier and funnier than iteratively),
using basic pattern:
(defun process-list (list)
(cond ((null list) 'done)
(t (do-something-with (car list)) (process-list (cdr list)))))
- Often, we can build the result directly from (car list) and
(process-list (cdr list)). This is the case here too, but it'd mean
the call to process-list wouldn't be a tail call, so we'd use O(n)
stack space. To avoid this, the solution is to pass the partial
result as argument to the recursive function:
(defun process-list (list result)
(cond ((null list) result
(t (process-list (cdr list)
(compute-partial-result (car list) result))))))
So we will have:
(defun occurences-1 (list result)
(cond ((null list) result)
(t (occurences-1 (cdr list)
(increment-counter (car list) result)))))
(defun occurences (list)
(sort (occurences-1 list '()) (lambda (a b) (>= (cdr a) (cdr b)))))
and we want increment-counter to increment the counter in the a-list.
We can do it applying the same process, but building a new a-list every time:
(defun increment-counter (item counter-alist)
(cond ((null counter-alist)
(list (cons item 1)))
((eql item (car (car counter-alist)))
(cons (cons item (1+ (cdr (car counter-alist))))
(cdr counter-alist)))
(t
(cons (car counter-alist)
(increment-counter item (cdr counter-alist))))))
But we would prefer to just increment the counter when the association
already exist instead of copying the a-list. This won't be a
functional procedure anymore:
(defun increment-counter (item counter-alist)
(let ((ass (assoc item counter-alist)))
(if ass
(progn (incf (cdr ass)) counter-alist)
(cons (cons item 1) counter-alist))))
Of course, increment-counter and occurences-1 may not be too useful
out of occurences, so we can put them as local functions with LABELS:
(defun occurences (list)
(labels ((increment-counter (item counter-alist)
(let ((ass (assoc item counter-alist)))
(if ass
(progn (incf (cdr ass)) counter-alist)
(cons (cons item 1) counter-alist))))
(occurences-1 (list result)
(cond ((null list) result)
(t (occurences-1 (cdr list)
(increment-counter (car list)
result))))))
(sort (occurences-1 list '()) (function >=) :key (function cdr))))
Now, if the list can be big, with a lot of different items, it'd be
better to use a hash table instead of an a-list to keep the counters:
(defun occurences (list)
(sort (loop with counters = (make-hash-table)
for item in list
do (incf (gethash item counters 0))
finally (return
(let ((result '()))
(maphash (lambda (k v) (push (cons k v) result))
counters)
result)))
(function >=) :key (function cdr)))
--
__Pascal Bourguignon__ http://www.informatimago.com/
"This machine is a piece of GAGH! I need dual Opteron 850
processors if I am to do battle with this code!"
Jason wrote:
> I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
> Lisp". I'm determined to master each chapter before progressing to the
> next. Having said that, on page 56 there is the following problem:
>
> 3. Define a function that takes a list and returns a list indicating
> the number of times each (eql) element appears, sorted from the most
> common element to the least common.
>
>> (occurences '(a b a d a c d c a)
> ((A . 4) (C. 2) (D. 2) (B. 1))
>
> Well, this "simple" task has been driving me crazy! I must have spent
> at least 10 hours working on it. Having said that, I SOLVED IT!!! :)
>
That's great that you persisted, I am sure you learned something that
will be very valuable later on. Here is another solution.
(defun occurences (list)
(sort (let (count-list)
(dolist (sym list)
(incf (cdr (assoc sym (pushnew (cons sym 0) count-list :key 'car)))))
count-list)
#'> :key 'cdr))
Wade
"Jason" <·······@gmail.com> writes:
> I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
> Lisp". I'm determined to master each chapter before progressing to the
> next. Having said that, on page 56 there is the following problem:
>
> 3. Define a function that takes a list and returns a list indicating
> the number of times each (eql) element appears, sorted from the most
> common element to the least common.
>
>> (occurences '(a b a d a c d c a)
> ((A . 4) (C. 2) (D. 2) (B. 1))
>
> Well, this "simple" task has been driving me crazy! I must have spent
> at least 10 hours working on it. Having said that, I SOLVED IT!!! :)
Wow! 10 hours, eh? You must have learned a lot in that time. It can be
frustrating, though.
You do realise, though, don't you? that by posting it here on c.l.l.,
you've thrown down the gauntlet, and there will be a mad rush and the
furious clatter of the many keyboards of long-time Lispers to show how
it can be done in one line... ;-)
Sad to say, the following is all I came up with. Not having peeked at
On Lisp ch. 3, I can't say if my chosen technique is what the
erstwhile Mr Graham had in mind or not. Probably not... :-)
(defun occurrences (input-list)
"Take a list and return a list indicating the number of times each
EQL element appears, sorted from the most common element to the least
common."
(let ((table (make-hash-table)))
(dolist (item input-list)
(incf (gethash item table 0)))
(let ((result-list '()))
(maphash #'(lambda (key value)
(push (cons key value) result-list))
table)
(sort result-list #'> :key 'cdr))))
CL-USER> (occurrences '(a b a d a c d c a e e e t t t q f g))
((A . 4) (T . 3) (E . 3) (C . 2) (D . 2) (G . 1) (F . 1) (Q . 1) (B . 1))
David
--
David Trudgett
http://www.zeta.org.au/~wpower/
That a complex structure such as a living organism could be formed by
chance without intelligent input has never been demonstrated in the
lab or anywhere else. Given enough time, the naturalistic world view
reasons, anything is at least possible. The problem with this view is
that the degree of information and complexity required for living
organisms to be able to "live" is such that, aside from deliberate
intelligent design, from what we know now, no matter what the
conditions, time alone will not allow for the naturalistic
construction of life.
-- Jerry R. Bergman, B.S., M.S. Psychology, Ph.D. in
Evaluation and Research, M.A. Sociology, Ph.D. Human Biology.
David Trudgett wrote:
> "Jason" <·······@gmail.com> writes:
>
> > I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
> > Lisp". I'm determined to master each chapter before progressing to the
> > next. Having said that, on page 56 there is the following problem:
> >
> > 3. Define a function that takes a list and returns a list indicating
> > the number of times each (eql) element appears, sorted from the most
> > common element to the least common.
> >
> >> (occurences '(a b a d a c d c a)
> > ((A . 4) (C. 2) (D. 2) (B. 1))
> >
> > Well, this "simple" task has been driving me crazy! I must have spent
> > at least 10 hours working on it. Having said that, I SOLVED IT!!! :)
>
> Wow! 10 hours, eh? You must have learned a lot in that time. It can be
> frustrating, though.
>
Tell me about it! I now know, however, the extend to which lists and
cons are most definitely NOT the same. (That was confusing me a few
days ago...)
> You do realise, though, don't you? that by posting it here on c.l.l.,
> you've thrown down the gauntlet, and there will be a mad rush and the
> furious clatter of the many keyboards of long-time Lispers to show how
> it can be done in one line... ;-)
Of course. Consider the gauntlet tossed. ;P
>
> Sad to say, the following is all I came up with. Not having peeked at
> On Lisp ch. 3, I can't say if my chosen technique is what the
> erstwhile Mr Graham had in mind or not. Probably not... :-)
>
> (defun occurrences (input-list)
> "Take a list and return a list indicating the number of times each
> EQL element appears, sorted from the most common element to the least
> common."
> (let ((table (make-hash-table)))
> (dolist (item input-list)
> (incf (gethash item table 0)))
> (let ((result-list '()))
> (maphash #'(lambda (key value)
> (push (cons key value) result-list))
> table)
> (sort result-list #'> :key 'cdr))))
>
> CL-USER> (occurrences '(a b a d a c d c a e e e t t t q f g))
> ((A . 4) (T . 3) (E . 3) (C . 2) (D . 2) (G . 1) (F . 1) (Q . 1) (B . 1))
>
>
> David
This is another example that shows just how much I have yet to learn.
Years of C, C++, Java, TCL, Bourne Shell and Perl have left me woefully
ill prepared to handle Lisp. I feel like I am *finally* starting to
grow up as a programmer. :)
-Jason
Actually, hash tables are out, because Graham doesn't introduce them
till the following chapter, and I presume each exercise is supposed to
be solved using only the constructs introduced so far.
On Wed, 01 Mar 2006 20:07:32 -0800, Jason wrote:
>
> 3. Define a function that takes a list and returns a list indicating
> the number of times each (eql) element appears, sorted from the most
> common element to the least common.
Here's practically the same thing (but a little more flexible) from my
utils.lisp:
(defun hashtable-to-alist (table)
"Convert a hashtable to an alist"
(let ((list nil))
(maphash (lambda (k v) (push (cons k v) list)) table)
list))
(defun histogram (sequence &optional (test #'equalp))
"Given a sequence, make a histogram of the objects in it"
(let ((table (make-hash-table :test test)))
(map nil
(lambda (object)
(incf (gethash object table 0)))
sequence)
(hashtable-to-alist table)))
To make it exactly the same (my version doesn't care about the order of
the result) you just have to add:
(defun occurrences (list)
(sort (histogram list #'eql) #'> :key #'cdr))
Best wishes,
Bill.
"Jason" <·······@gmail.com> writes:
> 3. Define a function that takes a list and returns a list indicating
> the number of times each (eql) element appears, sorted from the most
> common element to the least common.
>
> > (occurences '(a b a d a c d c a)
> ((A . 4) (C. 2) (D. 2) (B. 1))
>
> Well, this "simple" task has been driving me crazy! I must have spent
> at least 10 hours working on it. Having said that, I SOLVED IT!!! :)
>
> Here's my solution:
>
> (setq input '(a b a d a c d c a))
>
> (defun occurences (input-list)
> (let ((sorted-list (sort (copy-sequence input-list) 'string<))
> (a-list nil))
> (setq a-list (occurences-make-alist () sorted-list))
> (occurences-sort-alist a-list)))
Because of the initial sort, this will fail if you pass anything other
than numbers or strings. In particular, it will fail on the following
input:
(a b a d 2 c d e 2 3)
--
Thomas A. Russ, USC/Information Sciences Institute
Jason wrote:
> I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
> Lisp". I'm determined to master each chapter before progressing to the
> next. Having said that, on page 56 there is the following problem:
>
> 3. Define a function that takes a list and returns a list indicating
> the number of times each (eql) element appears, sorted from the most
> common element to the least common.
>
>> (occurences '(a b a d a c d c a)
> ((A . 4) (C. 2) (D. 2) (B. 1))
>
> Well, this "simple" task has been driving me crazy! I must have spent
> at least 10 hours working on it. Having said that, I SOLVED IT!!! :)
>
> Here's my solution:
>
> (setq input '(a b a d a c d c a))
>
> (defun occurences (input-list)
> (let ((sorted-list (sort (copy-sequence input-list) 'string<))
> (a-list nil))
> (setq a-list (occurences-make-alist () sorted-list))
> (occurences-sort-alist a-list)))
>
> (defun occurences-sort-alist (a-list)
> (sort a-list 'occurences-greater))
>
> (defun occurences-greater (node-1 node-2)
> (> (cdr node-1) (cdr node-2)))
>
> (defun occurences-make-alist (a-list sorted-list)
> (let ((node nil)
> (remainder nil))
> (if (not (null sorted-list))
> (progn
> (setq node (occurences-get-token-cons sorted-list))
> (setq remainder (occurences-remainder node sorted-list))
> (setq a-list (append a-list node (occurences-make-alist a-list
> remainder)))))
> a-list))
>
> (defun occurences-remainder (node sorted-list)
> (if (null node)
> sorted-list
> (subseq sorted-list (cdr (car node)))))
>
> (defun occurences-get-token-cons (sorted-list)
> (if (null sorted-list)
> nil
> (progn
> (let ((tok (car sorted-list)) (count 1))
> (setq count (occurences-get-token-count tok count (cdr sorted-list)))
> (list (cons tok count))))))
>
> (defun occurences-get-token-count (token count input-list)
> (if (eql token (car input-list))
> (setq count (+ count (occurences-get-token-count token count (cdr
> input-list)))))
> count)
>
> (occurences input)
>
> ;;; END
>
> And, it works! :)
>
> -Jason
>
Here is another solution in the style of "The Little Schemer."
It uses cond, car, and, cdr only.
(define a-count
(lambda (a lat)
(cond
((null? lat) 0)
((equal? a (car lat)) (+ 1 (a-count a (cdr lat))))
(else (a-count a (cdr lat))))))
(define rember*
(lambda (a lat)
(cond
((null? lat) '())
((equal? a (car lat)) (rember* a (cdr lat)))
(else (cons (car lat) (rember* a (cdr lat)))))))
(define occurrences
(lambda (lat)
(cond
((null? lat) '())
(else
(cons (cons (car lat)
(a-count (car lat) lat))
(occurrences (rember* (car lat) (cdr lat))))))))
(occurrences '(a b a d a c d c a))
Anon wrote:
> Jason wrote:
>> I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
>> Lisp". I'm determined to master each chapter before progressing to the
>> next. Having said that, on page 56 there is the following problem:
>>
>> 3. Define a function that takes a list and returns a list indicating
>> the number of times each (eql) element appears, sorted from the most
>> common element to the least common.
>>
>>> (occurences '(a b a d a c d c a)
>> ((A . 4) (C. 2) (D. 2) (B. 1))
>>
>> Well, this "simple" task has been driving me crazy! I must have spent
>> at least 10 hours working on it. Having said that, I SOLVED IT!!! :)
>>
>> Here's my solution:
>>
>> (setq input '(a b a d a c d c a))
>>
>> (defun occurences (input-list)
>> (let ((sorted-list (sort (copy-sequence input-list) 'string<))
>> (a-list nil))
>> (setq a-list (occurences-make-alist () sorted-list))
>> (occurences-sort-alist a-list)))
>>
>> (defun occurences-sort-alist (a-list)
>> (sort a-list 'occurences-greater))
>>
>> (defun occurences-greater (node-1 node-2)
>> (> (cdr node-1) (cdr node-2)))
>>
>> (defun occurences-make-alist (a-list sorted-list)
>> (let ((node nil)
>> (remainder nil))
>> (if (not (null sorted-list))
>> (progn
>> (setq node (occurences-get-token-cons sorted-list))
>> (setq remainder (occurences-remainder node sorted-list))
>> (setq a-list (append a-list node (occurences-make-alist a-list
>> remainder)))))
>> a-list))
>>
>> (defun occurences-remainder (node sorted-list)
>> (if (null node)
>> sorted-list
>> (subseq sorted-list (cdr (car node)))))
>>
>> (defun occurences-get-token-cons (sorted-list)
>> (if (null sorted-list)
>> nil
>> (progn
>> (let ((tok (car sorted-list)) (count 1))
>> (setq count (occurences-get-token-count tok count (cdr sorted-list)))
>> (list (cons tok count))))))
>>
>> (defun occurences-get-token-count (token count input-list)
>> (if (eql token (car input-list))
>> (setq count (+ count (occurences-get-token-count token count (cdr
>> input-list)))))
>> count)
>>
>> (occurences input)
>>
>> ;;; END
>>
>> And, it works! :)
>>
>> -Jason
>>
>
> Here is another solution in the style of "The Little Schemer."
> It uses cond, car, and, cdr only.
>
> (define a-count
> (lambda (a lat)
> (cond
> ((null? lat) 0)
> ((equal? a (car lat)) (+ 1 (a-count a (cdr lat))))
> (else (a-count a (cdr lat))))))
>
> (define rember*
> (lambda (a lat)
> (cond
> ((null? lat) '())
> ((equal? a (car lat)) (rember* a (cdr lat)))
> (else (cons (car lat) (rember* a (cdr lat)))))))
>
> (define occurrences
> (lambda (lat)
> (cond
> ((null? lat) '())
> (else
> (cons (cons (car lat)
> (a-count (car lat) lat))
> (occurrences (rember* (car lat) (cdr lat))))))))
>
> (occurrences '(a b a d a c d c a))
Oops! looked too fast.
I realize now it has to be sorted.
Back to the drawing board.
Anon wrote:
> Anon wrote:
>> Jason wrote:
>>> I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
>>> Lisp". I'm determined to master each chapter before progressing to the
>>> next. Having said that, on page 56 there is the following problem:
>>>
>>> 3. Define a function that takes a list and returns a list indicating
>>> the number of times each (eql) element appears, sorted from the most
>>> common element to the least common.
>>>
>>>> (occurences '(a b a d a c d c a)
>>> ((A . 4) (C. 2) (D. 2) (B. 1))
>>>
>>> Well, this "simple" task has been driving me crazy! I must have spent
>>> at least 10 hours working on it. Having said that, I SOLVED IT!!! :)
>>>
>>> Here's my solution:
>>>
>>> (setq input '(a b a d a c d c a))
>>>
>>> (defun occurences (input-list)
>>> (let ((sorted-list (sort (copy-sequence input-list) 'string<))
>>> (a-list nil))
>>> (setq a-list (occurences-make-alist () sorted-list))
>>> (occurences-sort-alist a-list)))
>>>
>>> (defun occurences-sort-alist (a-list)
>>> (sort a-list 'occurences-greater))
>>>
>>> (defun occurences-greater (node-1 node-2)
>>> (> (cdr node-1) (cdr node-2)))
>>>
>>> (defun occurences-make-alist (a-list sorted-list)
>>> (let ((node nil)
>>> (remainder nil))
>>> (if (not (null sorted-list))
>>> (progn
>>> (setq node (occurences-get-token-cons sorted-list))
>>> (setq remainder (occurences-remainder node sorted-list))
>>> (setq a-list (append a-list node (occurences-make-alist a-list
>>> remainder)))))
>>> a-list))
>>>
>>> (defun occurences-remainder (node sorted-list)
>>> (if (null node)
>>> sorted-list
>>> (subseq sorted-list (cdr (car node)))))
>>>
>>> (defun occurences-get-token-cons (sorted-list)
>>> (if (null sorted-list)
>>> nil
>>> (progn
>>> (let ((tok (car sorted-list)) (count 1))
>>> (setq count (occurences-get-token-count tok count (cdr
>>> sorted-list)))
>>> (list (cons tok count))))))
>>>
>>> (defun occurences-get-token-count (token count input-list)
>>> (if (eql token (car input-list))
>>> (setq count (+ count (occurences-get-token-count token count (cdr
>>> input-list)))))
>>> count)
>>>
>>> (occurences input)
>>>
>>> ;;; END
>>>
>>> And, it works! :)
>>>
>>> -Jason
>>>
>>
>> Here is another solution in the style of "The Little Schemer."
>> It uses cond, car, and, cdr only.
>>
>> (define a-count
>> (lambda (a lat)
>> (cond
>> ((null? lat) 0)
>> ((equal? a (car lat)) (+ 1 (a-count a (cdr lat))))
>> (else (a-count a (cdr lat))))))
>>
>> (define rember*
>> (lambda (a lat)
>> (cond
>> ((null? lat) '())
>> ((equal? a (car lat)) (rember* a (cdr lat)))
>> (else (cons (car lat) (rember* a (cdr lat)))))))
>>
>> (define occurrences
>> (lambda (lat)
>> (cond
>> ((null? lat) '())
>> (else
>> (cons (cons (car lat)
>> (a-count (car lat) lat))
>> (occurrences (rember* (car lat) (cdr lat))))))))
>>
>> (occurrences '(a b a d a c d c a))
>
> Oops! looked too fast.
> I realize now it has to be sorted.
> Back to the drawing board.
;; Sorted by the occurrence field, the cdr or the pair.
(define a-count
(lambda (a lat)
(cond
((null? lat) 0)
((eqv? (car lat) a) (+ 1 (a-count a (cdr lat))))
(else (a-count a (cdr lat))))))
(define rember-if
(lambda (test? a lat)
(cond
((null? lat) '())
((test? a (car lat)) (rember-if test? a (cdr lat)))
(else (cons (car lat) (rember-if test? a (cdr lat)))))))
(define occurrences
(lambda (lat)
(cond
((null? lat) '())
(else
(cons (cons (car lat)
(a-count (car lat) lat))
(occurrences (rember-if eqv? (car lat) (cdr lat))))))))
(define sort-it
(lambda (lst)
(cond
((null? lst) '())
(else
(append (sort-it (rember-if (lambda (a b)
(>= (cdr a) (cdr b)))
(car lst) (cdr lst)))
(list (car lst))
(sort-it (rember-if (lambda (a b)
(< (cdr a) (cdr b)))
(car lst) (cdr lst))))))))
(define sorted-occurrences
(lambda (lat)
(sort-it (occurrences lat))))
(sorted-occurrences '(a b a d a c d c a))
((a . 4) (d . 2) (c . 2) (b . 1))
I was curious about the efficiency of various approaches, so I tried to
create some utility functions for this purpose, and added the following
hashtable-based solution to my other two above:
(defun occurrences-h (lst)
(let ((counts (make-hash-table)))
(dolist (elem lst)
(incf (gethash elem counts 0)))
(let ((items nil))
(maphash #'(lambda (k v) (push (cons k v) items)) counts)
(sort items #'> :key #'cdr))))
I used the following functions for timing and generating fake data:
(defun occurrences-sample-data
(num-elems num-distinct-elems &optional (state *random-state*))
"Returns a list of symbols for testing occurrences algorithms,
such that there are num-elems total elements comprised of
num-distinct-elems distinct elements selected randomly using
the optional state argument."
(let ((distinct-elems (generate-symbols num-distinct-elems))
(data nil))
(dotimes (i num-elems data)
(push (aref distinct-elems (random num-distinct-elems state))
data))))
(defun generate-symbols (n)
"Returns a vector of n distinct unused symbols."
(let ((symbols (make-array (list n) :element-type 'symbol)))
(dotimes (i n symbols)
(setf (aref symbols i) (gensym)))))
(defun time-fn (fn fn-name num-elems num-distinct-elems)
"Time an occurrences function fn with string name fn-name on
a randomly generated list of length num-elems consisting of
num-distinct-elems distinct elements."
(let ((lst (occurrences-sample-data
num-elems num-distinct-elems
(make-random-state *random-state*))))
(progn
(gc :full t)
(format t "~%----~%Function: ~A~%Total elems: ~A~%Distinct elems:
~A~%~%"
fn-name num-elems num-distinct-elems)
(time (funcall fn lst)))
nil))
(Apologies for the weird wrapping, but google groups was wrapping long
lines at bad places.)
Here is the output of running my first solution above and the
hashtable-based solution in this message. I ran them both twice, on a
list of 100,000 elements, with the number of distinct elements
variously at 10, 100, 1000, and 10,000:
CL-USER> (dolist (fn-symbol '(occurrences occurrences-h occurrences
occurrences-h))
(let ((total-elems (* 100 1000)))
(dolist (num-distinct-elems '(10 100 1000 10000))
(time-fn (symbol-function fn-symbol) (symbol-name fn-symbol)
total-elems num-distinct-elems))))
----
Function: OCCURRENCES
Total elems: 100000
Distinct elems: 10
Evaluation took:
0.028 seconds of real time
0.028001 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
----
Function: OCCURRENCES
Total elems: 100000
Distinct elems: 100
Evaluation took:
0.191 seconds of real time
0.184011 seconds of user run time
0.008001 seconds of system run time
0 page faults and
8,192 bytes consed.
----
Function: OCCURRENCES
Total elems: 100000
Distinct elems: 1000
Evaluation took:
2.003 seconds of real time
1.740109 seconds of user run time
0.040002 seconds of system run time
0 page faults and
81,920 bytes consed.
----
Function: OCCURRENCES
Total elems: 100000
Distinct elems: 10000
Evaluation took:
20.295 seconds of real time
19.905245 seconds of user run time
0.036002 seconds of system run time
0 page faults and
1,146,880 bytes consed.
----
Function: OCCURRENCES-H
Total elems: 100000
Distinct elems: 10
Evaluation took:
0.022 seconds of real time
0.020001 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
----
Function: OCCURRENCES-H
Total elems: 100000
Distinct elems: 100
Evaluation took:
0.024 seconds of real time
0.024001 seconds of user run time
0.0 seconds of system run time
0 page faults and
11,304 bytes consed.
----
Function: OCCURRENCES-H
Total elems: 100000
Distinct elems: 1000
Evaluation took:
0.024 seconds of real time
0.024002 seconds of user run time
0.0 seconds of system run time
0 page faults and
169,560 bytes consed.
----
Function: OCCURRENCES-H
Total elems: 100000
Distinct elems: 10000
Evaluation took:
0.043 seconds of real time
0.040002 seconds of user run time
0.0 seconds of system run time
0 page faults and
1,780,952 bytes consed.
----
Function: OCCURRENCES
Total elems: 100000
Distinct elems: 10
Evaluation took:
0.036 seconds of real time
0.036002 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
----
Function: OCCURRENCES
Total elems: 100000
Distinct elems: 100
Evaluation took:
0.234 seconds of real time
0.224014 seconds of user run time
0.0 seconds of system run time
0 page faults and
8,192 bytes consed.
----
Function: OCCURRENCES
Total elems: 100000
Distinct elems: 1000
Evaluation took:
2.194 seconds of real time
2.176136 seconds of user run time
0.0 seconds of system run time
0 page faults and
86,016 bytes consed.
----
Function: OCCURRENCES
Total elems: 100000
Distinct elems: 10000
Evaluation took:
20.527 seconds of real time
19.881243 seconds of user run time
0.052003 seconds of system run time
0 page faults and
1,146,880 bytes consed.
----
Function: OCCURRENCES-H
Total elems: 100000
Distinct elems: 10
Evaluation took:
0.022 seconds of real time
0.024002 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
----
Function: OCCURRENCES-H
Total elems: 100000
Distinct elems: 100
Evaluation took:
0.025 seconds of real time
0.020001 seconds of user run time
0.0 seconds of system run time
0 page faults and
11,304 bytes consed.
----
Function: OCCURRENCES-H
Total elems: 100000
Distinct elems: 1000
Evaluation took:
0.024 seconds of real time
0.024001 seconds of user run time
0.0 seconds of system run time
0 page faults and
168,064 bytes consed.
----
Function: OCCURRENCES-H
Total elems: 100000
Distinct elems: 10000
Evaluation took:
0.044 seconds of real time
0.036002 seconds of user run time
0.004 seconds of system run time
0 page faults and
1,780,952 bytes consed.
NIL
CL-USER>
I'll try some other implementations by others later, but am too tired
at the moment. It's no surprise that the hashtable solution dominates,
for the large number of distinct elements especially.
Here's an attempt to reduce the time spent sorting by mapping multiple
elements from the list which have the same number of values as a single
mapping in the list that gets sorted:
(defun occurrences-h3 (lst)
"Alternate hashtable solution that tries to sort on a smaller list by
grouping
all items in the original list that have the same number of values
as 1 pair."
(let ((counts (make-hash-table)) ; for (A . 4) (C . 2)-type counts
(rcounts (make-hash-table)) ; for collecting reverse-count
pairs for rev-list
(rev-list) ; for sorting the (4 . (A
B))-type pairs
(final-list)) ; for unpacking the previous list
into
;; first, get the hashtable of (A . 4) (B . 4) (C . 2)-type pairs
(dolist (elem lst)
(incf (gethash elem counts 0)))
;; then convert it to (4 . (A B)) (2 . (C))-type pairs
(maphash #'(lambda (k v) (setf (gethash v rcounts) (cons k
(gethash v rcounts))))
counts)
;; then put them into a list in order to sort
(maphash #'(lambda (k v) (push (cons k v) rev-list))
rcounts)
;; then sort them, and for each element in the sorted list,
;; unpack (4 . (A B)) to (A . 4) (B . 4)
(dolist (itm (sort rev-list #'< :key #'car))
(let ((cnt (car itm)))
(dolist (sym (cdr itm))
(push (cons sym cnt) final-list))))
final-list))
This seems about as fast and sometimes slightly faster than the
previous version that sorted, and uses less memory, despite all the
extra work that it is doing.
Perhaps there is a better way of doing something like this in order to
keep the sort list with as few items as possible.