Fastest way to find String in List in Java

Question

I want to use the fastest possible method to match a String with a String in List.

Im iterating trough a list to match productname and set price for that product.

Im trying to match every 400 000 items by name in another list where i could find the price, that list also contains 400 000 items.

Doing a "contains()" on String to match 400 000 items 400 000 times takes a long time to finish. I did also try startsWith() as i dont search by substring, im using the String because there is for sure a full match in the second list. It just has to be a faster way to find a match in the inner for loop to get the price?

ProductData t = null;
for (int i = 0; i < ParseCSV.products.size(); i++) {  // List of 400K+ items
        t = ParseCSV.products.get(i);

        for (int j = 0; j < ParseCSVprice.productPrice.size(); j++) {  // another List of 400K+ items
        if (ParseCSVprice.productPrice.get(i).getpairID()
                .contains(t.pairID)) {

            t.price = ParseCSVprice.productPrice.get(i).getPrice();
        }

    }

In the end, it means you're implementing the `contains` method. Use a different [string matching algorithm](http://en.wikipedia.org/wiki/String_searching_algorithm) and test it if its faster than `String#contains`. — Luiggi Mendoza, Mar 04 '14 at 21:27
You should search on the keywords *preprocessing* and *Hashmap*, that might help you a lot. — skiwi, Mar 04 '14 at 21:27
Do you understand order of complexity? What you are trying to do is n^2 time, or n*m time. Perhaps having your data better organized would be a better solution. — Pete B., Mar 04 '14 at 21:28
What does `getpairID()` return? A `String`, or something else? — Richard Fearn, Mar 04 '14 at 21:31

score 0 · Answer 1 · answered Mar 04 '14 at 21:27

0

You need to use another structure probably.
Possibly a HashMap or a HashSet.
There's no much faster way by using a List.
Searching in a List is O(N).

answered Mar 04 '14 at 21:27

peter.petrov

38,363
16
94
159

Using a `Map` in this case won't help because the String to find could be a substring of the Strings in the collection. – Luiggi Mendoza Mar 04 '14 at 21:29
Actually in this case im searching by the whole String in the list no substring. Do you think a Map can help? – rainbowpol Mar 04 '14 at 21:42
2

Yes, definitely. Searching in a HashMap is theoretically O(1) no matter of the size N of the HashMap. – peter.petrov Mar 04 '14 at 21:48

Jamie Holdstock · Answer 2 · 2014-03-04T21:49:45.153

0

If you only expect one or zero matches, you can increase the speed of your code in some cases by stopping your loops using the break keyword after you have found the match.

Also you might consider changing your id fields to contain numeric values which would be faster to compare than strings.

Because you are having to call a method on each object in the List in order to make the comparison, there isn't much else you can do to speed this up

edited Mar 04 '14 at 21:49

answered Mar 04 '14 at 21:43

Jamie Holdstock

166
1
11

I absolutely should break; how could i miss that! :) That could in best case make it finish a lot faster. Half the time maybe. I will try this. I can´t change the fields, i get those values from other systems. – rainbowpol Mar 04 '14 at 21:48
The break keyword in this case made it finish in 49% of the time it took before :) – rainbowpol Mar 04 '14 at 21:52
See [this answer](http://stackoverflow.com/a/886979/1428338) for a great example of how to break out of both loops with only one break statement from inside your if statement. If you weren't doing that before it may be even faster – Jamie Holdstock Mar 04 '14 at 21:53

Fastest way to find String in List in Java

2 Answers2