Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

What is the best collection for searching?  RSS feed

 
Montana Burr
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What I want to do is create a collection of objects from which I can select one that meets a certain predicate.  For example, I need a collection of Person objects, and the primary function of the program involves picking the one whose name is "Mario Andretti".

For my personal use, I expect no more than 30 items in this collection.
 
Campbell Ritchie
Marshal
Posts: 55678
161
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You should not start worrying about searching thirty objects; even the most inefficient search will run quickly for so few. Once you have 30000000 objects, then you will find out  whether your search algorithm is working correctly.
What do you know about search algorithms? Do you know which run in constant time, which in logarithmic time, which in linear time and which in quadratic time?
You should consider the following factors before searching:-
How often and you are going to run the search? How often are you going to add things to your collection? How long will it take to sort it?
Have you been through the Java™ Tutorials about collections? That might tell you something about searching.
 
Montana Burr
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:You should not start worrying about searching thirty objects; even the most inefficient search will run quickly for so few. Once you have 30000000 objects, then you will find out  whether your search algorithm is working correctly.
What do you know about search algorithms? Do you know which run in constant time, which in logarithmic time, which in linear time and which in quadratic time?
You should consider the following factors before searching:-
How often and you are going to run the search? How often are you going to add things to your collection? How long will it take to sort it?
Have you been through the Java™ Tutorials about collections? That might tell you something about searching.

I don't know too many search algorithms. The only algorithms I used are linear searching and binary searching.
The search will be run at the user's request.
I expect that items will be added infrequently. I want the searching to be performed as quickly as noticable.
Considering my particular use case, I'm considering using a Map with each object's name being the associated key.
One of the tutorials to which you linked mentioned streams, which have a filtering function that I was looking at earlier. Supposedly, I can create a Collection of any subtype, generate a stream by invoking the collection's stream() function, then proceed to run a filter. However, none of the Collection objects I tried (ArrayList & something else) had a stream() function, but perhaps this is because I'm using Android SDK 4.4.
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One of the tutorials to which you linked mentioned streams, which have a filtering function that I was looking at earlier. Supposedly, I can create a Collection of any subtype, generate a stream by invoking the collection's stream() function, then proceed to run a filter. However, none of the Collection objects I tried (ArrayList & something else) had a stream() function, but perhaps this is because I'm using Android SDK 4.4. 

Streams would be perfect for you, but unfortunately, it looks like Android does not implement all of Java 8's features.
 
Campbell Ritchie
Marshal
Posts: 55678
161
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Montana Burr wrote:. . . I don't know too many search algorithms. The only algorithms I used are linear searching and binary searching.
That suggests you know enough (); just about every real‑life search uses binary search or linear search. Remember that Lists implement an indexOf method, which probably does a linear search and returns the index of the item sought (or −1 if it was not found). Remember that method requires a correct overriding of the equals() method in the object sought. Also remember that you will not notice the duration of a search for a few score elements in the collection. You need collections containing millions of items to test performance.
. . . Considering my particular use case, I'm considering using a Map with each object's name being the associated key.
A Map is not actually a Collection. It works slightly differently. You “put” a pair of Key and Value, and you do not usually search a Map. You use “get”, which requires the key be provided, but runs in constant time. That means it is no faster to find a K‑V pair in a 2 element Map than a 200000000 element Map. You can read about Maps in the tutorials link I gave you yesterday. If your objects are suitable for putting into a Map, both the put operation and the get operation run in constant time (put may run in amortised constant time), and that is fast. Very fast. You can run get on a 20000000 element Map just as fast as on a 2 element Map.
Beware: the keys should be immutable (String is a common immutable choice); if the key changes its state and therefore its hash code, it may become impossible to find it again in the Map.
One of the tutorials to which you linked mentioned streams, which have a filtering function that I was looking at earlier. Supposedly, I can create a Collection of any subtype, generate a stream by invoking the collection's stream() function, then proceed to run a filter. However, none of the Collection objects I tried (ArrayList & something else) had a stream() function, but perhaps this is because I'm using Android SDK 4.4.
I suspect that the filter method runs in linear time, like linear search. There is a difference between filter and indexOf. The indexOf method returns the index at which the object was found. The filter method returns a Stream containing all elements for which the appropriate Predicate returns true.That will produce a List containing everybody called Ritchie; that can have any number of elements, depending how many were found. 1000000 elements if there are a million Ritchies, and if you have the good fortune to inhabit a Ritchieless world, a 0‑element List. If there are no Ritchies, you will get −1, otherwise one index number.

I didn't know you were using Android, which is rather different from ordinary Java®; the stream() method has been available in ordinary Java® since March two years ago.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!