Determine and count unique values of an array

Very fast function to determine and count unique values of numeric, logical, char, cell arrays.

Description

This function determines the unique values of an N-D array, and counts instances of those values using MATLAB's accumarray function, or in cases where accumarray is inappropriate the more traditional sort-diff method is used.

Its primary use is to very quickly count the number of instances of unique values within an array.

However, if only returning unique values (and not counts), it is slightly faster than MATLAB's built-in 'unique' function for arrays of intermediate to large sizes. This is particularly true for integer-valued arrays (not necessarily just integer type). For float arrays, the speed increase is due mainly to fewer input validation tests and other options. Unlike 'unique' it does not have 'rows', 'first', or 'last' options.

It returns the unique values in a sorted vector, and counts of those values are in the same order.

- Usage:
>> [uniques] = count_unique(largeArray);
>> [uniques,numUnique] = count_unique(largeArray);

- Example (a rather trivial example):
>> a = repmat((1:1000),1000,1); %build an unsorted array of values
>> [uniques,numUnique] = count_unique(a);
>> size(uniques)
ans =
        1000 1
>> numUnique(1:10)
ans =
        1000
        1000
        1000
        1000
        1000
        1000
        1000
        1000
        1000
        1000

- Example (a less trivial example):
>> a = floor(rand(1e6,1)*1e6);
>> [uniques,numUnique] = count_unique(a);
>>uniques(1:10),numUnique(1:10)
ans =
     0
     1
     4
     5
     7
     9
    11
    12
    15
    19

ans =
     2
     2
     2
     1
     2
     3
     1
     1
     1
     1

For returning only unique values:
- Speed Comparison (integer valued):
>> a = floor(rand(1e7,1)*1e6);
>> tic;[uniques] = count_unique(a);toc %count_unique
Elapsed time is 1.891197 seconds.
>>tic;[uniques] = unique(a);toc %built-in MATLAB
Elapsed time is 2.829160 seconds.

- Speed Comparison (decimal valued):
>>a = rand(1e7,1)*1e6;
>>tic;[uniques] = count_unique(a,'float');toc
Elapsed time is 2.995239 seconds.
>>tic;[uniques] = unique(a);toc
Elapsed time is 3.002850 seconds.

• MATLAB release: MATLAB 7.7 (R2008b)
• Other requirements: Requires 'accumarray' function, present in recent MATLAB versions.
• Other Files: count_unique.m, ; license.txt

[John D'Errico]

I'm confused. Even the author admits this is only slightly faster than the existing unique, and that the main reason is probably because it does not bother to check the arguments. He also admits that it has considerably less capability than the existing unique.

Anyone truly in need of the maximum speed is better off with a direct call to accumarray anyway, which will further reduce any overhead.

Why does this exist? Perhaps some time comparisons might be of value, and some examples that show why this is a better choice than the existing alternatives.

The code does look to be carefully written at a glance, and the help seems reasonable, were I to rate this.

[Anthony Kendall]

John,
The code is primarily used to count the number of each unique instance within an array, but as a side benefit is slightly faster than the existing unique function (and quite a bit faster for integer-valued arrays). I'll modify the description to make this more obvious.

Thanks for your comments.

[John D'Errico]

Ok. That was quick. This is looking better now. As a potential downloader, the description gives me some reason to use it, especially if I'm looking to squeeze some speed out of a tight piece of code.

A look inside the code is always interesting. I like to see when the author has taken care in the code. Friendly code worries about things like the presence of nans, infs, different variable classes, etc. Also lots of comments. White space. Intelligently named, mnemonic variable names. These things make any piece of code an easy read, and easy to debug in the future.

Good help, examples. etc. All well done. Thanks for the changes.

[Bruno Luong]

Inside the code, the author uses ACCUMARRAY on the values of the input array. This is a poor choice because it might create a large chunk of memory and slow down greatly.

Here is a code to check this effect. On my computer the worse time is 2.5 s, and unique can accomplish in less than 1 ms.

power=1:64;
time=zeros(length(power),2);

for k=1:length(power)
    
    twoelem=[0 2.^power(k)-1];
    disp(twoelem)
    
    tic
    count_unique(twoelem);
    time(k,1) = toc;
    
    tic
    unique(twoelem);
    time(k,2) = toc;
end
fprintf('worse time = %g s\n', max(time,[],1))
plot(power,time);
ylabel('second');
title('Time for array of two elements')
legend('count unique','unique')

[Anthony Kendall]

Bruno,
Thanks for making this point. This can be addressed by specifying the 'float' option in count_unique. However, I've added also added a check that when the maximum value of the input array is much greater than its number of elements, accumarray is not used.

I ran your example on the unmodified code, and got results similar to yours. Now, on the modified code (without specifying the 'float' option, which does not use accumarray), the run times are both trivial in your example. The change increased run times for large array integer values slightly, and the description above is modified to reflect that.

Thanks again.

[Ilya]

 

[dave matthews]

it would be nice to extend this to the n-d case, or at least the 2-d case, i.e., find and list unique pairs?

x = [1 2; 1 3; 1 2];
then, uniques = [1 2], [1 3];
and, numuniques = [2 1];

thanks