Re: Which Elisp data structure is fastest for searching?

[Jean Louis]

* tomas@tuxteam.de <tomas@tuxteam.de> [2024-12-26 12:25]:
> 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.

Sure, that is why I am asking possibly those who made better
experience with it.

(measure-time (seq-filter (lambda (item) (when (string-match "MY QUERY" (cdr 
item)) item)) my-alist)) ➜ "0.004352"

(measure-time (seq-filter (lambda (item) (when (string-match "MY QUERY" item) 
item)) my-list)) ➜ "0.004252"

(measure-time (delq nil (mapcar (lambda (key) (when (string-match "MY QUERY" 
(gethash key my-hash)) key)) (hash-table-keys my-hash)))) ➜ "0.004506"

I have measured list, alist, hash, with bit different functions, for
my 1300 page information pieces, I will keep measuring. Though small
inconceivable differences matter not.

I think hash method is so much easier, I can keep it all in the single
hash, and only query those keys which are relevant:

Following I would not query:

    (puthash (intern (format "id-%d-name" id)) name wrs-search-hash)
    (puthash (intern (format "id-%d-link" id)) link wrs-search-hash)
    (puthash (intern (format "id-%d-description" id)) description 
wrs-search-hash)
    (puthash (intern (format "id-%d-keywords" id)) keywords wrs-search-hash)))

I would query only those which are numeric, for example. Then I would
use `id-123-name' to get the name for numeric key 123.

> 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.

I will need to use AND, OR, NOT and there will be little different
functions to search within the has depending of the combinations
allowed.

> 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.

I will only use values to search name, url, description, summary

> 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).

Okay, thanks. 

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

I think 1300 x 4 elements is small thing.

> 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)))) 

➜ ("Elapsed time: 0.030115s" . "Elapsed time: 0.028604s")

I see no much difference, important is there is no human noticeable 😐
too long ⏱️ lag, small ⚖️ lags are always there 👍.

Okay thanks, I am advancing.

-- 
Jean Louis

signature.asc
Description: PGP signature