count occurrences of string in a single cell array (How many times a string appear)

I have a single cell array containing long string as shown bellow:

xx = {'computer', 'car', 'computer', 'bus', 'tree', 'car'};

I am trying to achieve output in two cell array as shown:

xx  = {'computer', 'car', 'bus', 'tree'}
occ = {'2', '2','1','1'}

Your suggestion and ideas are highly appreciated. Thanx in advance

Answer 1

[Azzi Abdelmalek]

xx = {'computer', 'car', 'computer', 'bus', 'tree', 'car'}
a=unique(xx,'stable')
b=cellfun(@(x) sum(ismember(xx,x)),a,'un',0)

[KnowledgeSeeker]

Thank you Azzi, you save my day.

[Rahulsivanand s]

What is x?

Answer 2

[Jos (10584)]

A faster method and more direct method of counting using the additional output of UNIQUE:

XX = {'computer', 'car', 'computer', 'bus', 'tree', 'car'}
[uniqueXX, ~, J]=unique(XX) 
occ = histc(J, 1:numel(uniqueXX))

[Adam Danz]

Jos's (updated: and Bruno's) methods are the most efficient and fastest among the answers here to date.

To compare them, each method was timed 10,000 times using tic/toc and the median durations are compared below (Matlab r2019b update 6, Windows 10 Pro 64bit 16GB ram).

• Jos' histc vs Azzi's cellfun: The histc method was 3.5 x faster.
• Jos' histc vs MSchoenhart's countcats: The histc method was 5.4 x faster after modification, 1.87x faster before modification (see notes).
• Jos' histc vs My histcounts (shown below): The histc method was 9.5 x faster.
• Jos' histc vs Girish's loops: The histc method was 100.2 x faster (timed only 500 times).
• Jos' histc vs Bruno's accumarray: The histc and accumarray were nearly indistinguishable so I ran the comparison 3 times and they all resulted in the accumarray method 1.01-1.02 x faster

Some methods were slighly adapted so that all methods produced a column vector of counts that matched the original order of the strings. All versons produced the exact same output.

% TEST DATA
load carsmall.mat
Mfg = cellstr(Mfg); 

% JOS'S HISTC METHOD
[uniqueXX, ~, J]=unique(Mfg,'stable');     
occ = histc(J, 1:numel(uniqueXX)); 

% BRUNO'S ACCUMARRAY METHOD
[yy,~,i]=unique(Mfg,'stable');         
count=accumarray(i,1,[numel(yy),1]);   

% AZZI'S CELLFUN METHOD
a=unique(Mfg,'stable');                       
b=cellfun(@(x) sum(ismember(Mfg,x)),a);  

% MSCHOENHART'S COUNTCATS METHOD
unq=unique(Mfg,'stable');   
c = categorical(Mfg, unq, 'Ordinal', true);
N = countcats(c);
% Note: the original is faster but does not maintain the 
% original order of outputs and Jos' is still 1.87x faster.
%   c = categorical(Mfg);
%   N = countcats(c);

% ADAM DANZ'S HISTCOUNTS METHOD
MfgUnq = unique(Mfg,'stable'); 
Nc = histcounts(categorical(Mfg), categorical(MfgUnq))'; 

% GIRISH'S LOOPS METHOD
U=unique(Mfg,'stable');
A=zeros(numel(U),1);
for i=1:numel(U);
    for j=1:numel(Mfg)
        if strcmp(U(i),Mfg(j))==1;
            A(i)=A(i)+1;
        end
    end
end

% TEST FOR EQUALITY
isequal(occ, count, b, N, Nc, A)
%     ans =
%       logical
%        1

[Bruno Luong]

@Adam: Please add this one to your bechmark (I don't have the test file)

[yy,~,i]=unique(Mfg,'stable');
count=accumarray(i(:),1,[numel(yy),1]); % remove (:) if Mfg is column cell, however it might not matter for runtime

I'm confidence it's even faster than Jos's HISCT

>> i=randi(100,1,1e7);
>> tic; c=histc(i, 1:100); toc
Elapsed time is 0.187668 seconds.
>> tic; c=accumarray(i(:), 1, [100,1]); toc
Elapsed time is 0.045374 seconds.

[Adam Danz]

@Bruno Luong, added. But it looks like it's nearly tied with Jos' but technically, the median speed of yours was 1.01-1.02 x faster than Jos'.

To rule out any differences between r2019b (where the tests were run) and r2020a, I repeats the comparison again with Matlab Online and yours was 1.0093 x faster than Jos'. Of course there's small variation when the entire comparison is repeated.

This comparison repeats the timing of each method 10,000 times and compares the medians. Here's a boxplot comparison of all 10k reps (as you can see, there's lot of outlier).

But single iterations are probably too fast for tic/toc so I repeated it by timing the entire loop (see below) using Matlab Online (20a) but I got similar results:

Histc: Elapsed time is 1.116929 seconds.

Accumarray: Elapsed time is 1.100523 seconds.

where accumarray is 1.0149 x faster

clear
load carsmall.mat
Mfg = cellstr(Mfg);
pause(.1)

t = tic();
for q = 1:10000
    [uniqueXX, ~, J]=unique(Mfg,'stable');
    occ = histc(J, 1:numel(uniqueXX));
end
toc(t)

clear
load carsmall.mat
Mfg = cellstr(Mfg);
pause(.1)

t = tic();
for q = 1:10000
    [yy,~,i]=unique(Mfg,'stable');
    count=accumarray(i,1,[numel(yy),1]);
end
toc(t)

[Bruno Luong]

You might try to replace HISTC with HISTCOUNTS which on my book faster (but still slower than accumarray)

i = randi(100,1,1e7);
tic; c=histc(i, 1:100); toc                 % Elapsed time is 0.220877 seconds.
tic; c=histcounts(i, [1:100 Inf]); toc      % Elapsed time is 0.051881 seconds.
tic; c=accumarray(i(:), 1, [100,1]); toc    % Elapsed time is 0.038259 seconds.

The INF must be added for HISCOUNTS since it treats the last edge not like other edges (I really distke this change).

The complexity of HISTC/HISTCOUNTS is at best IMO, O(N x log(M)) and ACCUMARRAY O(N), where N length(i) and M length of the BINS.

I must have a lengthly discussion with Walter long ago on the compexity of HISTC.Both can be easily implemented as multi-threads.

[Adam Danz]

For the carsmall data used in the other comparisons, histc was actually 1.33x faster than histcounts in r2019b and 1.22 x faster on r2020a (matlab online). On both machines I repeated the 10000-rep analysis 3 times and the final results were all within +/-0.02 of what's reported.

The difference between those numbers and your results may have to do with first-time-costs if you're just measuring the execution once with tic/toc.

I like your dedication to optimization! 😎

[Bruno Luong]

No first-time cost I ensure you. I post just one result ans snipet for simplicity, but I ran tic/toc on loop and within function and on 2 different computers (Windows 8.1 Windows 10 both with R2020a).

The conclusion on my side doesn't not change.

Yeah I'm kind of obssesing with Matlab speed, and I can't hide it.

Answer 3

[MSchoenhart]

A very fast and simple vectorized method is to use categories (since R2013b). "countcats" is also using histc in the background but the code looks much cleaner:

xx = {'computer', 'car', 'computer', 'bus', 'tree', 'car'};
c = categorical(xx);
categories(c)
countcats(c)

[Adam Danz]

*Edited question to format code

Nice solution!

[Giuseppe Degan Di Dieco]

Dear MSchoenhart,

thanks for your solution, it helped me too.

Best!

Answer 4

[Bruno Luong]

[yy,~,i] = unique(xx,'stable');
count = accumarray(i(:),1,[numel(yy),1]);

[Adam Danz]

+1

Just as fast if not a tad faster than Jos' already-super-fast solution.

Answer 5

[Girish Chandra]

Not using histc function you can do it in the following way

xx = {'computer', 'car', 'computer', 'bus', 'tree', 'car'}
U=unique(xx)
A=zeros(1,numel(U))
for i=1:numel(U)
    for j=1:numel(xx)
        if strcmp(U(i),xx(j))==1
            A(i)=A(i)+1
        end
    end
end

[Christophe Pouillot]

Best solution is Jos (10584) 's one as it leverages MATLAB's vectorization.

[Jon Adsersen]

Based on the answer by Jos, a function that works for both numerical and string arrays could be formulated:

function [rep_values, N_rep, ind_rep] = f_reapeated_elements(A)
% Find repeated elements in A (can be both numeric or cell strings etc.)
% Outputs:
% rep_values - repeated values in A (occuring 2 or more times)
% N_rep - Number of repetitions of the values given in "rep_values"
% ind_rep - Ind in A of repeated values (occuring 2 or more times)

[un, ~, ind_un] = unique(A) ;
N_A = histc(ind_un,1:numel(un)) ; 
rep_values = un(N_A>1) ;
N_rep = N_A(N_A>1) ;

ind_cell  = cell(1, numel(rep_values)) ;
A_list = 1:numel(A) ;
for k = 1:numel(rep_values)
    if isnumeric(rep_values)
        ind_cell{k} = find(A == rep_values(k)) ;
    else
        log_ind = strcmp(A,rep_values(k)) ;
        ind_cell{k} = A_list(log_ind) ;  
    end 
end

ind_rep = unique([ind_cell{:}]) ;

[Adam Danz]

*Answer edited to correctly format code