From: "David G. Andersen" <dga@...>
Date: 2004-12-03T03:42:59+09:00
Subject: Re: ordered hash ?

On Fri, Dec 03, 2004 at 03:12:42AM +0900, itsme213 scribed:
> 
> "David G. Andersen" <dga@lcs.mit.edu> wrote in message
> > Brian's point is the right one to consider:  insertion order, in a
> > sense, is merely another key, one that's defined implicitly.
> 
> Sure, but then any operation that is sequence-sensitive (it modifies state)
> can be shoehorned into implicit ordering keys. This does not make it
> necessarily a good way to understand (i.e. model or specify) them, or to
> implement them, imho.

I repeat from my earlier message: 
"if you gained significant speed or ease of
implementation from using insertion order specifically."

A stack is simple to implement as a list -- much more simple than
a lookup tree -- and O(1) for push/pop operations.  A hash provides
O(1) key lookup instead of O(log n) key lookup.  So does an array.
These are obvious.

It gets a little less obvious when you start comparing the things
we were _actually_ talking about, which are considerably more
complex.

  a)  Multiple key ordered data structure
      +  General, can be used for arbitrary multiple key lookups
      -  O(log n) operations
  b)  Hash + doubly-linked list
      +  O(1) operations (_if_ you implement the list traversal right)
      -  Can only handle insertion order

In many cases, you might be using insertion order as a synonym
for time.  If you wanted at some later point to permit
the user to insert objects retroactively, you'd have to
move to an explicit representation.  (a)  would let you do that;
(b) would not.  

In an interpreted, high-level  language, I'd probably prefer to
have a good, solid implementation of (a), because it's more useful
to more people, and for the size of things we usually do in Ruby,
O(log n) operations in fast C for N in the thousands issn't too
much slower -- relative to the speed of the entire program running
in ruby -- as using an O(1) operation in C.

(The arguments above should not be construed as suggesting
that it should also replace general hash tables -- they're
more commonly used, and so benefit more from a little attention
to speed).

If this were in the kernel, it would usually be implemented the
other way.

  -Dave

-- 
work: dga@lcs.mit.edu                          me:  dga@pobox.com
      MIT Laboratory for Computer Science           http://www.angio.net/