Effectiveness of viewing TreeMap filters
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. For this, I 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 method onDates
is a huge performance bottleneck, accounting for 85% of the program processing time. And since there are millions of simulations involved in the program, that means hours spent on this method.
How can I improve the performance of this method?
source to share
I would give a ImmutableSortedMap
try, assuming you can use it. It is based on a sorted array, not a balanced tree, so I think its overhead is much less (*). You need to use the biziclop idea to create it as the builder does not support deletion.
(*) There is a call Collection.sort
, but it should be harmless as the collection is already sorted and TimSort
optimized for such a case.
If your original map doesn't change after creation onDates
, maybe a view can help. In case this is the case, you will need some "permanent" card, which sounds rather complicated.
Perhaps some hacky solution based on sorted arrays and binary search might be the fastest, perhaps you can even convert LocalDate
first to int
and then to double
and put everything in one interleaved double[]
to save memory (and hopefully also time ). You will need your own binary search, but this is pretty trivial.
The idea behind the presentation is quite simple, assuming that
- You don't need all methods
NavigableMap
, but just a few methods - the original map does not change
- in
retainDates
missing only a few elements.
Method example:
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
}
source to share
Simplest optimization:
public TimeSeries onDates(Set<LocalDate> retainDates) {
TreeMap<LocalDate, Double> filteredPrices = new TreeMap<>();
for (Entry<LocalDate, Double> entry : prices.entrySet() ) {
if (retainDates.contains( entry.getKey() ) ) {
filteredPrices.put( entry.getKey(), entry.getValue() );
}
}
TimeSeries filtered = new TimeSeries( filteredPrices );
return filtered;
}
It saves the cost of creating a complete copy of your map first, and then repeats the copy again for filtering.
source to share