O(1) in a Java algorithm

Question

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?

How could it be constant if you look at every element? Update the stats based on the single new transaction instead of recalculating them from scratch. — Nico Schertler
– Nico Schertler, Commented Dec 3, 2016 at 14:43
.collect(summarizingDouble(Transaction::getAmount)) But how you figure this to have any chance of being O(1) as opposed to O(validTransactions.size()), eludes me. — Marko Topolnik
– Marko Topolnik, Commented Dec 3, 2016 at 14:43
@NicoSchertler I tried that, but if I update stats each time a transaction happen, if no transaction is added, there is no recalculation, and I get old stats (like, stats from more than 60 seconds ago) — Luiz E.
– Luiz E., Commented Dec 3, 2016 at 14:45
What was your question, then? Performing an O(1) operation four times is still O(1). — Marko Topolnik
– Marko Topolnik, Commented Dec 3, 2016 at 14:50
Also, you can compute all these statistics in a single pass: docs.oracle.com/javase/8/docs/api/java/util/stream/…. Given that you store everything in memory and don't seem to flush the old transactions, my guess is that your list is not very large, and that using a sequential stream would be faster that a parallel one. — JB Nizet
– JB Nizet, Commented Dec 3, 2016 at 14:57

Coderslang Master · Accepted Answer · 2016-12-03 14:52:53Z

2

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.

answered Dec 3, 2016 at 14:52

Coderslang Master

3682 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ped7g Over a year ago

I think it's possible to create O(1*m) algorithm for this problem (where m is number of transactions leaving/entering the current 60s time block), but it would require completely different approach. Also when there's little number of transactions, the O(n) may be faster, as that O(1) in my mind is achieved in "O(60*m)" way (min/max for 60s block with 1s granularity). Sum and average can be done in O(1*m) easily.

Collectives™ on Stack Overflow

O(1) in a Java algorithm

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related