|
Home > Archive > Unix Programming > August 2005 > choosing the right data structure & algo for a dynamic lookup table
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
choosing the right data structure & algo for a dynamic lookup table
|
|
| jimjim 2005-08-11, 5:55 pm |
| Hello,
What factors should I take into consideration when choosing a data structure
and algorithm for a dynamic lookup table? Any pointers, pitfalls and
thoughts please?
TIA
| |
| John Gordon 2005-08-11, 5:55 pm |
| In <lAOKe.87031$G8.37102@text.news.blueyonder.co.uk> "jimjim" <netuser@blueyonder.co.uk> writes:
> Hello,
> What factors should I take into consideration when choosing a data structure
> and algorithm for a dynamic lookup table? Any pointers, pitfalls and
> thoughts please?
Key size
Relative frequency of lookups, inserts, deletes
Desired performance for lookups, inserts, deletes
Frequency of collisions
Data storage format (binary file, XML file, ??)
--
John Gordon "It's certainly uncontaminated by cheese."
gordon@panix.com
| |
| David Schwartz 2005-08-11, 5:55 pm |
|
"John Gordon" <gordon@panix.com> wrote in message
news:ddge0k$8fv$1@reader2.panix.com...
> In <lAOKe.87031$G8.37102@text.news.blueyonder.co.uk> "jimjim"
> <netuser@blueyonder.co.uk> writes:
[vbcol=seagreen]
[vbcol=seagreen]
> Key size
> Relative frequency of lookups, inserts, deletes
> Desired performance for lookups, inserts, deletes
> Frequency of collisions
> Data storage format (binary file, XML file, ??)
Also:
Relative importance of performance versus resource consumption.
Relative frequency of different types of lookups, if applicable.
It basically comes down to these questions:
1) What kind of data am I storing?
2) What kind of operations will I be performing on it and how often?
3) What am I trying to get out of this data structure? (Performance?
Ease of implementation? Maintainability? Low memory consumption? Minimal
disk access?)
There is no substitute for experience and keeping current with the
literature. 9 times out of 10, whatever data storage problem I'm dealing
with, someone spent 5 years studying it and came up with a solution that is
better than the one I could come up with in the time available (rarely 5
years).
If you don't know at least one of Lawson, Jenkins, or Matsumoto and
Kurita, you aren't a good programmer. They developed extremely good hash
sizing functions, hash value functions, and pseudo-random number generators
respectively.
DS
| |
| jimjim 2005-08-14, 5:55 pm |
| Thank you very much for the reply.
> If you don't know at least one of Lawson, Jenkins, or Matsumoto and
> Kurita, you aren't a good programmer. They developed extremely good hash
> sizing functions, hash value functions, and pseudo-random number
> generators respectively.
>
So, a hash table would be the solution to a dynamic lookup table problem.
The most suited kind of the data structure and algorithm would depend on the
factors you have just mentioned, right? Any good web resources on this topic
please?
TIA
|
|
|
|
|