Reorganizing inventory items into a data structure I'm currently refactoring some old code of mine that I had done a few years ago, where it takes in two Lists to compare their contents, and then return the mapped contents that were matched. With 750 items for potential needles, and over 25000 items as the haystack, the original code took about 22-25 seconds to process. After a bit of refactoring however I was able to reduce it to just over a second. Is there a way to improve it further?

Here's the original code


Map&lt;String, ArrayList&lt;TreeMap&lt;String, String&gt;&gt;&gt; map = new TreeMap&lt;String, ArrayList&lt;TreeMap&lt;String, String&gt;&gt;&gt;();

String charsToFilter = "[" + Pattern.quote("_-") + "]";

for (int i = 0 ; i &lt; baseDataArray.size() ; i++) {
  String currentProduct = baseDataArray.get(i).get("product_name").replaceAll(charsToFilter, "  ").toLowerCase();

  for (int j = 0 ; j &lt; inventoryArray.size() ; j++) {
      String currentListing = inventoryArray.get(j).get("title").replaceAll(charsToFilter, " ").toLowerCase();

      if (currentListing.contains(currentProduct)) {
          ArrayList&lt;TreeMap&lt;String, String&gt;&gt; currentListingArray = new ArrayList&lt;TreeMap&lt;String, String&gt;&gt;();
          TreeMap&lt;String, String&gt; currentListingMap = new TreeMap&lt;String, String&gt;();

          for (Map.Entry&lt;String, String&gt; keyValue : inventoryArray.get(j).entrySet()) {
              currentListingMap.put(keyValue.getKey(), keyValue.getValue());
          }

          currentListingArray.add(currentListingMap);

          if (map.get(currentProduct) == null) {                      
              map.put(currentProduct, currentListingArray);
          } else {
              map.get(currentProduct).add(currentListingMap);
          }
      }
  }
}

return map;



And here's the new code:

Map&lt;String, ArrayList&lt;TreeMap&lt;String, String&gt;&gt;&gt; map = new TreeMap&lt;String, ArrayList&lt;TreeMap&lt;String, String&gt;&gt;&gt;();

String charsToFilter = "[" + Pattern.quote("_-") + "]";

ArrayList&lt;String&gt; productNameArray = new ArrayList&lt;String&gt;();

for (Map&lt;String, String&gt; baseDataItem : baseDataArray) {
    productNameArray.add(baseDataItem.get("product_name")
      .replaceAll(charsToFilter, " ").toLowerCase());
}

for (Map&lt;String, String&gt; inventoryItem : inventoryArray) {

    //moving this to the for loop below increase execution time by 100%
    String processedInventoryItem = inventoryItem.get("title").replaceAll(charsToFilter, " ").toLowerCase();     


    for (String productName : productNameArray) {
        if (processedInventoryItem.contains(productName)) {
            ArrayList&lt;TreeMap&lt;String, String&gt;&gt; currentListingArray = new ArrayList&lt;TreeMap&lt;String, String&gt;&gt;();
            TreeMap&lt;String, String&gt; currentListingMap = new TreeMap&lt;String, String&gt;();

            for (Map.Entry&lt;String, String&gt; keyValue :  inventoryItem.entrySet()) {
                currentListingMap.put(keyValue.getKey(),  keyValue.getValue());
            }

            currentListingArray.add(currentListingMap);

            if (map.get(productName) == null) {                     
                map.put(productName, currentListingArray);
            } else {
                map.get(productName).add(currentListingMap);
            }

            break;
        }
    }
}

return map;


There's some differences such as going from for to foreach loops, but nothing that I can see that would make such a change. Anyone have any thoughts on how to improve it further, or why it has come so far already.
The first thing to note is that Java no longer requires the generic types to be specified in the declaration of the collections you have, so, for example, the code 


Map&lt;String, ArrayList&lt;TreeMap&lt;String, String&gt;&gt;&gt; map = new TreeMap&lt;String, ArrayList&lt;TreeMap&lt;String, String&gt;&gt;&gt;();



can be replaced with:

Map&lt;String, ArrayList&lt;TreeMap&lt;String, String&gt;&gt;&gt; map = new TreeMap&lt;&gt;();


That simplifies your line-lengths in a few places.

This is how I would simplify the code cosmetically:

Map&lt;String, ArrayList&lt;TreeMap&lt;String, String&gt;&gt;&gt; map = new TreeMap&lt;&gt;();
String charsToFilter = "[" + Pattern.quote("_-") + "]";
ArrayList&lt;String&gt; productNameArray = new ArrayList&lt;&gt;();

for (Map&lt;String, String&gt; baseDataItem : baseDataArray) {
    productNameArray.add(baseDataItem.get("product_name")
                    .replaceAll(charsToFilter, " ")
                    .toLowerCase());
}

for (Map&lt;String, String&gt; inventoryItem : inventoryArray) {
    //moving this to the for loop below increase execution time by 100%
    String processedInventoryItem = inventoryItem.get("title")
          .replaceAll(charsToFilter, " ")
          .toLowerCase();     

    for (String productName : productNameArray) {
        if (processedInventoryItem.contains(productName)) {
            ArrayList&lt;TreeMap&lt;String, String&gt;&gt; currentListingArray = new ArrayList&lt;&gt;();
            TreeMap&lt;String, String&gt; currentListingMap = new TreeMap&lt;&gt;();
            for (Map.Entry&lt;String, String&gt; keyValue :  inventoryItem.entrySet()) {
                currentListingMap.put(keyValue.getKey(),  keyValue.getValue());
            }

            currentListingArray.add(currentListingMap); 
            if (map.get(productName) == null) {                     
                map.put(productName, currentListingArray);
            } else {
                map.get(productName).add(currentListingMap);
            }

            break;
        }
    }
}
return map;


OK, that fits on a single screen, and is almost narrow-enough for StackExchange code blocks.

Right, now, what are you doing? You're iterating over the inventoryArray, and, for each inventoryItem, you check to see whether there's a baseDataArray member who's filtered name is part of the filtered inventoryItem's name.

You extract the processing of the baseDataArray names to a separate loop to prevent recalculating it often. That's a good idea. It would be better if you reused a single compiled Pattern:

Pattern charfilter = Pattern.compile("[" + Pattern.quote("_-") + "]");


Then, use that pattern in the loop, replacing the following


for (Map&lt;String, String&gt; baseDataItem : baseDataArray) {
    productNameArray.add(baseDataItem.get("product_name")
      .replaceAll(charsToFilter, " ").toLowerCase());
}



with:

for (Map&lt;String, String&gt; baseDataItem : baseDataArray) {
    productNameArray.add(charfilter.matcher(baseDataItem.get("product_name"))
      .replaceAll(" ").toLowerCase());
}


Similarly, inside the inventory loop, you can also do:

String processedInventoryItem = charfilter.matcher(inventoryItem.get("title")).replaceAll(" ").toLowerCase();


That should reuse the pattern more efficiently, and improve the replaceall time (though Java probably does a good job of detecting that misuse, and compiling it efficiently anyway.

There is a potential bug in your code, though, and it possibly accounts for the speed-up too.

In the original code, you check every inventory item against every product.

In the second code, you check each product against only the first inventory. You "break" the inner loop.

As a result, your "faster" code does not do a full join between the data sets, but only a partial one. This may or may not impact your results, but it will impact the performance.

As an aside, this code would look great in Java 8 with streams... do you have Java 8 available?