faster dictionary?

[hsmyers]

Which is faster(just curious, not optimizing); a dictionary built like:

Code Select Expand


(set 'board '(
  ("a1" ("r" "w"))
  ("b1" ("n" "w"))
  ("c1" ("b" "w"))
  ("d1" ("q" "w"))
  ("e1" ("k" "w"))
  ("f1" ("b" "w"))
  ("g1" ("n" "w"))
  ("h1" ("r" "w"))))

or using the context with a custom function like:

Code Select Expand


 (board "a1" (list "r" "w" "w"))
  (board "b1" (list "n" "w" "b"))
  (board "c1" (list "b" "w" "w"))
  (board "d1" (list "q" "w" "b"))
  (board "e1" (list "k" "w" "w"))
  (board "f1" (list "b" "w" "b"))
  (board "g1" (list "n" "w" "w"))
  (board "h1" (list "r" "w" "b"))

Faster(more efficient etc.) in terms of creation and use. This for small dictionaries of fixed size.



--hsm

[cormullion]

Timing is easily done with the time function. Usually, you'll have to repeat the operation a lot of times before getting a sensible value.

Code Select Expand

(println (time (set 'board '(
  ("a1" ("r" "w"))
  ("b1" ("n" "w"))
  ("c1" ("b" "w"))
  ("d1" ("q" "w"))
  ("e1" ("k" "w"))
  ("f1" ("b" "w"))
  ("g1" ("n" "w"))
  ("h1" ("r" "w")))) 1000))

gives about 8 milliseconds for building that list 1000 times.



The context method comes in at about 40ms, but would be quicker - down to about 30ms - if you replaced the list with a simple '.



Using lookup on the first list is barely measurable - 0ms for 1000 reps... :). The context lookup is a couple of milliseconds.

[hsmyers]

Much thanks for data and info about time function. Should have known something like that would exist--- when I saw it in the function list I blanked on it thinking yet another time of day routine. Bad me!



--hsm

p.s. you meant:

Code Select Expand


(board "a1" '("r" "w" "w"))

yes?

[cormullion]

yes ;)

[Jeff]

It depends on size.  Contexts are better for large sets, lists for smaller sets.  Lists are more like O(n) access time, while contexts, after the initial penalty for creation, are around O(log n) access.