fastest data structure for a hash-like lookup

fastest data structure for a hash-like lookup

[Florian von Savigny]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1322 bytes --]




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?

Sorry I wasn't able to find any useful documentation (the manual is as
terse as ever). Neither an archive nor an FAQ seems to be available
for this group, and though there is plenty of interesting elisp code
available, there seems to be no discussion of elisp programming but
here.

Thanks a lot in advance,



Florian v. Savigny

If you are going to reply in private, please be patient, as I only
check for mail something like once a week. - Si vous allez répondre
personellement, patientez s.v.p., car je ne lis les courriels
qu'environ une fois par semaine.

Re: fastest data structure for a hash-like lookup

[lawrence mitchell]

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>

Re: fastest data structure for a hash-like lookup

[Kevin Rodgers]

Florian von Savigny wrote:

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

You definitly want to use an obarray.  From each key string, generate a symbol
in the obarray whose value is the list you want to look up.

(defvar my-hash (make-vector some-large-prime-number 0))

(defun my-hash-set (key value)
   (set (intern key my-hash) value))

(defun my-hash-get (key)
   (symbol-value (intern-soft key my-hash)))

-- 
<a href="mailto:&lt;kevin.rodgers&#64;ihs.com&gt;">Kevin Rodgers</a>

Re: fastest data structure for a hash-like lookup

[Stefan Monnier]

> I need a data structure that can be accessed via a key (the keys are

What do the keys look like ?  Can you choose them freely ?
In elisp, it seems you could use a hash table of
lisp lists, vectors, or structures.
See `defstruct' in the CL manual for structure.
See `make-hash-table' in the elisp manual.

> values" each. The structure would be quite large and not be
> manipulated by the elisp program, but merely serve as a lookup table.

You mean it would be built once and for all and then stay constant.

> Sorry I wasn't able to find any useful documentation (the manual is as
> terse as ever).

Which manual, what did you look for in it, what did you expect to find
and what did you find instead ?


        Stefan

Re: fastest data structure for a hash-like lookup

[Florian von Savigny]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2632 bytes --]


"Stefan Monnier" <monnier+gnu.emacs.help/news/@flint.cs.yale.edu> writes:

> What do the keys look like ?  Can you choose them freely ?

They are strings, more precisely, attribute values (ID tokens) taken
from SGML instances.

> In elisp, it seems you could use a hash table of lisp lists,
> vectors, or structures.  See `defstruct' in the CL manual for
> structure.

CL means "common lisp"?

> See `make-hash-table' in the elisp manual.

That seems to be Emacs 21, which I'm trying to do without.

> You mean it would be built once and for all and then stay constant.

Yes, the code will even written by another program and imported by
emacs via load-file.

> > Sorry I wasn't able to find any useful documentation (the manual is as
> > terse as ever).
> 
> Which manual, what did you look for in it, what did you expect to find
> and what did you find instead ?

I tried to find advice on nested data structures in the chapters about
Lisp data types, lists, and sequences, arrays and vectors. There is an
example of a nested alist under copy-alist, but I tried to find the
fastest such structure (and I doubted an alist was fast, since "keys"
are not unique there). There was no hint in the section about vectors
whether you could use them in such a way. After having played with
Kevin's kind proposal, I realise chapter 7 about symbols is very
relevant, but that's not where I thought to find anything.

I'm not criticizing the manual in saying it is terse (condensed, more
precisely). That makes it very clear when you try to find some detail
you've forgotten. What I sometimes miss, though, is something with a
"cookbook" approach: "I want to XY, how do I ...".

It is hard for me to say what I "found instead", since I haven't tried
to read in depth what apparently wouldn't help me further. It seems
entirely possible to me if I knew more about the BASIC NOTIONS of
Elisp, it would have been quite obvious that yes of course, why not,
structure X and structure Y can be combined, thus, sections that
seemed without a clue now would have been very helpful then. I suppose
I'm not a serious programmer in this sense; I only try to learn things
as far as I need them to produce something I can use (in other words,
I'm the type who uses Perl...). Imitating also saves a lot of time
compared to trying out.

I don't know whether that answers your questions adequately.


-- 


Florian v. Savigny

If you are going to reply in private, please be patient, as I only
check for mail something like once a week. - Si vous allez répondre
personellement, patientez s.v.p., car je ne lis les courriels
qu'environ une fois par semaine.

Re: fastest data structure for a hash-like lookup

[Stefan Monnier]

>> In elisp, it seems you could use a hash table of lisp lists,
>> vectors, or structures.  See `defstruct' in the CL manual for
>> structure.
> CL means "common lisp"?

C-h i m cl RET

CL is an elisp package that provides some of the functionality of
Common-Lisp, so no it's not Common-Lisp, but yet, it's got something to do
with it.

>> See `make-hash-table' in the elisp manual.
> That seems to be Emacs 21, which I'm trying to do without.

It's also available in Emacs-20 if you use CL (which internally uses
obarrays, then).

> I tried to find advice on nested data structures in the chapters about

All data structures can nest, just like in most languages.

> fastest such structure (and I doubted an alist was fast, since "keys"
> are not unique there). There was no hint in the section about vectors

Alists are pretty fast as long as they're not too long.


        Stefan