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)).'

如果 accumarray 稳定，预期的输出将是 11:20。实际上输出是：

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))

MATLAB 中的稳定 accumarray

Stable accumarray in MATLAB

matlab

stable-sort

accumarray