CODEWITHSUNDEEP
javaalgorithmbig-o
Luiz E.
Luiz E.

Reputation: 7229

O(1) in a Java algorithm

I have two endpoints, one responsible for receive transactions and other responsible for generate stats based on transactions from the last minute only.

To store them, I'm using a 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);
    }

I use the timestamp as key, so that I can get all transactions from last minute just tailing the map, as follow:

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

so far, so good (I guess?). well anyway, the process happens in the statsAgg.aggreate() method, and this method should be O(1). My implementation is like that:

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

I'm not really sure that this is O(1) since I'm running through the list 4 times...I tried extract validTransactions.parallelStream().mapToDouble(a -> a.getAmount()) to a variable and re-use it, but of course, once the stream is processed, it is closed and I can't do anything.
So the question is: is this O(1) and if not, is there a way to run through the stream and too all this calculations at once?

Upvotes: 0

Views: 491

Answers (1)

Coderslang Master
Coderslang Master

Reputation: 368

An algorithm that solves your problem has to be at least O(n) complexity, as you have to go through each element in validTransactions at least once.

And it wouldn't become O(1) even if you run validTransactions.parallelStream().mapToDouble(a -> a.getAmount()) just once.

Upvotes: 2

Related Questions