MATLAB中稳定的accumarray

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

如果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

- knedlsepp

Answer 1

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

SORTROWS使用了一个稳定版本的快速排序算法。

由于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所建议的那样，可以通过生成下标的线性索引来使用sort而不是sortrows。

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

- knedlsepp

---

将索引反转后再输入到 sortrows 中是必要的，这样排序才能按线性索引的方式进行，对吧？也许你可以在你的回答中加上这一点。 - Luis Mendo

@LuisMendo：我也是这么想的，但是我们需要先使用max找出矩阵的维度，我觉得这会增加不必要的复杂性。我会尝试一下。 - knedlsepp

是的，匿名函数比较慢。此外，你可以去掉那些“-1”和“+1”来稍微提高一下性能。http://ideone.com/hUNzqV - Luis Mendo

@LuisMendo：我会添加第二个版本。看起来这似乎与我正在测试的 fun = @(x)x(end) 有关，由于某种原因，它比版本1慢得多... 我们应该使用一个测试用例，其中 fun~=sum，否则稳定的东西根本没有任何意义。 - knedlsepp

现在我看到你的关于不使用sum的评论是错的 :-) 所以我们认为稳定性对于“非标准”函数是有意义的。 - Luis Mendo