Skip to main content

Posts

When O(n+m) Isn't Fast Enough: A Java Optimization Adventure

Views: Loading...
My very first project at my current company was to migrate a system written in PHP to Java. There is one function that plays an important role in the system. It performs the following tasks: Given a sorted list A and a set B , both containing Strings. A and B are loaded from Redis and cached in memory. List A remains constant between requests, while set B changes. Find the intersection of A and B Create list C containing the intersecting items, ordered as they appear in A Append all remaining items from  B to C Return the reverse of C Here's the original Java implementation of the core logic: private static List<String> sortItems(List<String> sortedItemList, Set<String> items) { if (items == null || items.isEmpty()) { return Collections.emptyList(); } if (sortedItemList == null || sortedItemList.isEmpty()) { return new ArrayList<>(items); } // Find intersection, preserving order from sortedItemList List<Strin...