1

I took one project and I'm getting really hard to continue. No comments, undocumented code, inconsistent naming variables ect.

But, at some point I expired slow execution of search. To be honest, I've never earlier expired slowness on mobile apps I developed because there wasn't much data to process.

Ok, there is a class A with following fields:

  • ID integer
  • Info 1 string
  • Info 2 string
  • ... string

During the session, Collection of class A is filling with new instances. At some point user ask for instance information selecting the instance ID (collection is not sorted by ID in any order). In average, there is about 2500 instances On some older devices it takes over long to find it. What is best practice to do this as fast as possible? (with time complexity explanation)

The genie who left me his code put it all in one collection and searched by linear search.

  1. Heapsort, so can search multiple times by binary search?
  2. Adding it in sorted order, then use binary search?
  3. Putting data in SQLite temp table (getting sense on more data) and search by query
  4. HashSet or TreeSet
  5. Something else..
fenix
  • 1,716
  • 2
  • 20
  • 26

3 Answers3

3

If you are searching a collection by key, you should generally use a HashMap, which finds items in the map based on their key in expected O(1) time.

If, however, the identifiers are numeric and consecutive (i.e. they go from 0 to 2500 with no gaps), you can use an ArrayList, where you can access an item by its index in O(1) time. If the identifier are numeric and consecutive, and in addition the number of items is bound, you don't need a Collection at all. An array would do.

Eran
  • 387,369
  • 54
  • 702
  • 768
  • First part of answer suits my case. What if I use spinner and 'name' string instead ID's showing in spinner? Could you suggest solution? – fenix Aug 10 '14 at 15:52
  • @StevanPopov One option is to have two HashMaps, one with the ID as key and the other with `name` as key. Another option is to have only one map with ID as key, and in the Spinner you would distinguish between the displayed value (name) and the actual value (ID) - I'm assuming such a distinction exists (I'm not familiar with Spinner class). When an item is selected, you search for it in the HashMap by its ID. – Eran Aug 10 '14 at 15:59
  • You mean http://stackoverflow.com/questions/1625249/android-how-to-bind-spinner-to-custom-object-list? Would we assume that custom adapter searchs objects efficiently? – fenix Aug 10 '14 at 16:47
  • @StevanPopov You're surely not going to show more than a few dozens items in the spinner, are you? For so few items, linear search is good enough. – maaartinus Aug 11 '14 at 05:34
  • @maaartinus I'd rather use two HashMaps instead letting my code search linear. Do you have some reference about getting other values of selected string (object) in spinner? You know its going to search linear? – fenix Aug 11 '14 at 12:50
0

I would say it depends on what kind of operations you need to do with this collection. If you are only searching elements by ID, an HashMap could be a good solution (constant-time complexity for all basic operations). If you need to sort the elements, you may prefer a TreeSet (O(log(n)) complexity for basic operations like add, find, remove etc but ordered data structure).

If you need to search on other criterias, you may consider using a database.

Dici
  • 25,226
  • 7
  • 41
  • 82
0

ArrayList and Vector in collection implements Random access interface which is best solution for search operations. You can use HashMap if you are using ID as keys

kittu
  • 6,662
  • 21
  • 91
  • 185