Выполнение Java-кода для получения результата в O (1)

Question

У меня есть веб-сервис, с которого я получаю время и цену.Я сохранил эти записи в ConcurrentHashMap, поскольку он должен поддерживаться в многопоточной среде с отметкой времени ( LocalDateTime ) в качестве ключа и ценой ( BigDecimal ) в качестве значений.Требовалось получить следующие данные

1. Всего записей за последние 90 записей
2. Среднее количество записей за последние 90 записей
3. Самая низкая цена за последние 90 записей
4. Самая высокая цена за последние 90 записей
5. Общая цена за последние 90 записей
6. Средняя цена за последние 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)

Может кто-нибудь, пожалуйста, помогите мне или предложите мнедругой подход к достижению этого.Я не должен использовать Коллекции, чтобы достигнуть O (1)

Answer 1

Из комментариев - вот пример того, что я имел в виду для вычисления точных ключей для использования.Он по-прежнему использует LocalDateTime (вместо Long для nanos) в качестве ключа, но он усекается до секунд .Таким образом, нужно собрать не более 90 ключей.

Существует совокупный класс 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;
            }
        }
    }

}

Answer 2

Предположительно, у вас намного больше записей, чем только за последние 90 секунд.Перебирая их все, чтобы отфильтровать только те немногие, которые вас интересуют, вы проводите большую часть своего времени.Вам нужно либо

1. отсортировать список ключей, прежде чем выполнять их итерацию (что само по себе не является операцией O (1)), либо
2. Хранить данные в отсортированном порядке, чтобыначинается с.(Посмотрите, соответствует ли ConcurrentSkipListMap вашим потребностям.)

Как только данные упорядочены в порядке, начните итерацию с самого последнего конца.Когда вы найдете запись, которая старше 90 секунд, вы можете остановить цикл.

Примечание: Это никогда не будет O (1), так как вы выполняете итерации по спискуэто может измениться в размере.Вы по-прежнему сможете значительно повысить производительность, упорядочив коллекцию, над которой вы работаете.