Finding the count of elements in an array fastly

Question

I have an array, size can be up to 10000. It holds only 1/2/3/4. I need to find how many 1s, 2s, 3s and 4s are there in the array. What's the fastest way of doing it? My language of use is Java. My piece of code-

for(int i=0; i<myArray.length;i++){
            int element = myArray[i];
            if(element == 1){
                onesCount++;
            }
            else if(element == 2){
                twosCount++;
            }
            else if(element == 3){
                threesCount++;
            }
            else
                foursCount++;
}

I hope there's a good solution.

Since you are anyway going to parse the entire array, your run time would have to be `O(n)` no matter how you do it. — noMAD, Mar 05 '12 at 07:19
You can do it similarly by threading, where each thread can count occurence for a specific range of elements in an array, thread-1 counts for first 2000 elements & so on parallely. — Nayan Wadekar, Mar 05 '12 at 07:53
@sans481, You see your solution seems to be very good. There are in fact some micro optimizations possible (and surely worth trying). And now that we are all talking about them, I wanted to note, that you could use the prefix incrementation (or decr, respectively) to "speed up" your loop ;) [see this quesion](http://stackoverflow.com/questions/561588/what-is-more-efficient-i-or-i) — hage, Mar 05 '12 at 08:14

score 7 · Accepted Answer · answered Mar 05 '12 at 07:29

7

int count[5]; //initialize this to 0
for(int i = 0; i<n; i++)
{
count[array[i]]+=1;
}

answered Mar 05 '12 at 07:29

noMAD

7,744
19
56
94

1

Although it is still O(n), this one can save a few comparisons. – Bob Wang Mar 05 '12 at 07:59
OTOH, it now has to update an array on the heap instead of a local int on the stack. – Thilo Mar 05 '12 at 08:00
This might be better then mine. Doing this unsafe would win, I assume. – Haymo Kutschbach Mar 05 '12 at 08:01
Uh. just realized this is Java. So no unsafe here, sorry. – Haymo Kutschbach Mar 05 '12 at 08:57
1

@noMAD ++count[array[i]]; would be more faster according to http://stackoverflow.com/questions/561588/what-is-more-efficient-i-or-i. Won't it be? – sgowd Mar 05 '12 at 10:37
@HaymoKutschbach: What do you mean by `unsafe`? Could you elaborate? – noMAD Mar 05 '12 at 17:32
I failed in realizing this is Java. In .NET one can speed operations further by using "unsafe" pointer arithmetics. – Haymo Kutschbach Mar 05 '12 at 19:01

Juvanis · Answer 2 · 2012-03-05T07:53:10.047

2

You will have separate counters for the array entries. Each will be incremented upon a new matching number is found, so you have to visit every index at least once, that is to say you will have an algorithm working in O(n) time. Switch statement could be preferred instead of multiple if-else statements:

int[] array = new int[10000];
// ... populate array
int[] counters = new int[4];

for (int i = 0; i < array.length; i++)
{
    int temp = array[i];
    switch (temp) {
    case 1:
        counters[0]++;
        break;
    case 2:
        counters[1]++;
        break;
    case 3:
        counters[2]++;
        break;
    case 4:
        counters[3]++;
        break;
    default:
        // to do.
    }
}

edited Mar 05 '12 at 07:53

answered Mar 05 '12 at 07:28

Juvanis

25,802
5
69
87

Oops! I forgot switch case. It might eliminate good amount of comparisons. But why array of counters instead of count variables(like in my question). Any reason? – sgowd Mar 05 '12 at 09:48
no specific reason but it is more flexible. if you want to print all counters, you will just iterate over counters array with a for loop. isn't that good? – Juvanis Mar 05 '12 at 09:53

score 2 · Answer 3 · answered Mar 05 '12 at 07:29

There is no solution essentially better than yours. Could be more flexible, but not faster. Everything has to do at least that single pass through the whole array.

The only area of performance optimization would be to avoid doing this operation, for example by keeping track of the counters as the array is updated. If that is worth the trouble (probably not) depends on how often you need to do this, how big the array is, and what else you need to do with it.

score 1 · Answer 4 · answered Mar 05 '12 at 07:31

1

If you are using Java 7 you could make use of the Fork/Join Framework. The complexity will still be O(n)... but it may be faster for a large array

answered Mar 05 '12 at 07:31

hage

5,966
3
32
42

+1. Not at all sure if this makes sense in this case, but in general, this is a perfect task for parallel processing. – Thilo Mar 05 '12 at 08:01
1

@Thilo, Yes, overhead of thread creation may be too big for this operation, but I think it's worth trying – hage Mar 05 '12 at 08:06

score 0 · Answer 5 · answered Mar 05 '12 at 07:21

You can do it using one pass through the array.

Just have yourself an array of four elements, each representing one of your values (1/2/3/4) and for each element in the original array you increase the count at the corresponding place in the "count" array. That would make it O(n).

score 0 · Answer 6 · answered Mar 05 '12 at 07:25

0

If you can use a Map or a custom class instead. If you can't you have to iterate through the whole array. If you don't habe performance problems right now with this, I sugest to just do the iteration.

answered Mar 05 '12 at 07:25

BetaRide

16,207
29
99
177

Haymo Kutschbach · Answer 7 · 2012-03-05T08:06:17.590

if the switch version (deporter) or noMAD's version is not best, try this:

for (int i = 0; i < myArray.length; i++) {
    int element = myArray[i];
    if (element > 2) {
        if (element == 4) {
            foursCount++;
        } else 
            threesCount++;
    } else {
        if (element == 2) 
            twosCount++;
        else 
            onesCount++; 
    }
}

It may save a tiny amount of comparison. But it depends on the true data. If you are lucky with the data, the straightforward version may do better.

Besides that, using parallelism is always worth a try for large data.

brettw · Answer 8 · 2012-03-05T08:41:50.600

0

I don't think you'll get any faster than this:

final int[] counts = new int[5];
final int length = array.length - 1;
for (int i = 0; i < length; i++) {
   counts[array[i]]++;
}

Note that in the for loop, array.length is not referenced. It is put into a local final int, this avoids a dereference of array.length in each iteration.

I benchmarked this vs. this method that uses a switch..case statement and only local stack variables:

    int count1 = 0;
    int count2 = 0;
    int count3 = 0;
    int count4 = 0;

    for (int i = array.length - 1; i >= 0; i--) {
        switch (array[i]) {
        case 1:
            count1++;
            break;
        case 2:
            count2++;
            break;
        case 3:
            count3++;
            break;
        case 4:
            count4++;
            break;
        }
    }

The results were the first method took 17300 nanoseconds, and the switch..case method took 79800 nanoseconds. [UPDATED: forgot to divide the nanoseconds by 10. I ran each method 10 times.]

Note: I did warn-up the VM first before benchmarking.

edited Mar 05 '12 at 08:41

answered Mar 05 '12 at 08:05

brettw

10,664
2
42
59

how did you measure? release build? JIT optimizations? Debugger attached? data size? repetitions? cache aware? Could you post some code? At best: assembly for both versions? – Haymo Kutschbach Mar 05 '12 at 08:08
I ran the VM with '-server' and warmed it up with 11000 calls to the two methods (the server JIT hotspot compile threshold is 10000 iterations). Then used System.nanoTime() before and after calling each of the two methods 10 times. Yes, compiled with debug. No, no debugger attached. Data-size of 10000 integers. – brettw Mar 05 '12 at 08:15
Running javap to dump the two methods' bytecode is an exercise left to the reader. Suffice it to say that the first method is 32 'lines' of bytecode, and the second method 105. The second method uses the 'tableswitch' bytecode along with lots of 'goto' jumps and in the end is much less efficient (as evidenced by the benchmark). – brettw Mar 05 '12 at 08:26
Accessing larger amounts of memory in reverse is often slower than accessing it in order as the cache can pre-fetch the data you will need. – Peter Lawrey Mar 05 '12 at 08:33
@Peter Lawrey, true that. I changed my code and it shaved 300ns off of the average (now measuring 17300ns). – brettw Mar 05 '12 at 08:40
Its just the way the cache is optimised to access vectors of data, but the difference is not great as you have seen. – Peter Lawrey Mar 05 '12 at 08:44

Finding the count of elements in an array fastly

8 Answers8