Looking for a More Efficient Method of Searching a List

[Steve Dyke]

In my app I create a list object of several thousand data base records. I do this because it is a static list of records and I just need it loaded into the app once.
In lieu of calling the data multiple times.

Within the app I loop thru the list for a match on a particular record.
I use the for(Object object: list) method.

Is there a more efficient way to search the list or a different list type object to store the data in for searching.

[Campbell Ritchie]

Can you organise the search on the database? Databases are heavily optimised for that sort of processing.
Can you predict what sort of feature you are searching on and put that feature as a “K” in a Map?
How long does it take to search a few thousand records?

[Junilu Lacar]

Programmers are notoriously bad at optimizing applications and are particularly bad at optimizing by gut feel. Do you have any objective measures that can justify loading all your data in memory versus just delegating the search task to the database which, as Campbell pointed out, is already optimized to do that kind of job?

If you don't have empirical measurements and you're just going off on "I think this will be more efficient" then your "improvements" are dubious at best.

[Steve Dyke]

Junilu Lacar wrote:Programmers are notoriously bad at optimizing applications and are particularly bad at optimizing by gut feel. Do you have any objective measures that can justify loading all your data in memory versus just delegating the search task to the database which, as Campbell pointed out, is already optimized to do that kind of job?

If you don't have empirical measurements and you're just going off on "I think this will be more efficient" then your "improvements" are dubious at best.

Just attempting to cut down on thousands of data connections per day. Loading this data into the object at app start only takes one connection.

[Junilu Lacar]

Do you have any data on how expensive these connections are? What exactly are you saving and how much? Do you have evidence that reducing the cost of making multiple connections will actually translate to $$$ or some kind of benefit to your users or your company? Have you explored other approaches, like maybe caching only the most frequent used queries? Again, what hard evidence are you basing this decision on? Frankly, it still sounds a lot like "gut-based optimization" to me.

[fred rosenberger]

You can spend days or week optimizing stuff, and in the end, you save the user 0.1 milliseconds (or whatever).  so users would have to run that millions of times before the cost is offset.  Is it really worth it?

and then let's not forget that in six months, or two years, someone will have to come back to that code and re-work it.  If your optimizations are "clever", the code becomes harder to understand and debug.

How efficient is efficient enough?  unless you have a documented target, you will never be done...someone can always ask for it to be faster.

Would you be better off spending money on faster computers/routers/other hardware?  

[Steve Dyke]

fred rosenberger wrote:You can spend days or week optimizing stuff, and in the end, you save the user 0.1 milliseconds (or whatever).  so users would have to run that millions of times before the cost is offset.  Is it really worth it?

and then let's not forget that in six months, or two years, someone will have to come back to that code and re-work it.  If your optimizations are "clever", the code becomes harder to understand and debug.

How efficient is efficient enough?  unless you have a documented target, you will never be done...someone can always ask for it to be faster.

Would you be better off spending money on faster computers/routers/other hardware?  

I understand all this. But I still look at doing what I can to minimize network traffic from the user front end to our back database server.
I will look at using a conventional connection to look for a match.
However, I sill would like to know if there is a way to check for an element in a List object without having to loop thru the list.

[Mike Simmons]

Steve Dyke wrote:I sill would like to know if there is a way to check for an element in a List object without having to loop thru the list.

Campbell suggested using a Map rather than a List... assuming you know an attribute that you can use as the key.  E.g. if you have a list of orders and you want to look them up by order number, put all the orders in a map using the order number as key.  Then you can use map.get(12345) to get the order number 12345.  Works great if you know the order number, and if there are few enough records that they can all fit into memory.  But if you then want to look up an order by something else... data, products number, address, whatever... then you will need to loop through all the records to see what matches.   Or make additional maps with other keys.

[salvin francis]

Mike Simmons wrote:... and if there are few enough records that they can all fit into memory...

OP did mention:

Steve Dyke wrote:... list object of several thousand data base records...

Which is why I think that the suggested DB approach might suit better and is scalable for this situation.
Additionally, if we are sure about the columns that are being searched, then, they can even be indexed by the database for faster searches.

[Steve Dyke]

salvin francis wrote:

Mike Simmons wrote:... and if there are few enough records that they can all fit into memory...

OP did mention:

Steve Dyke wrote:... list object of several thousand data base records...

Which is why I think that the suggested DB approach might suit better and is scalable for this situation.
Additionally, if we are sure about the columns that are being searched, then, they can even be indexed by the database for faster searches.

I have replaced the loop on the list with an sql call to the DB for the specific record.
In the past I did not have my connection pooling set up correctly so the connection overhead was causing a lot of issues.
With the connection pooling in place maybe the connection burden will be minimized.

Thanks for all the help.

[Mike Simmons]

salvin francis wrote:

Mike Simmons wrote:... and if there are few enough records that they can all fit into memory...

OP did mention:

Steve Dyke wrote:... list object of several thousand data base records...

Which is why I think that the suggested DB approach might suit better and is scalable for this situation.

Additionally, if we are sure about the columns that are being searched, then, they can even be indexed by the database for faster searches.

Absolutely.  I figured enough people had addressed the fact that using the database is probably better; I was just addressing ways to improve on looping through a list in Java.  Frankly, thousands of records in a Map does not sound like a big deal to me.  But it depends how big a record is, and what sort of platform you're running on, etc.  Certainly as you increase the size it won't scale as well as a database-based solution.

[Tim Holloway]

I once noted to a proud application developer that you couldn't collect all those saved nanoseconds in a jar and use them later. The only time optimization really is worth the often-vastly-greater expense of the extra programmer work and greater cost of maintenance is when resources are getting hammered so hard that even throwing more hardware at the problem isn't going to help. And hardware is really cheap these days, unlike programmers.

But a linear search of a list is a horribly inefficient way to search large data sets. Plus if you load up virtual memory with an entire database worth of data the paging overhead will at least equal the I/O required to actually deal with a database. In addition to the fact that the database can retrieve and update large sets of data more intelligently than brute-force RAM access will.

Databases commonly locate data via hashed and/or tree searches. Many of them dynamically balance their indexes for optimal performance. They have caches for frequently-referenced data.

And since they are often hosted on separate machines, all that work gets taken off of the application running as the database client.

Yes, that means network overhead, but it's smart network overhead. Only the data of immediate interest is dealt with. And if a large set of data requires processing, stored procedures on the DBMS server (which is often a beefed-up machine) can eliminate the network overhead in cases where it isn't economical. Plus you can further optimise client operations with client-side caches.

So, just to repeat what others here have said, before you spend a lot of time optimising something, first make sure it needs optimising, secondly, measure stuff to see what parts of the process need optimising, third, see if you can save work by using an off-the-shelf solution, and only then should you consider doing a lot of grunt work.

[Junilu Lacar]

Tim Holloway wrote:I once noted to a proud application developer that you couldn't collect all those saved nanoseconds in a jar and use them later.

If I had a nickel for every jar of nanoseconds that have ever been saved... I'd probably be down a few dollars.