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

从评论中 - 这是我的意思的一个例子，即计算要使用的确切键。它仍然使用 a LocalDateTime（而不是 Long 用于 nanos）作为键，但它被截断为 seconds。所以最多需要收集 90 个密钥。有一个聚合PriceRequest类可以在同一秒内保存并发请求。（它不是完全线程安全的。）public class Last90Seconds {&nbsp; &nbsp; private Map<LocalDateTime, PriceRequest> priceRequests = new ConcurrentHashMap<>();&nbsp; &nbsp; public static void main(String[] args) throws Exception {&nbsp; &nbsp; &nbsp; &nbsp; Last90Seconds app = new Last90Seconds();&nbsp; &nbsp; &nbsp; &nbsp; app.simulatePriceRequests();&nbsp; // thread which continuously simulates a price request&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < 10; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Thread.sleep(9000);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; app.reportOnPriceRequests();&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; private void simulatePriceRequests() {&nbsp; &nbsp; &nbsp; &nbsp; new Thread(new RequestForPriceSimulator()).start();&nbsp; &nbsp; }&nbsp; &nbsp; private void reportOnPriceRequests() {&nbsp; &nbsp; &nbsp; &nbsp; long startNanos = System.nanoTime();&nbsp; &nbsp; &nbsp; &nbsp; new ReportSimulator().generateReport();&nbsp; &nbsp; &nbsp; &nbsp; long elapsedNanos = System.nanoTime() - startNanos;&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Took " + elapsedNanos / 1000.0 + " milliseconds to generate report.\n\n");&nbsp; &nbsp; }&nbsp; &nbsp; private LocalDateTime truncateToSeconds(LocalDateTime ldt) {&nbsp; &nbsp; &nbsp; &nbsp; return ldt.truncatedTo(ChronoUnit.SECONDS);&nbsp; &nbsp; }&nbsp; &nbsp; private PriceRequest getPriceTracker(LocalDateTime key) {&nbsp; &nbsp; &nbsp; &nbsp; return priceRequests.get(key);&nbsp; &nbsp; }&nbsp; &nbsp; private PriceRequest getPriceTrackerEvenIfAbsent(LocalDateTime key) {&nbsp; &nbsp; &nbsp; &nbsp; return priceRequests.computeIfAbsent(key, v -> new PriceRequest());&nbsp; &nbsp; }&nbsp; &nbsp; public class RequestForPriceSimulator implements Runnable {&nbsp; &nbsp; &nbsp; &nbsp; @Override&nbsp; &nbsp; &nbsp; &nbsp; public void run() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LocalDateTime rightNow = truncateToSeconds(LocalDateTime.now());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LocalDateTime ninentySecondsFromNow = rightNow.plusSeconds(90);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while (rightNow.isBefore(ninentySecondsFromNow)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; PriceRequest pt = getPriceTrackerEvenIfAbsent(rightNow);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; double price = ThreadLocalRandom.current().nextDouble() * 10.0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pt.addRequest(price);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; try {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Thread.sleep(10);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } catch (InterruptedException e) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; e.printStackTrace();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; rightNow = truncateToSeconds(LocalDateTime.now());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("All done simulating a price request!\n");&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; public class ReportSimulator {&nbsp; &nbsp; &nbsp; &nbsp; public void generateReport() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; double lowest = Double.MAX_VALUE;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; double highest = Double.MIN_VALUE;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; double total = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; long requestCounter = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int keyCounter = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int validKeyCounter = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LocalDateTime rightNow = truncateToSeconds(LocalDateTime.now());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LocalDateTime key = rightNow.minusSeconds(90);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while (key.isBefore(rightNow)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; keyCounter++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; key = key.plusSeconds(1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; PriceRequest pt = getPriceTracker(key);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (pt == null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; validKeyCounter++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (pt.getLowest() < lowest) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; lowest = pt.getLowest();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (pt.getHighest() < highest) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; highest = pt.getHighest();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; total += pt.getTotal();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; requestCounter += pt.getCounter();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Used " + validKeyCounter + " keys out of " + keyCounter + " possible keys.");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Total records in last 90 seconds: " + requestCounter);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Average records per second in last 90 seconds: " + requestCounter / 90);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Lowest Price in last 90 seconds: " + lowest);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Highest Price in last 90 seconds: " + highest);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Total Price in last 90 seconds: " + total);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Average Price in last 90 seconds: " + (total / requestCounter));&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; public class PriceRequest {&nbsp; &nbsp; &nbsp; &nbsp; private long counter;&nbsp; &nbsp; &nbsp; &nbsp; private double lowest;&nbsp; &nbsp; &nbsp; &nbsp; private double highest;&nbsp; &nbsp; &nbsp; &nbsp; private double total;&nbsp; &nbsp; &nbsp; &nbsp; public PriceRequest() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; lowest = Double.MAX_VALUE;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; highest = Double.MIN_VALUE;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public void addRequest(double price) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; synchronized (this) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (price < lowest) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; lowest = price;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (price > highest) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; highest = price;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; total += price;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; counter++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public double getCounter() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; synchronized (this) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return counter;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public double getLowest() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; synchronized (this) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return lowest;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public double getHighest() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; synchronized (this) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return highest;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public double getTotal() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; synchronized (this) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return total;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}

Answer 2

据推测，您拥有的记录远不止过去 90 秒的记录。遍历所有这些以仅过滤掉您感兴趣的少数几个是您花费大部分时间的地方。你需要要么在迭代它们之前对键列表进行排序（这本身不是 O(1) 操作），或者保持数据的排序顺序开始。（查看ConcurrentSkipListMap是否符合您的需求。）一旦数据按顺序排列，从最近的末尾开始迭代。一旦找到超过 90 秒的记录，就可以停止循环。注意：这永远不会是真正的 O(1)，因为您正在迭代一个可以改变大小的列表。您仍然应该能够通过对正在循环的集合进行排序来大大提高性能。