Java 8 : Optimal Way to Compute Min and Max in Large List

Question

I have the below code in which am computing Min and Max ordered items from list of Orders and works as expected. Am wondering if this can be refactored/improved any further to make it more optimal and performant to deal with thousands or orders list in prod.

I intentionally did not do Collections.min(itemFrequencyMap.values()) and Collections.max(itemFrequencyMap.values()) since it would require iteration of all values twice and then looping over itemFrequencyMap again to find entry with Min and Max value.

@Data
public class Order {
    private Long id;
    private String created_at, current_total_price, currency;
    Double total_price;     
    private List<Item> items;
}

@Data
public class Item {
private Long product_id;
String title, name, price;
}

@Data
public class ItemFrequency {
private Item item;
Long frequency;
}

public void minMaxItems(List<Order> orders) {       

    ItemFrequency minOrder = null;
    ItemFrequency maxOrder = null;
    Map<Item, Long> itemFrequencyMap = new TreeMap<>();
    orders.stream()
            .map(o -> o.getLine_items())
            .flatMap(List::stream)
            .forEach(Item -> {
                itemFrequencyMap.compute(Item, (k, v) -> v == null ? 1 : v + 1);
            });

    boolean isFirstEntry = true;
    Long max = Long.MIN_VALUE, min = Long.MAX_VALUE;
    for (Map.Entry<Item, Long> itemFrequency : itemFrequencyMap.entrySet()) {
        Item Item = itemFrequency.getKey();
        if (isFirstEntry) {
            max = itemFrequency.getValue();
            min = itemFrequency.getValue();
            isFirstEntry = false;
            continue;
        }
        if (itemFrequency.getValue() > max) {                
            max = itemFrequency.getValue();
            maxOrder = new ItemFrequency(Item,max);
        } else if (itemFrequency.getValue() < min) {                
            min = itemFrequency.getValue();
            minOrder = new ItemFrequency(Item,min);
        }
    }
    
}

What do you think about the answers here: https://stackoverflow.com/q/41816264/61158 — akarnokd, Jun 21 '22 at 15:36
"Thousands" isn't huge. Have you actually measured to determine whether a "simple" solution would be good enough? — Andy Turner, Jun 21 '22 at 15:38
By the way: `stream.collect(groupingBy(item -> item, counting()))` is a better way of counting items, and it directly returns the `Map`. — Andy Turner, Jun 21 '22 at 15:41
Note that data oriented design is particularly useful in Java since collections are slow (due to object inheritence, boxing, compaction and many things). See: https://stackoverflow.com/questions/1641580/what-is-data-oriented-design . But this generally requires to deeply redesign your application (better sooner because then there is not much to do when the application is huge and cache misses appear everywhere). — Jérôme Richard, Jun 21 '22 at 23:16

score 1 · Accepted Answer · answered Jul 19 '22 at 07:14

You can optimize your code to perform the min and max ordered items calculations at run-time that is as you add items in the different order. Please find below the sample code. Using this approach you can retrieve min and max ordered item in O(1) constant time.

import java.util.HashMap;
import java.util.List;
import java.util.Objects;

public class Test {
    private static HashMap<Item, Long> itemFrequencyMap = new HashMap<>();
    private static ItemFrequency minOrder;
    private static ItemFrequency maxOrder;


   public ItemFrequency getMinOrder() {
       return minOrder;
   }

   public ItemFrequency getMaxOrder() {
       return maxOrder;
   }

   public static class Item {
       private Long product_id;
       String title;
       String name;
       String price;

       @Override
       public boolean equals(Object o) {
           if (this == o) return true;
           if (!(o instanceof Item)) return false;
           Item item = (Item) o;
           return product_id.equals(item.product_id);
       }

       @Override
       public int hashCode() {
           return Objects.hash(product_id);
       }
   }

      public static class Order {
       private Long id;
       private String created_at, current_total_price, currency;
       private Double total_price;
       private List<Item> items;


       public List<Item> getItems() {
           return items;
       }

       public void addItem(Item item) {
           this.items.add(item);
           long frequency = itemFrequencyMap.getOrDefault(item, 0L) + 1;
           itemFrequencyMap.put(item, frequency);
           if (minOrder.frequency > frequency)
               minOrder = new ItemFrequency(item, frequency);

           if (maxOrder.frequency < frequency)
               maxOrder = new ItemFrequency(item, frequency);
       }
   }
   
   public static class ItemFrequency {
       private Item item;
       private Long frequency;
       public ItemFrequency(Item item, Long frequency) {
           this.item = item;
           this.frequency = frequency;
       }
   }
  }

Java 8 : Optimal Way to Compute Min and Max in Large List

1 Answers1