Re: How do I make this utility more flexible without losing speed?



Chaitanya Gupta wrote:
Geoff Wozniak wrote:

On May 9, 2:41 am, Chaitanya Gupta <m...@xxxxxxxxxxxxxxxxxx> wrote:

Alan Manuel K. Gloria wrote:

Hmm, as far as I can tell, hash tables would be the best for your
problem domain.

Point. That's the problem I am trying to solve.


Why not both hash tables and lists, depending on the situation?

(defun group-hash (list test key)
(let ((hash-table (make-hash-table :test test)))
(dolist (el list)
(push el (gethash (funcall key el) hash-table)))
(loop
for val being the hash-value in hash-table
collect val into vals
finally (return vals))))

(defun group-list (list test key)
(let ((groups nil))
(dolist (elt list groups)
(let ((pos (position (funcall key elt) groups :test
(lambda (e group)
(funcall test e
(funcall key (car
group)))))))
(if pos
(push elt (nth pos groups))
(push (list elt) groups))))))

(defun standard-test-function-p (fn)
(member fn (list 'eq #'eq
'eql #'eql
'equal #'equal
'equalp #'equalp)))

(defun group (list &key (test #'eql) (key #'identity))
"Groups items in a list based on TEST and KEY. If TEST is one of
the
standard equality functions, the function will likely be considerably
faster."
(if (standard-test-function-p test)
(group-hash list test key)
(group-list list test key)))


Cool. Didn't think about that. From what I know till now, this is probably the optimum solution.

What happens if you have a non-standard test and a large dataset?

Part of the problem is your definition of the problem: you limit
solutions to standard Lisp constructs. Is this homework? If not, use
something non-standard, a C library or your own hashing algorithm.

But if you really really really want to use only standard Lisp, then
listen to yourself!:

You want hash tables for speed, and they only take certain tests. So you
have to use one of those tests:

(group2 *strings*
:key #'(lambda (x &aux (c (char x 0)))
(cons c (upper-case-p c)))
:test #'equal)

ie, if the mountain won't come to your test function, your key function
must go to the mountain.

hth,kzo

--
http://www.theoryyalgebra.com/

"Algebra is the metaphysics of arithmetic." - John Ray

"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts

"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz

"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen


.

Relevant Pages