java - 具有 O(1) 时间和空间复杂度的股票统计计算

Question

我必须在 Java 中设计一个 rest API:-

接受带有以下 json 的 POST 请求:-
{
“仪器”:“ABC”，
“价格”:“200.90”，
“时间戳”:“2018-09-25T12:00:00”
}

这些记录将保存在内存集合中，而不是任何类型的数据库中。

会有一个 GET API 返回过去 60 秒内收到的特定仪器记录的统计信息。 GET 请求将是:-/statistics/{instrumentName} 例如:-/statistics/ABC。响应如下所述:-
{
“计数”:“3”
“分钟”:“100.00”
“最大”:“200.00”
“总和”:“450.00”
“平均”:“150.00”
}

将有另一个 GET 请求/statistics 返回过去 60 秒内收到的所有工具的统计信息(不特定于特定工具，如 #2)

使该算法难以实现的原因在于应该执行 GET 调用 - O(1) 时间和空间复杂度。
我为 3# 考虑的方法是拥有一个包含 60 个桶的集合(因为我们必须计算过去 60 秒，所以每 1 秒采样一次)。每次事务进入时，它都会根据键(即小时-分钟-秒)进入特定的存储桶(这将是带有此键的映射和该秒的统计信息)。
但我无法理解的是如何解决问题 2#，我们必须在 O(1) 时间和空间复杂度中获取最后 60 秒内特定仪器/statistics/ABC 的统计数据。
清理超过 60 秒的记录的最佳策略是什么？
对算法的任何帮助将不胜感激。

Answer 1

将数据存储在 Map<String, Instrument> 中，并让类看起来像这样:

class Instrument {
    private String name;
    private SortedMap<LocalDateTime, BigDecimal> prices;
    private BigDecimal minPrice;
    private BigDecimal maxPrice;
    private BigDecimal sumPrice;

    // Internal helper method
    private void cleanup() {
        LocalDateTime expireTime = LocalDateTime.now().minusSeconds(60);
        Map<LocalDateTime, BigDecimal> expiredPrices = this.prices.headMap(expireTime);
        for (BigDecimal expiredPrice : expiredPrices.values()) {
            if (this.minPrice.compareTo(expiredPrice) == 0)
                this.minPrice = null;
            if (this.maxPrice.compareTo(expiredPrice) == 0)
                this.maxPrice = null;
            this.sumPrice = this.sumPrice.subtract(expiredPrice);
        }
        expiredPrices.clear(); // Removes expired prices from this.prices
        if (this.minPrice == null && ! this.prices.isEmpty())
            this.minPrice = this.prices.values().stream().min(Comparator.naturalOrder()).get();
        if (this.maxPrice == null && ! this.prices.isEmpty())
            this.maxPrice = this.prices.values().stream().max(Comparator.naturalOrder()).get();
    }

    // other code
}

Instrument 的所有公共(public)方法必须是 synchronized并且必须从调用 cleanup() 开始, 因为时间已经过去了任何以前的电话。 addPrice(LocalDateTime, BigDecimal)方法当然必须更新 3 个统计字段。
为确保统计信息同步，最好使用 Statistics可以用作返回值的类，因此所有 4 个主要统计值(包括从 count 获得的 this.prices.size())代表同一组价格。