Win a copy of Testing JavaScript Applications this week in the HTML Pages with CSS and JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Liutauras Vilda
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • fred rosenberger
  • salvin francis
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Carey Brown

What is the best collection for searching?

 
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.
 
Marshal
Posts: 69884
278
  • 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.
 
Sheriff
Posts: 7108
184
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • 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: 69884
278
  • 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.
 
Creativity is allowing yourself to make mistakes; art is knowing which ones to keep. Keep this tiny ad:
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
    Bookmark Topic Watch Topic
  • New Topic