TreeMap filtered view performance

Question

I have a class that has (among other things):

public class TimeSeries {
  private final NavigableMap<LocalDate, Double> prices;

  public TimeSeries() { prices = new TreeMap<>(); }

  private TimeSeries(NavigableMap<LocalDate, Double> prices) {
    this.prices = prices;
  }

  public void add(LocalDate date, double price) { prices.put(date, price); }

  public Set<LocalDate> dates() { return prices.keySet(); }

  //the 2 methods below are examples of why I need a TreeMap

  public double lastPriceAt(LocalDate date) {
    Map.Entry<LocalDate, Double> price = prices.floorEntry(date);
    return price.getValue(); //after some null checks
  }

  public TimeSeries between(LocalDate from, LocalDate to) {
    return new TimeSeries(this.prices.subMap(from, true, to, true));
  }
}

Now I need to have a "filtered" view on the map where only some of the dates are available. To that effect I have added the following method:

public TimeSeries onDates(Set<LocalDate> retainDates) {
  TimeSeries filtered = new TimeSeries(new TreeMap<> (this.prices));
  filtered.dates().retainAll(retainDates);
  return filtered;
}

The onDates method is a huge performance bottleneck, representing 85% of the processing time of the program. And since the program is running millions of simulations, that means hours spent in that method.

How could I improve the performance of that method?

Answer 1

I'd give ImmutableSortedMap a try, assuming you can use it. It's based on a sorted array rather then a balanced tree, so I guess its overhead is much smaller(*). For building it, you need to employ biziclop's idea as the builder supports no removals.

(*) There's a call to Collection.sort there, but it should be harmless as the collection is already sorted and TimSort is optimized for such a case.

---

In case your original map doesn't change after creating onDates, maybe a view could help. In case it does, you'd need some "persistent" map, which sounds rather complicated.

Maybe some hacky solution based on sorted arrays and binary search could be fastest, maybe you could even convert LocalDate first to int and then to double and put everything into a single interleaved double[] in order to save memory (and hopefully also time). You'd need your own binary search, but this is rather trivial.

---

The view idea is rather simple, assuming that

• you don't need all NavigableMap methods, but just a couple of methods
• the original map doesn't change
• only a few elements are missing in retainDates

An example method:

public double lastPriceAt(LocalDate date) {
    Map.Entry<LocalDate, Double> price = prices.floorEntry(date);
    while (!retainDates.contains(price.getKey()) {
        price = prices.lowerEntry(price.getKey()); // after some null checks
    }
    return price.getValue(); // after some null checks
}