Re: Which Elisp data structure is fastest for searching?

[tomas]

On Thu, Dec 26, 2024 at 11:53:38AM +0300, Jean Louis wrote:

[Hashes vs. ...]

> > This is why different data structures exist. There is no "best"; only "best
> > for..."
> 
> As is written in manual that hash table is very fast, I believe yes,
> though my search may not be.

Never believe such a thing out-of-context.

As others have already pointed out, it depends *a lot* on how you are
searching. If your search always involves *exact* matches, hash tables
might be what you need. If these are more complex matches (think, as
a working example: case-insensitive match), "naked" hashes are pretty
useless, since your code might well end up walking all of the entries
to apply the "custom comparison function" anyway.

Sometimes (again, think our "case-insensitive match" example, a hash
still might be useful: you may map the keys appropriately before
hashing (again, in our example: lower case) and search for the equally
mapped search item. Sometimes this reduces precision and you may get
"false positives" -- but then you can refine your sequential search
over a much reduced set (this is, BTW, the same thing hash tables do,
but I disgress).

That's, roughly, how databases do their thing.

Another context point is size. For small things, hashes haven't an
advantage over alists.

Here's a small code snippet. On my machine, and in the current
moon phase, hashes overtake alists at roughly 10 entries:

(let* ((size 10) ; alist, hash size
       (runs 100000) ; benchmark runs
       (alist '())
       (hash (make-hash-table :test 'eq :size 1549))
       (keys (make-vector size nil))
       (count size))
  ;; setup
  (while (> count 0)
    (setq count (1- count))
    (let ((sym (intern (format "SYM%04d%03d" (random 10000) count))))
      (aset keys count sym)
      (setq alist (cons (cons sym "foo") alist))
      (puthash sym "foo" hash)))
  ;; run
  (cons
   (benchmark runs '(assq (aref keys (random size)) alist))
   (benchmark runs '(gethash (aref keys (random size)) hash))))

Tools, jobs and that. If you enter a carpenter's shop, you never
ever will find just one tool hanging of the wall.

Cheers
-- 
t

signature.asc
Description: PGP signature