Re: fastest data structure for a hash-like lookup

[lawrence mitchell <wence@gmx.li>]

Florian von Savigny wrote:

> Hi folks,

> I need a data structure that can be accessed via a key (the keys are
> unique), which points to a value that is a list (in the general sense,
> not in the elisp sense) of three elements. [In Perl, I would implement
> this as a hash where the values are references to lists.]. It may also
> be thought of as a structure with keys that point to "a set of three
> values" each. The structure would be quite large and not be
> manipulated by the elisp program, but merely serve as a lookup table.

> I think I've read something that sounded like a vector would be the
> right thing to use (is not changed, is fast), but I haven't found any
> advice on that. Or is it an obarray? A property list? An alist? An
> array? A combination of two? And how would that look like?

Hmm, how about a hash-table :).

/----[ C-h f make-hash-table RET ]
| make-hash-table is a built-in function.
| (make-hash-table &rest KEYWORD-ARGS)
|
| Create and return a new hash table.
|
| Arguments are specified as keyword/argument pairs.  The following
| arguments are defined:
|
| [...]
|
\----

In Emacs 21, hash tables are built in, in Emacs 20, you may need
to do (require 'cl), to get at the CL package's hash tables.

[...]

If you, in fact, do not want to use hash tables, then, for
random access, a vector might be the best idea, however, IIRC,
you can't access an element via a key with a vector.  So, you
might be better-off with an alist/plist, both of these have
linear access time.

-- 
lawrence mitchell <wence@gmx.li>