CODEWITHSUNDEEP
javaandroid
Malabarba
Malabarba

Reputation: 4553

How store a big list of strings to optimize both initialization time and search speed

I'm writing an android application which stores a set of ~50.000 strings, and I need input on how to best store them.

My objective is to be able to query with low latency for a list of strings matching a pattern (like Hello W* or *m Aliv*), but avoid a huge initialization time.

I thought of the following 2 ways:

  1. A java collection. I imagine a java collection should be quick to search, but given that it's fairly large I'm afraid it might have a big impact on the app initialization time.
  2. A table in a SQLite database. I imagine this would go easy on initialization time (since it doesn't need to be loaded to memory), but I'm afraid the query would impose some relevant latency since it needs to start a SQLite process (or doesn't it?).

Are my "imagine"s correct or horribly wrong? Which way would be best?

Upvotes: 1

Views: 241

Answers (4)

sergej shafarenka
sergej shafarenka

Reputation: 20426

I would definitely stick to SQLite. It's really fast in the both initialization and querying. SQLite runs in application process, thus there is almost no time penalties on initialization. A query is normally fired in a background thread to not block main thread. It will be very fast on 50.000 records and you won't load all data in memory, which is also important.

Upvotes: 1

Alberto
Alberto

Reputation: 975

If you want quick (as in instant) search times, what you need is a full-text index of your strings. Fortunately, SQLite has some full-text search support with the FTS extension. SQLite is part of the Android APIs and the initialisation time is totally negligible. What you you do have to watch is that the index (the .sqlite file) has to either be shipped with your app in the .apk, or be re-created the first time it opens (and that can take quite some time)

Upvotes: 5

CodingRat
CodingRat

Reputation: 1944

your string no are 50 in this case you can use java collection database will be time taking.

Upvotes: -1

Dale Wilson
Dale Wilson

Reputation: 9434

Look at data structures like a patricia trie (http://en.wikipedia.org/wiki/Radix_tree) or a Ternary Search Tree (http://en.wikipedia.org/wiki/Ternary_search_tree). They will dramatically reduce your search time and depending on the amount of overlap in your strings may actually reduce the memory requirements. The Java collections are good for many purposes but are not optimal for large sets of short strings.

Upvotes: 1

Related Questions