MATLAB 中的稳定 accumarray [英] Stable accumarray in MATLAB

问题描述

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

MATLAB's built-in function accumarray accepts a function fun as a fourth argument.

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

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

This applies fun to each subset of elements in val that have identical subscripts in subs. The documentation however states:

如果 subs 中的下标没有按照它们的线性索引排序，fun 不应该依赖于输入数据中值的顺序.

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?

How can we implement a stable version of accumarray, which doesn't have this limitation, but will guarantee that the subsets adopt the same order as given by val?

示例:

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

如果 accumarray 是稳定的，那么预期的输出将是 11:20.实际上输出是:

The expected output of this would be 11:20 if accumarray were stable. In fact the output is:

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

推荐答案

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

We can use sortrows as a preprocessing step to sort the indices and corresponding values first, as its documentation states:

SORTROWS 使用 稳定 版本的快速排序.

SORTROWS uses a stable version of quicksort.

由于subs中的下标应该按照它们的线性索引进行排序，所以我们需要按照逆字典顺序对它们进行排序.这可以通过在使用 sortrows 之前和之后翻转列顺序来实现.

As the subscripts in subs should be sorted with respect to their linear indices, we need to sort them in reverse lexicographic order. This can be achieved by flipping the column ordering before and after using sortrows.

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

This gives us the following code for a stable version of 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 代替.>

As suggested by Luis Mendo, instead of sortrows one could also generate the linear indices from the subscripts and use sort instead.

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 的结果仍然相同；这为我们节省了几个周期.

Note that we should be using 1+(subs-1)*cumprod([1,sz(1:end-1)]).' for the conversion to linear indices. We leave out the +1 and -1 as the result of sort will still be the same; which saves us a few cycles.

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

Which one of the above solutions is faster will depend on your machine and MATLAB version. You could test for example via:

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

这篇关于MATLAB 中的稳定 accumarray的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！