0

I am currently working on an android game that revolves around words. There is a database in the background that contains the words along with an integer and 2 more substrings, containing approximately 300000 rows. I load the words on starting the game into an ArrayList of Word objects(populating from the database). Currently I am using sequential search.

My question is this: Given that I have to search the list by different criteria, for example by definition(like book) or integer(which is a description of the word), and that I have to make many searches during the lifetime of the game(and only searches, so no inserts etc.), what is the most efficient way to search this list by different criteria without creating another list, as we have to save memory space given that this is an android game?

I was thinking about using binary search, but I'm lost on the criteria part and my only solution is to create 2 lists since I need to search by name and by the integer description at different times unrelated to each other.

Thanks in advance.

EDIT: database entry example

word | integer | string | string
--------------------------------
book |    2    |   xd   |   xp
Vincent van der Weele
  • 12,927
  • 1
  • 33
  • 61
EldarGranulo
  • 1,575
  • 1
  • 14
  • 37
  • is the List ordered by the criteria you are looking for? – Blackbelt Oct 07 '14 at 09:35
  • I thought about sorting it first by integer and right after to sort it by the name(definition), as in alphabetically. – EldarGranulo Oct 07 '14 at 09:37
  • still is always a List, so the complexity is always `O(n)` – Blackbelt Oct 07 '14 at 09:39
  • Please give examples of your database entries. Just to make it more clear – SME_Dev Oct 07 '14 at 09:40
  • I explained about possibly using binary search near the end of the question, advice? – EldarGranulo Oct 07 '14 at 09:41
  • @mts First sort the list, then use BinarySearch. The Collection.sort() and Collection.binarySearch() would do the job. There's no better way than this. – Alboz Oct 07 '14 at 09:46
  • possible duplicate http://stackoverflow.com/questions/5187888/java-searching-within-a-list-of-objects – Martin Frank Oct 07 '14 at 09:48
  • @Alboz. That's only correct, if he stays with a "stupid" datastructure like array or list. However, if he changes the datastructure, there is better perfomance possible (iam thinking of a tree or Hashmap, but yet iam undecided, what to go for in an answer). – SME_Dev Oct 07 '14 at 09:49
  • If you have a database, why don't you query it directly? That's what databases are for, right? Your objects are simple, so you can just instantiate them whenever you need them. – Vincent van der Weele Oct 07 '14 at 09:55
  • I am trying reduce the number of times I access the database as it is expensive on Android – EldarGranulo Oct 07 '14 at 10:09
  • I think the best solution would be a Hashtable. In that case you have to write a good hashCode() method for your Word objects. To do so, there are a few requirements, that need to be determined first: A) What attribute will be most frequently search for/with ? B) How unique is each word/integer/string ? C) Are the values related to each other (for example "book" MUST ALWAYS have "2")? – SME_Dev Oct 07 '14 at 10:31
  • Only the word part is unique, others have repeating values between records; and words and integers are strictly connected as are the other 2 strings(with the word) – EldarGranulo Oct 07 '14 at 10:43
  • @Matsura have you tried trie tree? Its most efficient while dealing with searching for words. Example is availabe [here](https://gist.github.com/prettymuchbryce/3719435) – Sagar Mar 30 '18 at 01:02

0 Answers0