在MATLAB中稳定准确

Question

MATLAB的内置函数accumarray接受函数fun作为第四个参数.

A = accumarray(subs,val,sz,fun);

这适用fun于val具有相同下标的元素的每个子集subs.但文件说明:

如果下标subs未按其线性索引排序,则fun不应取决于其输入数据中值的顺序.

我们如何实现一个没有这个限制的稳定版本accumarray,但是会保证子集采用与给定的相同的顺序val？

例:

subs = [1:10,1:10];
val = 1:20;
accumarray(subs(:), val(:), [], @(x)x(end)).'

这样做的预计产出将是11:20,如果accumarray是稳定的.实际上输出是:

ans =
    11    12    13    14     5     6     7    18    19    20

我们的实施应该产生:

accumarrayStable(subs(:), val(:), [], @(x)x(end)).'`
ans =
    11    12    13    14    15    16    17    18    19    20

Answer 1

我们可以使用它sortrows作为预处理步骤来首先对索引和相应的值进行排序,正如其文档所述:

SORTROWS使用稳定版本的quicksort.

因为下标subs应该根据它们的线性索引进行排序,我们需要按照反向词典顺序对它们进行排序.这可以通过在使用之前和之后翻转列排序来实现sortrows.

这为我们提供了以下稳定版本的代码accumarray:

function A = accumarrayStable(subs, val, varargin)
[subs(:,end:-1:1), I] = sortrows(subs(:,end:-1:1));
A = accumarray(subs, val(I), varargin{:});

替代方案:

正如路易斯·门多所建议的那样,代替sortrows人也可以从下标中生成线性索引并使用sort.

function A = accumarrayStable(subs, val, varargin)
if numel(varargin)>0 && ~isempty(varargin{1})
    sz = varargin{1};
else
    sz = max(subs,[],1);
end
[~, I] = sort(subs*cumprod([1,sz(1:end-1)]).');
A = accumarray(subs(I,:), val(I), sz, varargin{:});

请注意,我们应该1+(subs-1)*cumprod([1,sz(1:end-1)]).'用于转换为线性索引.我们离开了+1,并-1作为的结果sort仍然会是相同的; 这节省了几个周期.

以上哪种解决方案更快将取决于您的机器和MATLAB版本.您可以通过以下方式测试:

A = randi(10, 1e4, 5); 
timeit(@()accumarrayStable(A(:,1:end-1), A(:,end), [], @(x)x(1))