CODEWITHSUNDEEP
javaperformancealgorithm
James Raitsev
James Raitsev

Reputation: 96461

How to map List of KVP to Map<Key, List<Value>> .. fast

I quickly wrote this snippet to do the job

private void map() {
    for (KVPair kvPair : content) {
        String k = kvPair.getKey();
        String v = kvPair.getValue();

        if (mappedContent.containsKey(k)) {
            List<String> values = mappedContent.get(k);
            values.add(v);
        } else {
            List<String> values = new ArrayList<>();
            values.add(v);
            mappedContent.put(k, values);
        }
    }
}

It works and when ran with 1k, 2k, 4k and 8k of random data, i get the following performance (average of 100,000 runs)

Running with 1,000 pairs
  [perfRun] 100000 iterations took 3 seconds
  [perfRun] Run time: 3758786000 ns. 1 iteration takes 37 us
Running with 2,000 pairs
  [perfRun] 100000 iterations took 6 seconds
  [perfRun] Run time: 6675544000 ns. 1 iteration takes 66 us
Running with 4,000 pairs
  [perfRun] 100000 iterations took 13 seconds
  [perfRun] Run time: 13337145000 ns. 1 iteration takes 133 us
Running with 8,000 pairs
  [perfRun] 100000 iterations took 27 seconds
  [perfRun] Run time: 27109480000 ns. 1 iteration takes 271 us

Roughly speaking, when size doubles, time doubles. I'd take linear growth, but wonder still, can we do better? Is it possible to map things using constant time?

Upvotes: 2

Views: 490

Answers (3)

A4L
A4L

Reputation: 17595

based on @Quoi's answer, don't know exactly if it makes a difference to save the else block after the null check

for (KVPair kvPair : content) {
    String k = kvPair.getKey();
    List<String> values = mappedContent.get(k);
    if (values == null) {
        values = new ArrayList<>();
        mappedContent.put(k, values);
    }
    values.add(kvPair.getValue());
}

also you can make some assumption on how large a list might become, so you pass that size to the list constructor and save the time that the list needs to re-size. If memory is not an issue you might take content.size() + 1 as size for the list.

Upvotes: 1

vossad01
vossad01

Reputation: 11958

Unless you can change the underlying data structure, no, you cannot do better than linear time.

Consider this: You have a list with n unique entries. To map each one that one must be accessed. Suppose access costs 1. Then there must n accesses. Thus you have complexity of at n * 1 = n, or linear time as your benchmarking pointed out.

Now if you can you had a data structure to something can share the data but provide both interfaces, then you could achieve constant time in switching between the two. Obviously you would have different static types than your example though.

Upvotes: 0

Subhrajyoti Majumder
Subhrajyoti Majumder

Reputation: 41220

What I can see, mappedContent.containsKey(k) its unnecessary which roughly takes BigO(n), You can escape by null check, 

for (KVPair kvPair : content) {
        String k = kvPair.getKey();
        String v = kvPair.getValue();
        List<String> values = mappedContent.get(k);
        if (values!=null) {
            values.add(v);
        } else {
            values = new ArrayList<>();
            values.add(v);
            mappedContent.put(k, values);
        }
}

Upvotes: 3

Related Questions