Я хотел бы предложить еще одну идею, которая имеет некоторые Concep tual сходство с erfan's. Моя идея использует hash functions, и, в частности, GetMD5 FEX submission.
Основная задача - «уменьшить» каждую строку в A до единственного репрезентативного значения (например, символьного вектора), а затем найти уникальные записи этого вектора.
Судя по эталону противдругие предложения, мой ответ не работает так же хорошо, как один из альтернатив, но я думаю, что его raison d'être заключается в том, что он полностью агрегирован по типу данных (в пределах ограничений GetMD5 ), что алгоритм очень понятен, это замена взамен, поскольку он работает на A и что результирующий массив точно равен тому, который получен исходным методом. Конечно, для этого требуется, чтобы компилятор работал и имел риск возникновения хеш-коллизий (что может повлиять на результат в ОЧЕНЬ ОЧЕНЬ редких случаях).
Здесь приведены результаты типичного прогона на моем компьютере, а затем код:
Original method timing: 8.764601s
Dev-iL's method timing: 0.053672s
erfan's method timing: 0.481716s
rahnema1's method timing: 0.009771s
function q39955559
G=[0 -1 1; 0 -1 2; 0 -1 3; 0 -1 4; 0 -1 5; 1 -1 6; 1 0 6; 1 1 6; 2 -1 6; 2 0 6; 2 1 6; 3 -1 6; 3 0 6; 3 1 6];
h=7;
M=reshape(G(nchoosek(1:size(G,1),h),:),[],h,size(G,2));
A=cell(size(M,1),2);
for p=1:size(M,1)
A{p,1}=squeeze(M(p,:,:));
left=~ismember(G, A{p,1}, 'rows');
A{p,2}=G(left,:);
end
%% Benchmark:
tic
A1 = orig_sort(A);
fprintf(1,'Original method timing:\t\t%fs\n',toc);
tic
A2 = hash_sort(A);
fprintf(1,'Dev-iL''s method timing:\t\t%fs\n',toc);
tic
A3 = erfan_sort(A);
fprintf(1,'erfan''s method timing:\t\t%fs\n',toc);
tic
A4 = rahnema1_sort(G,h);
fprintf(1,'rahnema1''s method timing:\t%fs\n',toc);
assert(isequal(A1,A2))
assert(isequal(A1,A3))
assert(isequal(numel(A1),numel(A4))) % This is the best test I could come up with...
function out = hash_sort(A)
% Hash the contents:
A_hashed = cellfun(@GetMD5,A,'UniformOutput',false);
% Sort hashes of each row:
A_hashed_sorted = A_hashed;
for ind1 = 1:size(A_hashed,1)
A_hashed_sorted(ind1,:) = sort(A_hashed(ind1,:));
end
A_hashed_sorted = cellstr(cell2mat(A_hashed_sorted));
% Find unique rows:
[~,ia,~] = unique(A_hashed_sorted,'stable');
% Extract relevant rows of A:
out = A(ia,:);
function A = orig_sort(A)
%To find equivalent rows up to order I use a double loop (VERY slow).
indices=[];
for j=1:size(A,1)
if ismember(j,indices)==0 %if we have not already identified j as a duplicate
for i=1:size(A,1)
if i~=j
if (isequal(A{j,1},A{i,1}) || isequal(A{j,1},A{i,2}))...
&&...
(isequal(A{j,2},A{i,1}) || isequal(A{j,2},A{i,2}))...
indices=[indices;i];
end
end
end
end
end
A(indices,:)=[];
function C = erfan_sort(A)
STR = cellfun(@(x) num2str((x(:)).'), A, 'UniformOutput', false);
[~, ~, id] = unique(STR);
IC = sort(reshape(id, [], size(STR, 2)), 2);
[~, col] = unique(IC, 'rows');
C = A(sort(col), :); % 'sort' makes the outputs exactly the same.
function A1 = rahnema1_sort(G,h)
idx = nchoosek(1:size(G,1),h);
%concatenate complements
M = [G(idx(1:size(idx,1)/2,:),:), G(idx(end:-1:size(idx,1)/2+1,:),:)];
%convert to cell so A1 is unique rows of A
A1 = mat2cell(M,repmat(h,size(idx,1)/2,1),repmat(size(G,2),2,1));
- Если более сложные типы данных должны быть hashed, вместо этого можно использовать DataHash FEX submission, что несколько медленнее.
Hi! Вопрос не закончен. Вы добавили: «То, что я делаю в данный момент:«, у него нет части », и это не работает, потому что:« –
Спасибо, я добавил эту часть. – user3285148
Можете ли вы быть более наглядным? Я не знаю, что * до порядка k подкатегорий * означает, и я не могу вызвать его из кода. –