Counting occurences
in [Lisp]
|
Prev: Black-Jewish History FAQ - Is The Secret Relationship between blacks and jews a “hate literature”?
Next: which library to generate xml with namespaces?
From: RG on 18 Jun 2010 17:04 In article <hvgfqg$a87$1(a)news.eternal-september.org>, Tim Bradshaw <tfb(a)tfeb.org> wrote: > On 2010-06-18 17:59:32 +0100, RG said: > > > dictionary.lisp is only 295 LOC including comments and blank lines. > > Even if you add in rg-utils (only a tiny part of which is used by > > dictionary.lisp) that's only an addition 970 LOC. That is not "huge" by > > any stretch of the imagination. > > It's about two orders of magnutude larger than simple versions of > occurrence-counting funcions using alists or hashtables (both of which > come out at around 7 lines without comments, so maybe 9 with): > > (defun occ/alist (list &key (test #'eql)) > (loop with al = '() > for e in list > for a = (or (assoc e al :test test) > (first (push (cons e 0) al))) > do (incf (cdr a)) > finally (return al))) > > (defun occ/hash (list &key (test #'eql)) > (loop with ht = (make-hash-table :test test) > for e in list > do (incf (gethash e ht 0)) > finally (return (loop for k being the hash-keys of ht using (hash-value v) > collect (cons k v))))) > > That's just dictionaries. This depends on how you count. LOC always depend on what you choose to count as code and what you choose to count as library. You are using LOOP, whose implementation is a helluva lot bigger than dictionaries. > It's OK, I don't expect you to understand the point I'm making, or agree. That train seems to be running both ways. rg
From: Marcus Breiing on 18 Jun 2010 17:42 * Bob Felts > You're arguing about LOC, Ron is arguing about correct abstraction. Read Chapter 18.1.1 of the CLHS: The CL hash-table itself is an abstraction. For example, the implementation already is free to choose "an underlying implementation based on run-time profiling without changing your client code", to quote a part of his justification. Piling complication on top of this simple abstraction could make sense in the context of advanced application design, but is it good paedagogy for beginners?
From: Thomas A. Russ on 18 Jun 2010 17:27 Eric Wolf <eric(a)boese-wolf.eu> writes: > Hello there! > > I'm starting to learn lisp and doing the exercises of Ansi Common Lisp > authored by Paul Graham. > > So my solution to counting occurences in a list and outputting a > list of dotted pairs (symbol . count) sorted by count is > > (defun occurences-helper (lst result) > (if (null lst) > result > (progn > (let ((symb (car lst))) > (let ((test (assoc symb result))) > (if test > (setf (cdr test) (+ (cdr test) 1)) > (setf result (cons (cons symb 1) result))))) > (occurences-helper (cdr lst) result)))) > > (defun occurences (lst) > (sort > (occurences-helper lst ()) > #'(lambda (x y) > (> > (cdr x) > (cdr y)))) > ) > > > And I thought: "Hmm that doesn't look elegant" but I'm not used to > recursion and functional programming and that stuff so I didn't > came up with a better version. Well, with one more level of abstraction and the use of more of the arguments to SORT, you can come up with something very similar that looks more elegant. ;; Adds increment to the matching counts item and ;; (importantly) returns the updated counts structure (defun add-to-count (key counts &optional (increment 1)) (let ((entry (assoc key counts))) (if entry (progn (incf (cdr entry) increment) counts) (acons key 1 counts)))) (defun occurences-helper (lst result) (if (null lst) result (occurences-helper (cdr lst) (add-to-count (car lst) results)))) (defun occurences (lst) (sort (occurences-helper lst ()) #'> :key #'cdr)) -- Thomas A. Russ, USC/Information Sciences Institute
From: RG on 18 Jun 2010 20:47 In article <bmmbef4ptsedn(a)breiing.com>, Marcus Breiing <usenet(a)2010w24.mail.breiing.com> wrote: > * Bob Felts > > > You're arguing about LOC, Ron is arguing about correct abstraction. > > Read Chapter 18.1.1 of the CLHS: The CL hash-table itself is an > abstraction. For example, the implementation already is free to choose > "an underlying implementation based on run-time profiling without > changing your client code", to quote a part of his justification. No. While it is true that the spec is not explicit about this, it does place certain constraints on hash tables. For example, CL hash tables cannot under any circumstances assume that the keys have a total order, so they cannot be implemented by any underlying data structure that requires that the keys be ordered. Furthermore, the existence of hash-table-rehash-size, and the rehash-size and rehash-threshold arguments to make-hash-table doesn't make any sense if the underlying implementation is anything other than a hash table. Finally (and only on CLL would one have to point this out) the fact that these things are called "hash tables" very strongly implies that they are in fact hash tables and not something else. > Piling complication on top of this simple abstraction could make sense > in the context of advanced application design, but is it good > paedagogy for beginners? Of course it is. Why would you doubt it? rg
From: Captain Obvious on 18 Jun 2010 18:31
BF> You're arguing about LOC, Ron is arguing about correct abstraction. There is no such thing as a "correct abstraction." If code works, it is correct. Otherwise, we can put a shitload of abstractions on top of it -- but will it make it better? |