Re: data structure question

Jack said:


Richard Heathfield wrote:
Jack said:

What is the best data structure for designing a telephone directory
which contains several millions items? WHat is spped of lookup? Thanks.

What do your lecture notes suggest?

Is hashing table the correct answer? Thanks.

Well, it wouldn't be a totally stupid answer, that's for sure.

The speed of lookup will depend on whether you can get a perfect hash for
your data, which is unlikely, I think, if you have millions of items. The
more buckets you have, the lower your collision rate, and the faster the
lookup.

Other possibilities include: B+-tree, trie.

As someone else said, the really right answer is "use a database", but your
teacher probably won't buy that.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
.

Relevant Pages

  • Re: data structure question
    ... Jack wrote: ... WHat is spped of lookup? ... What do your lecture notes suggest? ... Is hashing table the correct answer? ...
    (comp.programming)
  • Re: data structure question
    ... WHat is spped of lookup? ... What do your lecture notes suggest? ... Richard Heathfield ... rjh at above domain ...
    (comp.programming)
  • Re: data structure question
    ... Richard Heathfield wrote: ... WHat is spped of lookup? ... What do your lecture notes suggest? ... Is hashing table the correct answer? ...
    (comp.programming)
  • Re: Function pointers: performance penalty?
    ... Might be more convincing if you'd said strings -n 3 since the ... if you don't call it by name lookup (which is a weird way to do it ... Richard Heathfield ...
    (comp.lang.c)
  • Re: compile time vs. run time?
    ... lookup table and iteration as part of the same solution. ... Iteration is no better than if-else clauses in terms of performance. ... secondary storage, pre-hashing key values, etc. ... > faster than hashing. ...
    (comp.lang.cpp)