Frage Kumulierter Summenüberindex in MATLAB


Betrachten Sie die folgende Matrix, wobei die erste Spalte der Index ist, die zweite - Werte, die dritte - die kumulative Summe, die zurückgesetzt wird, sobald sich der Index ändert:

1     1     1     % 1   
1     2     3     % 1+2
1     3     6     % 3+3
2     4     4     % 4
2     5     9     % 4+5
3     6     6     % 6
3     7    13    % 6+7
3     8    21    % 13+8
3     9    30    % 21+9
4    10    10    % 10
4    11    21    % 10+11

Wie kann man in der dritten Spalte Schleifen vermeiden?

Ich versuche folgendes:

  A = [1 1;...                 % Input
       1 2;...
       1 3;...
       2 4;...
       2 5;...
       3 6;...
       3 7;...
       3 8;...
       3 9;...
       4 10;...
       4 11];
  CS = cumsum(A(:,2));         % cumulative sum over the second column

  I = [diff(data(:,1));0];     % indicate the row before the index (the first column)  
                               % changes
  offset=CS.*I;                % extract the last value of cumulative sum for a given 
                               % index

  offset(end)=[]; offset=[0; offset] %roll offset 1 step forward

  [A, CS, offset]

Das Ergebnis ist:

ans =

 1     1     1     0
 1     2     3     0
 1     3     6     0
 2     4    10     6
 2     5    15     0
 3     6    21    15
 3     7    28     0
 3     8    36     0
 3     9    45     0
 4    10    55    45
 4    11    66     0

So wäre das Problem gelöst worden, wenn es eine triviale Möglichkeit gäbe, die vierte Spalte der obigen Matrix zu transformieren

O =

 0
 0
 0
 6
 6
15
15
15
15
45
45

Da liefert CS-O die gewünschte Ausgabe.

Ich würde mich über Vorschläge freuen.


10
2017-09-25 17:46


Ursprung


Antworten:


Benutzen accumarray mit einer benutzerdefinierten Funktion:

result = accumarray(A(:,1), A(:,2), [], @(x) {cumsum(x)});
result = vertcat(result{:});

Dies funktioniert unabhängig davon, ob Indexänderungen um einen Schritt von 1 (wie in Ihrem Beispiel) durchgeführt wurden oder nicht.


Der folgende Ansatz ist schneller, da Zellen vermieden werden. Sehen Sie @ Divakars exzellentes Benchmarking in seine Antwort (und sehen Sie seine Lösung, die die schnellste ist):

  1. Wenn Indexänderungen immer einer Erhöhung um 1 entsprechen (wie in Ihrem Beispiel):

    last = find(diff(A(:,1)))+1; %// index of last occurrence of each index value
    result = A(:,2); %// this will be cumsum'd, after correcting for partial sums
    correction = accumarray(A(:,1), A(:,2)); %// correction to be applied for cumsum
    result(last) = result(last)-correction(1:end-1); %// apply correction
    result = cumsum(result); %// compute result
    
  2. Wenn der Indexwert sich um mehr als 1 ändern kann (d. H. Es können "übersprungene" Werte vorhanden sein), erfordert dies eine kleine Modifikation, die die Dinge etwas verlangsamt.

    last = find(diff(A(:,1)))+1; %// index of last occurrence of each index value
    result = A(:,2); %// this will be cumsum'd, after correcting for partial sums
    correction = accumarray(A(:,1), A(:,2), [], @sum, NaN); %// correction
    correction = correction(~isnan(correction)); %// remove unused values
    result(last) = result(last)-correction(1:end-1); %// apply correction
    result = cumsum(result);
    

5
2017-09-25 17:53



cumsum und diff basierte Methode und als solche könnte gut mit der Leistung sein -

%// cumsum values for the entire column-2
cumsum_vals = cumsum(A(:,2));

%// diff for column-1
diffA1 = diff(A(:,1));

%// Cumsum after each index
cumsum_after_each_idx = cumsum_vals([diffA1 ;0]~=0);

%// Get cumsum for each "group" and place each of its elements at the right place
%// to be subtracted from cumsum_vals for getting the final output
diffA1(diffA1~=0) = [cumsum_after_each_idx(1) ; diff(cumsum_after_each_idx)];

out = cumsum_vals-[0;cumsum(diffA1)];

Benchmarking

Wenn Sie Wert auf Leistung legen, hier sind einige Benchmarks gegen die anderen Lösungen basierend auf accumarray.

Benchmarking-Code (mit Kommentaren zur Kompaktheit entfernt) -

A = ..  Same as in the question

num_runs = 100000; %// number of runs

disp('---------------------- With cumsum and diff')
tic
for k1=1:num_runs
    cumsum_vals = cumsum(A(:,2));
    diffA1 = diff(A(:,1));
    cumsum_after_each_idx = cumsum_vals([diffA1 ;0]~=0);
    diffA1(diffA1~=0) = [cumsum_after_each_idx(1) ; diff(cumsum_after_each_idx)];
    out = cumsum_vals-[0;cumsum(diffA1)];
end
toc,clear cumsum_vals  diffA1 cumsum_after_each_idx out

disp('---------------------- With accumarray - version 1')
tic
for k1=1:num_runs
    result = accumarray(A(:,1), A(:,2), [], @(x) {cumsum(x)});
    result = vertcat(result{:});
end
toc, clear result

disp('--- With accumarray - version 2 (assuming consecutive indices only)')
tic
for k1=1:num_runs
    last = find(diff(A(:,1)))+1; %// index of last occurrence of each index value
    result = A(:,2); %// this will be cumsum'd, after correcting for partial sums
    correction = accumarray(A(:,1), A(:,2)); %// correction to be applied for cumsum
    result(last) = result(last)-correction(1:end-1); %// apply correction
    result = cumsum(result); %// compute result
end
toc, clear last result correction

disp('--- With accumarray - version 2 ( general case)')
tic
for k1=1:num_runs
    last = find(diff(A(:,1)))+1; %// index of last occurrence of each index value
    result = A(:,2); %// this will be cumsum'd, after correcting for partial sums
    correction = accumarray(A(:,1), A(:,2), [], @sum, NaN); %// correction
    correction = correction(~isnan(correction)); %// remove unused values
    result(last) = result(last)-correction(1:end-1); %// apply correction
    result = cumsum(result);
end
toc

Ergebnisse -

---------------------- With cumsum and diff
Elapsed time is 1.688460 seconds.
---------------------- With accumarray - version 1
Elapsed time is 28.630823 seconds.
--- With accumarray - version 2 (assuming consecutive indices only)
Elapsed time is 2.416905 seconds.
--- With accumarray - version 2 ( general case)
Elapsed time is 4.839310 seconds.

6
2017-09-25 18:16



Ihre Strategie ist tatsächlich, was ich getan habe. Ihr letzter Schritt könnte auf diese Weise erreicht werden: (Denken Sie jedoch daran, dass Ihr Ansatz fortlaufende Indizes voraussetzt. Sie können dies natürlich über ändern offset=[0; CS(1:end-1).*(diff(A(:,1))~=0)];, würde aber immer noch sortierte Indizes benötigen.)

I = find(offset);
idxLastI = cumsum(offset~=0);
hasLastI = idxLastI~=0; %// For the zeros at the beginning
%// Combine the above to the output
O = zeros(size(offset));
O(hasLastI) = offset(I(idxLastI(hasLastI)));
out = CS-O;

Dies sollte vergleichbar sein mit Divakarist es cumsum-diff Ansatz.


2
2018-02-05 10:58