[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: van Emde Boas hash.
From: |
tomas |
Subject: |
Re: van Emde Boas hash. |
Date: |
Mon, 23 Nov 2009 05:06:49 +0100 |
User-agent: |
Mutt/1.5.15+20070412 (2007-04-11) |
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On Fri, Nov 20, 2009 at 07:41:15AM +0100, A. Soare wrote:
>
> Van Emde Boas arrays are hashed arrays [...]
>
> For example, for an array of length 2^32, the complexity is O(0), and
> the number of steps is less than log_2 (32) = "maximum 5 steps" for every
> operation.
>
> The operations are:
>
> * insert a new number
> * delete a number
> * seek for a number
> * find the successor of a number
> * find the predecessor of a number
If I understood the Wikipedia page correctly (thnks, Deniz), you
can find "next" and "previous" to a number not in the hash? Then
they look like a good candidate to represent markers and boundaries of
overlays, no?
Regards
- -- tomás
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
iD8DBQFLCgpZBcgs9XrR2kYRAvh6AJ9TxH4v/4jFSN90gK/X/QHgJQuf/wCfUYYU
mZjOWuTH3spYQJWvZ3HtWzg=
=7Ccl
-----END PGP SIGNATURE-----