O (1) в Java-алгоритме

У меня есть две конечные точки, одна из которых ответственна за транзакции приема и другие ответственные за создание статистики на основе транзакций только с последней минуты.O (1) в Java-алгоритме

Чтобы сохранить их, я с помощью ConcurrentNavigableMap:

@Component 
@Log 
public class DatastoreComponent { 

    private ConcurrentNavigableMap<Long, List<Transaction>> transactions; 

    public DatastoreComponent() { 
     this.transactions = new ConcurrentSkipListMap<>(); 
    } 

    public synchronized List<Transaction> addTransaction(Transaction t){ 
     log.info("Adding transaction: "+t); 
     List<Transaction> transactionAtGivenTime = transactions.get(t.getTimestamp()); 
     if(transactionAtGivenTime == null) transactionAtGivenTime = new ArrayList<>(); 
     transactionAtGivenTime.add(t); 
     return transactions.put(t.getTimestamp(), transactionAtGivenTime); 
    }

Я использую метку время в качестве ключа, так что я могу получить все сделки от последней минуты просто хвостовой карты, следующим образом:

public StatisticsFacade aggregate(){ 
     List<Transaction> validTransactions = new ArrayList<>(); 
     dataStore.getTransactions().tailMap(sixtySecondsAgo()) 
         .values() 
         .parallelStream() 
         .forEach(list -> validTransactions.addAll(list)); 
     statsAgg.aggreate(validTransactions); 
     return this; 
    }

до сих пор, так хорошо (я думаю?). Во всяком случае, процесс происходит в методе statsAgg.aggreate(), и этот метод должен быть O (1). Моя реализация такова:

public synchronized void aggreate(List<Transaction> validTransactions) { 
     if(validTransactions == null || validTransactions.isEmpty()) 
      return; 
     this.avg = validTransactions.parallelStream().mapToDouble(a -> a.getAmount()).average().getAsDouble(); 
     this.sum = validTransactions.parallelStream().mapToDouble(a -> a.getAmount()).sum(); 
     this.max = validTransactions.parallelStream().mapToDouble(a -> a.getAmount()).max().getAsDouble(); 
     this.min = validTransactions.parallelStream().mapToDouble(a -> a.getAmount()).min().getAsDouble(); 
     this.count = new Long(validTransactions.size()); 
    }

Я не совсем уверен, что это O (1), так как я бегу по списку 4 раза ... Я попробовал экстракт validTransactions.parallelStream().mapToDouble(a -> a.getAmount()) переменной и повторного использования это, но, конечно, как только поток обрабатывается, он закрыт, и я ничего не могу сделать.
Итак, вопрос: это O (1), а если нет, есть ли способ запустить поток и тоже все эти вычисления сразу?

источник

2016-12-03 Luiz E.

Как он может быть постоянным, если вы посмотрите на каждый элемент? Обновите статистику на основе одной новой транзакции, а не пересчитывайте их с нуля. –

'.collect (summaryizing Double (Transaction :: getAmount))' Но как вы думаете, что это имеет шанс быть O (1), а не «O (validTransactions.size())», ускользает от меня. –

@NicoSchertler Я пробовал это, но если я обновляю статистику каждый раз, когда происходит транзакция, если никакая транзакция не добавляется, то нет перерасчета, и я получаю старую статистику (например, статистику более 60 секунд назад) –

Алгоритм, который решает вашу проблему, должен быть как минимум сложнее O (n), поскольку вам необходимо пройти через каждый элемент в validTransactions хотя бы один раз.

И это не стало бы О (1), даже если вы запустите validTransactions.parallelStream().mapToDouble(a -> a.getAmount()) только один раз.

источник

2016-12-03 14:52:53 Default71721

Я думаю, что для этой проблемы можно создать алгоритм O (1 * m) (где * m * - номер транзакций, выходящих/входящих в текущий 60-секундный блок), но для этого потребуется совершенно другой подход. Кроме того, при небольшом количестве транзакций O (n) может быть быстрее, так как этот O (1) в моем уме достигается в способе «O (60 * м)» (мин/макс для 60-секундного блока с 1-й гранулярностью). Сумма и среднее значение можно сделать в O (1 * m) легко. – Ped7g

O (1) в Java-алгоритме

ответ

Смежные вопросы