matlab - MATLAB 中的稳定 accumarray

Question

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

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

这适用 fun val 中元素的每个子集在 subs 中具有相同的下标.然而，文档指出:

If the subscripts in subs are not sorted with respect to their linear indices, fun should not depend on the order of the values in its input data.

我们如何实现 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 uses a stable version of 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{:});

替代方案:

按照 Luis Mendo 的建议，而不是 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))