kcorey wrote:
On Tue, 2004-07-13 at 17:01, Nur wrote:
What would be the most efficient algorithm to use for an index file for an modifiable dictionary database (where words can be inserted or removed)? Factors to be considered: searching speed, addition/deletion speed, index file size etc. Algorithms to be considered: binary search tree, binary heap, ......... ?
It depends on a few things...are you going to sort on more than one
field, or is it strictly alphabetical? what's your most common access
type for the dictionary (lookup, insertion, deletion)?
I would presume a lookup function on an alphabetically (only) sorted database. In that case, there's no real need for an index per se, just sort the records of the database. Slow to insert, but fast to lookup, as if the database is in order, you could simply do a binary search on the database.
However, if inserts and deletes are done on a regular basis, you might want to lower the cost of insertion at the expense of making retrieval slower. (For this scenario, I'd imagine a separate index
If this works, you could speed up inserts and deletes by putting storing several words in one Palm record. Like if you could store a max of 100 words in one Palm record, start off w/ 50-70 or whatever depending on how much you want to insert and delete. Whatever your method, if you will be storing large numbers of words, you'll probably want to store more than one per Palm record.
/* * Matt Graham * Palm OS Developer * www.healthramp.com */
-- For information on using the Palm Developer Forums, or to unsubscribe, please see http://www.palmos.com/dev/support/forums/