在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.

我们如何实现 stable的稳定版本，它没有此限制，但可以保证子集采用与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屋！