Re: [Q] Unrelated to scotty, but . . .(Router Discovery cont.)

Cary B. O'Brien (cobrien@access.digex.net)
Tue, 24 Jun 1997 00:09:17 -0400 (EDT)

> I know this question is unrelated to scotty, but the people on this mailing
> list tend to be quite a bit more informative that the people on the tcl
> newsgroup. Anyways, I was hoping somebody could point me in the direction of
> some information about arrays and hash tables. Basically, I need some type
> of container (array, hash table, etc) that meets the following criteria:
>
> - Fast lookup of whether an element exists (searching through a list for it
> is not acceptable)
> - The ability to hold from 10,000 to 100,000 or more elements, and their values
> - The ability to add elements at a reasonable rate (searching through a list
> of 50,000 elements, looking for the correct place to put this one is
> unacceptable)
>
> I was hoping that the tcl array functionality was implemented as some sort
> of hash table or similar structure, so that it could meet my needs.
> Unfortunately, I don't know where I can look to find out if such is true. If
> not, I'd also be interested in any other such structures that might be in
> tcl or any of the following extensions:
>
> - itcl
> - Tclx
> - expect
> - tclbin
>
> For those of you who have been folowing my posts, this is in relationship to
> the router discovery program I am writing. The container I am looking for is
> to hold a list of every interface IP address, and the router it belongs to.
> In doing so, whenever I run accross a next hop, I can check it against the
> list, to see if I know what router the new ip address belongs to.
>
> Thanks in advance for any help,
> Robert Seeger

As has already been observed, TCL Arrays are implemented as hash tables,
and it is a quite good implementation. I've done tests with 10K elements
with reasonably good results. This may suit your needs.

One drawback with TCL arrays is if you need persistance -- there is no
way to store the hash table intact to disk and get it back. Array
set/array get will do the job at the cost of reimplementing the hash table
in memory each time it is read in. This might be fine -- test it first.

The next step up would be dbm/gdbm hash table files. Perl has the
nice feature of associating(!) an associative array with a gdbm disk
file, providing much of the speed of an in-memory hash with persistance.
A TCL interface to gdbm should be available. The berkeley db library
has both hash and btree storage, should you need an ordered traverse.

The next step would be an RDBMS like m(y)sql or postgres. I'm not sure
about m(y)sql, but postgres proports to provide both b-tree and hashed
indexes.

There are a lot of possible solutions. My suggestion would be to
first determine exactly what the performance targets are, and then
mock something up with each of the possible choices and see who
wins. Nothing like rapid prototyping to figure out what is really
going on.

Let us know how things turn out.

-- cary
cobrien@access.digex.net

--
!! This message is brought to you via the `tkined & scotty' mailing list.
!! Please do not reply to this message to unsubscribe. To subscribe or
!! unsubscribe, send a mail message to <tkined-request@ibr.cs.tu-bs.de>.
!! See http://wwwsnmp.cs.utwente.nl/~schoenw/scotty/ for more information.