Reorganizing inventory items into a data structure

Question

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<String, ArrayList<TreeMap<String, String>>> map = new TreeMap<String, ArrayList<TreeMap<String, String>>>();

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

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

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

      if (currentListing.contains(currentProduct)) {
          ArrayList<TreeMap<String, String>> currentListingArray = new ArrayList<TreeMap<String, String>>();
          TreeMap<String, String> currentListingMap = new TreeMap<String, String>();

          for (Map.Entry<String, String> 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<String, ArrayList<TreeMap<String, String>>> map = new TreeMap<String, ArrayList<TreeMap<String, String>>>();

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

ArrayList<String> productNameArray = new ArrayList<String>();

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

for (Map<String, String> 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<TreeMap<String, String>> currentListingArray = new ArrayList<TreeMap<String, String>>();
            TreeMap<String, String> currentListingMap = new TreeMap<String, String>();

            for (Map.Entry<String, String> 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.

Answer 1

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<String, ArrayList<TreeMap<String, String>>> map = new TreeMap<String, ArrayList<TreeMap<String, String>>>();

can be replaced with:

Map<String, ArrayList<TreeMap<String, String>>> map = new TreeMap<>();

That simplifies your line-lengths in a few places.

This is how I would simplify the code cosmetically:

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

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

for (Map<String, String> 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<TreeMap<String, String>> currentListingArray = new ArrayList<>();
            TreeMap<String, String> currentListingMap = new TreeMap<>();
            for (Map.Entry<String, String> 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<String, String> baseDataItem : baseDataArray) {
    productNameArray.add(baseDataItem.get("product_name")
      .replaceAll(charsToFilter, " ").toLowerCase());
}

with:

for (Map<String, String> 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?

Answer 2

Adding onto @rolfl's excellent answer, you can slightly tweak the type of map to: Map<String, List<TreeMap<String, String>>>. I suppose you need the concrete TreeMap type for its specific methods, but you can certainly change ArrayList to just List.

As for Java 8 yes I do have that, indeed I used it as the JDK for this project when iI moved it from the previous codebase. - canadiancreed

Well, that simplifies some things... For example, your first loop can become:

// BTW, baseDataArray is not a great name for a Collection instance
List<String> productNameArray = baseDataArray.stream()
                                .map(baseDataItem -> baseDataItem.get("product_name"))
                                .map(ThisClass::normalize)
                                .collect(Collectors.toList());

We use map() twice - once to extract the product name, and the second to normalize it using the placeholder ThisClass.normalize(String) method reference (replace ThisClass with your actual class name). Since this normalization is done twice - and you'll want to do it consistently - it's better off as its own method. A possible implementation will be:

private static String normalize(String value) {
    // assuming charsToFilter has been made static too
    return value.replaceAll(charsToFilter, " ").toLowerCase();
}

After the mappings, you simply collect() it into the desired List. Actually, productNameArray isn't such a great name for a List (too, see above), and in fact if you are expecting unique names, you can try using a Set (using Collectors.toSet()) instead.

With the normalize() method in hand, you can use it below too:

String processedInventoryItem = normalize(inventoryItem.get("title"));

I'm also not too sure why do you need the explicit for-loop below, since there is a TreeMap constructor that can copy entries from an existing Map to itself:

TreeMap<String, String> currentListingMap = new TreeMap<>(inventoryItem);
/*
for (Map.Entry<String, String> keyValue :  inventoryItem.entrySet()) {
    currentListingMap.put(keyValue.getKey(),  keyValue.getValue());
}
*/

Finally, Java 8 carries over the once-specific putIfAbsent() method from ConcurrentHashMap to all Map implementations, so you do something similar to the following:

map.putIfAbsent(productName, new ArrayList<>());
map.get(productName).add(currentListingMap);

edit: as suggested by @rolfl:

map.computeIfAbsent(productName, ArrayList::new).add(currentListingMap);

computeIfAbsent() returns the current value if it already exists, else it creates a new ArrayList in this case and returns that. Afterwards it's just a matter of chaining add().

And yes, this means you do not need to create currentListingArray anymore.

One more thing: Sure, you can consider turning your second loop into a Stream-based process too, but I'll leave that as an exercise to the discerning concerned reader (it can be much, much simpler)... ;)

Answer 3

I have a possible explanation for your performance improvement between the 2 versions of your code and it is due to the change from the for to foreach loops.

In your code snippets you don't specify what the types of the baseDataArray and inventoryArray variables are except that they are Lists of some sort.

If these variables are LinkedLists or some other form of AbstractSequentialList then the .get(i) operations on those data structures are \$O(n)\$ to the size of the list. This is because each .get(i) call has to iterate through the data elements from the start (or end) of the list in order to retrieve the correct item.

Since you have 2 nested loops this gives you \$O(n^2)\$ performance.

Changing from for to foreach changes the loops to use an iterator, which is an \$O(1)\$ operation to retrieve each item.

Answer 4

The code

ArrayList<TreeMap<String, String>> currentListingArray = new ArrayList<TreeMap<String, String>>();
...
currentListingArray.add(currentListingMap);

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

Can be replaced by

map.computeIfAbsent(productName, v -> new ArrayList<>()).add(currentListingMap);

In addition to being more concise, the currentListingArray is created only when it is actually needed.