执行 Java 代码即可在 O(1) 内获得结果

Question

我有一个网络服务，我可以从中获取时间和价格。我已将这些记录保存在 ConcurrentHashMap 中，因为它需要支持以时间戳 (LocalDateTime) 作为键、以价格 (BigDecimal) 作为值的多线程环境。要求是获取以下详细信息

1. 最近 90 条记录中的总记录
2. 最近 90 条记录的平均记录
3. 过去 90 条记录中的最低价格
4. 过去 90 条记录中的最高价格
5. 最近 90 条记录的总价格
6. 最近 90 条记录的平均价格

我已经通过下面的代码成功实现了要求

ConcurrentHashMap<LocalDateTime, BigDecimal> data = // my full records

int totalRecords = 0;
BigDecimal highestPrice = new BigDecimal(0.0);
BigDecimal lowestPrice = new BigDecimal(0.0);
BigDecimal totalPriceSum = new BigDecimal(0.0);
Instant currentTime = Instant.now();
Duration limit = Duration.ofSeconds(90);
for (LocalDateTime time : data.keySet()) {
    Duration duration = Duration.between(currentTime , time);
    Boolean matches = ( duration.compareTo(limit) < 0 );
    if(matches) 
    {
        BigDecimal recordPrice = data.get(time);
        if(recordPrice.compareTo(lowestPrice) < 0) {
            lowestPrice = recordPrice;
        }

        if(recordPrice.compareTo(lowestPrice) > 0) {
            highestPrice = recordPrice;
        }
        totalPriceSum = totalPriceSum.add(recordPrice);
        totalRecords++;
    }
}


System.out.println("Total records in last 90 records: "+ totalRecords);
System.out.println("Average records in last 90 records: "+ (totalRecords/90)*100);
System.out.println("Lowest Price in last 90 records: "+ lowestPrice);
System.out.println("Highest Price in last 90 records: "+ highestPrice);
System.out.println("Total Price in last 90 records: "+ totalPriceSum);
System.out.println("Average Price in last 90 records: "+ (totalPriceSum.doubleValue()/90)*100);

但是我的客户说这存在一些性能问题，代码应该运行并在 O(1) 内完成

任何人都可以帮助我或建议我采用不同的方法来实现这一目标。我是否应该使用集合来实现 O(1)

Answer 1

来自评论 - 这是我关于计算要使用的确切键的含义的示例。它仍然使用 LocalDateTime(而不是纳秒的 Long)作为键，但它被截断为秒。所以最多需要收集90把 key 。

有一个聚合 PriceRequest 类来保存同一秒内的并发请求。 (它不是完全线程安全的。)

public class Last90Seconds {
    private Map<LocalDateTime, PriceRequest> priceRequests = new ConcurrentHashMap<>();

    public static void main(String[] args) throws Exception {
        Last90Seconds app = new Last90Seconds();
        app.simulatePriceRequests();  // thread which continuously simulates a price request

        for (int i = 0; i < 10; i++) {
            Thread.sleep(9000);
            app.reportOnPriceRequests();
        }
    }

    private void simulatePriceRequests() {
        new Thread(new RequestForPriceSimulator()).start();
    }

    private void reportOnPriceRequests() {
        long startNanos = System.nanoTime();
        new ReportSimulator().generateReport();
        long elapsedNanos = System.nanoTime() - startNanos;
        System.out.println("Took " + elapsedNanos / 1000.0 + " milliseconds to generate report.\n\n");
    }

    private LocalDateTime truncateToSeconds(LocalDateTime ldt) {
        return ldt.truncatedTo(ChronoUnit.SECONDS);
    }

    private PriceRequest getPriceTracker(LocalDateTime key) {
        return priceRequests.get(key);
    }

    private PriceRequest getPriceTrackerEvenIfAbsent(LocalDateTime key) {
        return priceRequests.computeIfAbsent(key, v -> new PriceRequest());
    }

    public class RequestForPriceSimulator implements Runnable {

        @Override
        public void run() {
            LocalDateTime rightNow = truncateToSeconds(LocalDateTime.now());
            LocalDateTime ninentySecondsFromNow = rightNow.plusSeconds(90);
            while (rightNow.isBefore(ninentySecondsFromNow)) {

                PriceRequest pt = getPriceTrackerEvenIfAbsent(rightNow);
                double price = ThreadLocalRandom.current().nextDouble() * 10.0;
                pt.addRequest(price);

                try {
                    Thread.sleep(10);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

                rightNow = truncateToSeconds(LocalDateTime.now());
            }

            System.out.println("All done simulating a price request!\n");
        }
    }

    public class ReportSimulator {

        public void generateReport() {
            double lowest = Double.MAX_VALUE;
            double highest = Double.MIN_VALUE;
            double total = 0;
            long requestCounter = 0;

            int keyCounter = 0;
            int validKeyCounter = 0;

            LocalDateTime rightNow = truncateToSeconds(LocalDateTime.now());
            LocalDateTime key = rightNow.minusSeconds(90);
            while (key.isBefore(rightNow)) {
                keyCounter++;

                key = key.plusSeconds(1);

                PriceRequest pt = getPriceTracker(key);
                if (pt == null) {
                    continue;
                }

                validKeyCounter++;
                if (pt.getLowest() < lowest) {
                    lowest = pt.getLowest();
                }

                if (pt.getHighest() < highest) {
                    highest = pt.getHighest();
                }

                total += pt.getTotal();
                requestCounter += pt.getCounter();
            }

            System.out.println("Used " + validKeyCounter + " keys out of " + keyCounter + " possible keys.");
            System.out.println("Total records in last 90 seconds: " + requestCounter);
            System.out.println("Average records per second in last 90 seconds: " + requestCounter / 90);
            System.out.println("Lowest Price in last 90 seconds: " + lowest);
            System.out.println("Highest Price in last 90 seconds: " + highest);
            System.out.println("Total Price in last 90 seconds: " + total);
            System.out.println("Average Price in last 90 seconds: " + (total / requestCounter));
        }
    }

    public class PriceRequest {
        private long counter;
        private double lowest;
        private double highest;
        private double total;

        public PriceRequest() {
            lowest = Double.MAX_VALUE;
            highest = Double.MIN_VALUE;
        }

        public void addRequest(double price) {
            synchronized (this) {

                if (price < lowest) {
                    lowest = price;
                }

                if (price > highest) {
                    highest = price;
                }

                total += price;
                counter++;
            }
        }

        public double getCounter() {
            synchronized (this) {
                return counter;
            }
        }

        public double getLowest() {
            synchronized (this) {
                return lowest;
            }
        }

        public double getHighest() {
            synchronized (this) {
                return highest;
            }
        }

        public double getTotal() {
            synchronized (this) {
                return total;
            }
        }
    }

}