5

MATLAB の組み込み関数は、関数を 4 番目の引数としてaccumarray受け入れます。fun

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

これは、で同じ添え字を持つfunの要素の各サブセットに適用されます。ただし、ドキュメントには次のように記載されています。valsubs

の添え字subsが線形インデックスに関してソートされていない場合fun、入力データの値の順序に依存してはなりません。

この制限がなく、サブセットが によって与えられるのと同じ順序を採用することを保証するの安定したバージョンをどのように実装できますか?accumarrayval

例：

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
4

1 に答える 1

5

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で提案されているように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)]).'線形インデックスへの変換に使用する必要があることに注意してください。+1andを省略します。-1結果としてsortwill は同じです。これにより、数サイクル節約できます。

上記のソリューションのどれがより高速かは、マシンと MATLAB のバージョンによって異なります。たとえば、次の方法でテストできます。

A = randi(10, 1e4, 5); 
timeit(@()accumarrayStable(A(:,1:end-1), A(:,end), [], @(x)x(1))
于 2015-02-11T20:03:21.000 に答える