Three points.
1) Building the searching functionality twice is far more expensive than
building it once, no matter what approach you use. Be sure that the
performance of the DB approach is acceptable before you go and build it
that way.
2) It can be quite challenging to get decent performance out of a
database for something like this, depending on the functionality
required. If, for example, you need real-time narrowing down of words, a
database is going to be very slow (e.g. as you type letters, you get an
alphabetized list of what's in the db).
3) There's probably an open source Trie out there somewhere that you can
just use.
Directed at the OP, of course.
Cheers...
On 12/20/2011 5:43 PM, Kristopher Micinski wrote:
On Tue, Dec 20, 2011 at 4:10 AM, martypantsROK<[email protected]> wrote:
Don't forget there are more than data structures involved here.
The method searching could be improved. As Jim suggested, breaking
things down with an index (search for zulu beginning in the z section)
could be sped up even more. Search for the last letter in the string
first. By searching for that 4th character "u" first you've
eliminated
3 other characters and can skip on to the next word. That way,
similar
words like zuch or zucchini won't slow you down matching the first two
characters. Works even better for longer words.
Marty
I guess my point in all of this is that this searching is highly tied
to your data structure. Good algorithms only work with good data
structures to back them. And there are many indexing and optimization
techniques you can use to get more efficiency. My point is, that
since you can argue all day over these things getting more and more
complicated data structures and searching algorithms (each becoming
more and more context dependent), most of the time for this
application using a database will suffice. If you use a database,
whose indexing method is already going to be pretty good, and find it
doesn't suit your needs, *then* you can switch over to using something
fancier, though I highly doubt you'd need anything much fancier than a
trie in this case.
SQLite is using B+ trees for tables, while this isn't *amazing*
(especially compared to what you'll see with a trie), it's still going
to be massively better (where massively = logarithmic), than just
linear search. Along with this, it looks like "Solutin 9420" shared
his advice... And don't forget about the bloom filter, (this won't
actually help you that much unless you're doing a bunch of queries in
a row, most of which might not be int he database, but I wanted to
bring it up again anyway..)
kris
--
You received this message because you are subscribed to the Google
Groups "Android Developers" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/android-developers?hl=en
