Java 代码执行以在 O(1) 中获得结果

Question

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

最近 90 条记录中的总记录
最近 90 条记录中的平均记录
最近 90 条记录中的最低价
最近 90 条记录中的最高价
最近 90 条记录的总价
最近 90 条记录的平均价格

我已经通过如下代码a成功实现了要求

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)

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

Answer 1

据推测，您的记录比过去 90 秒的记录多得多。循环遍历所有这些以仅过滤掉您感兴趣的少数几个是您花费大部分时间的地方。您需要

在迭代之前对键列表进行排序（这本身不是 O(1) 操作），或者
首先让数据按排序顺序排列。（查看 ConcurrentSkipListMap 是否满足您的需求。）

数据排序后，从最近的末尾开始迭代。一旦找到超过 90 秒的记录，就可以停止循环。

注意： 这永远不会真正是 O(1)，因为您正在遍历一个可以改变大小的列表。您应该仍然能够通过对正在循环的集合进行排序来大大提高性能。

Answer 2

来自评论 - 这是我计算要使用的确切键的意思的示例。它仍然使用 LocalDateTime（而不是 nanos 的 Long）作为键，但它被 截断为秒 。所以最多需要收集90把钥匙。

聚合 PriceRequest class 可以在同一秒内保持并发请求。（它不是完全线程安全的。）

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

}

Java 代码执行以在 O(1) 中获得结果

Java code execution to get result in O(1)

java

big-o

time-complexity

concurrenthashmap