TreeMap的过滤视图性能

Question

我有了（除其他事项外）类：

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)); 
    } 
} 

现在我需要的地图，只有部分日期可在“过滤”的看法。该效果我已经添加了以下方法：

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

的onDates方法是一个巨大的性能瓶颈，代表的程序的处理时间的85％。由于该程序正在运行数百万次的模拟，这意味着花费数小时的时间。

我该如何提高该方法的性能？

Answer 1

我想给ImmutableSortedMap一个尝试，假设你可以使用它。它基于排序数组而非平衡树，所以我猜它的开销要小得多（*）。为了建造它，你需要使用biziclop的想法，因为建造者不支持清除。 （*）Collection.sort这里有一个电话，但它应该是无害的，因为收集已经排序，TimSort针对这种情况进行了优化。

---

如果你原来的地图生成onDates后不发生变化，也许一个视图可帮助。如果是这样，你需要一些“持久”的地图，这听起来相当复杂。

也许基于排序数组和二进制搜索一些哈克的解决方案可能是最快的，也许你甚至可以转换LocalDate先int再到double，把一切都变成一个单一的交错double[]为了节省内存（希望也时刻）。你需要自己的二进制搜索，但这是相当微不足道的。

---

的观点想法很简单，假设

• 你并不需要所有NavigableMap方法，但只是一对夫妇的方法
• 原始地图不改变
• retainDates

示例方法：

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 
} 

Answer 2

最简单的优化：

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; 
} 

节省您先创建地图的完整拷贝的成本，然后在副本迭代再次进行筛选。