Самый быстрый способ найти уникальные значения в массиве

Question

Я пытаюсь найти быстрый способ поиска уникальных значений в массиве и удалить 0 как возможность уникального значения.

Сейчас у меня есть два решения:

result1 = setxor(0, dataArray(1:end,1)); % This gives the correct solution 
result2 = unique(dataArray(1:end,1)); % This solution is faster but doesn't give the same result as result1 

dataArray эквивалентно:

dataArray = [0 0; 0 2; 0 4; 0 6; 1 0; 1 2; 1 4; 1 6; 2 0; 2 2; 2 4; 2 6]; % This is a small array, but in my case there are usually over 10 000 lines. 

Таким образом, в этом случае, result1 равно [1; 2] и result2 равно [0; 1; 2]. Функция unique работает быстрее, но я не хочу 0 для рассмотрения. Есть ли способ сделать это с unique и не считать 0 уникальным значением? Есть ли другая альтернатива?

EDIT

Я хотел время различных решений.

clc 
dataArray = floor(10*rand(10e3,10)); 
dataArray(mod(dataArray(:,1),3)==0)=0; 
% Initial 
tic 
for ii = 1:10000 
    FCT1 = setxor(0, dataArray(:,1)); 
end 
toc 
% My solution 
tic 
for ii = 1:10000 
    FCT2 = unique(dataArray(dataArray(:,1)>0,1)); 
end 
toc 
% Pursuit solution 
tic 
for ii = 1:10000 
    FCT3 = unique(dataArray(:, 1)); 
    FCT3(FCT3==0) = []; 
end 
toc 
% Pursuit solution with chappjc comment 
tic 
for ii = 1:10000 
    FCT32 = unique(dataArray(:, 1)); 
    FCT32 = FCT32(FCT32~=0); 
end 
toc 
% chappjc solution 
tic 
for ii = 1:10000 
    FCT4 = setdiff(unique(dataArray(:,1)),0); 
end 
toc 
% chappjc 2nd solution 
tic 
for ii = 1:10000 
    FCT5 = find(accumarray(dataArray(:,1)+1,1))-1; 
    FCT5 = FCT5(FCT5>0); 
end 
toc 

И результаты:

Elapsed time is 5.153571 seconds. % FCT1 Initial 
Elapsed time is 3.837637 seconds. % FCT2 My solution 
Elapsed time is 3.464652 seconds. % FCT3 Pursuit solution 
Elapsed time is 3.414338 seconds. % FCT32 Pursuit solution with chappjc comment 
Elapsed time is 4.097164 seconds. % FCT4 chappjc solution 
Elapsed time is 0.936623 seconds. % FCT5 chappjc 2nd solution 

Однако решение с sparse и accumarray работает только с integer. Эти решения не будут работать с double.

Answer 1

Вот дурацкое предложение с accumarray, демонстрируется с использованием тестовых данных Флориса:

a = floor(10*rand(100000, 1)); a(mod(a,3)==0)=0; 
result = find(accumarray(nonzeros(a(:,1))+1,1))-1; 

Благодаря Луис Mendo для указывая, что с nonzeros, не обязательно выполнять result = result(result>0)!

Обратите внимание, что это решение требует целочисленных данных (не обязательно целочисленного типа данных, но только не с десятичными компонентами). Сравнивая значения с плавающей запятой для равенства, как это делает unique, опасно. См. here и here.

---

Оригинальное предложение: зерноуборочный unique с setdiff:

result = setdiff(unique(a(:,1)),0) 

Или удалить с логической индексации после unique:

result = unique(a(:,1)); 
result = result(result>0); 

Я вообще предпочитаю не назначать [] как в (result(result==0)=[];), т.к. он становится очень неэффективным для больших наборов данных.

Удаление нулей после unique должны быть быстрее, так как он работает на меньше данных (если каждый элемент не является уникальным, или если a/dataArray очень мало).

Answer 2

Почему бы не убрать нули в качестве второго шага:

result2 = unique(.....); 
result2 = (result2~=0); 

Answer 3

Я также нашел еще один способ сделать это:

result2 = unique(dataArray(dataArray(:,1)>0,1)); 

Answer 4

Просто, чтобы добавить к общему шуму - вот три различных метода. Все они дают один и тот же ответ, но немного разные тайминги:

a = floor(10*rand(100000, 1)); 
a(mod(a,3)==0)=0; 
tic 
b1 = unique(a(:,1)); 
b1(b1==0) = []; 
toc 
tic 
b2 = find(sparse(a(:,1)+1, 1, 1)) - 1; 
b2(b2==0)=[]; 
toc 
tic 
b3 = setxor(0, a(:, 1), 'rows'); 
toc 

display(b1) 
display(b2) 
display(b3) 

На моей машине, тайминги (для массива 100000 элементов) были следующими:

0.0087 s - for unique 
0.0142 s - for find(sparse) 
0.0302 s = for setxor 

Я всегда как sparse для проблема такая: вы получаете количество элементов одновременно с их уникальными значениями.

EDIT за предложение @ chappj. Я добавил четвертый вариант

b4 = find(accumarray(a(:,1)+1,1)-1); 
b4(b4==0) = []; 

Время:

0.0029 s , THREE TIMES FASTER THAN UNIQUE 

Дамы и господа, у нас есть победитель.

ПОСЛЕСЛОВИЕ индекс на основе методов (sparse и accumarray) работать только с целочисленными входами (хотя они могут быть double типа). Это казалось ОК на основе входного массива, заданного в вопросе, но не работает для нецелочисленных значений. Конечно, unique - это сложная концепция, когда у вас есть двойники - число, которое «выглядит» одинаково, может быть представлено по-разному. Вы можете усечь входной массив (дезинфицировать данные), чтобы убедиться, что это не проблема. Например, если вы сделали

a = 0.001 * double(int(a * 1000)); 

Вы бы округлить все значения не более чем на 3 значащих цифр, а потому, что вы пошли «через Int» вы уверены, что вы не до конца со значениями, которые являются " очень тонко отличается "(например, в восьмой цифре или выше). Конечно, в этом случае вы могли бы также сделать

a = round(a * 1000); 
mina = min(a(:)); 
b = find(accumarray(a - mina + 1, 1)) + mina - 1; 
b = 0.001 * b(b ~= 0); 

Это «довольно надежный» для нецелых значений (в вышеприведенном случае он обрабатывает значения с использованием до трех значащих цифр, если вам нужно больше, необходимое пространство в конечном итоге будет слишком большим, и этот метод будет медленнее, чем unique, который на самом деле должен сортировать данные.)