时间序列聚合效率

Question

我通常需要用给定的聚合函数(即求和,平均等)来总结具有不规则定时的时间序列.但是,我目前的解决方案似乎效率低,速度慢.

采取聚合功能:

function aggArray = aggregate(array, groupIndex, collapseFn)

groups = unique(groupIndex, 'rows');
aggArray = nan(size(groups, 1), size(array, 2));

for iGr = 1:size(groups,1)
    grIdx = all(groupIndex == repmat(groups(iGr,:), [size(groupIndex,1), 1]), 2);
    for iSer = 1:size(array, 2)
      aggArray(iGr,iSer) = collapseFn(array(grIdx,iSer));
    end
end

end

请注意这两个array和groupIndex可2D.每个列array都是要聚合的独立系列,但groupIndex应将这些列合在一起(作为一行)以指定句点.

然后当我们给它带来一个不规则的时间序列时(注意第二个周期是一个基本周期更长),时间结果很差:

a = rand(20006,10);
b = transpose([ones(1,5) 2*ones(1,6) sort(repmat((3:4001), [1 5]))]);

tic; aggregate(a, b, @sum); toc
Elapsed time is 1.370001 seconds.

使用分析器,我们可以发现该grpIdx行大约占执行时间的1/4(.28秒),iSer循环大约需要3/4(1.17秒)的总时间(1.48秒).

将此与期间无关紧要的情况相比较:

tic; cumsum(a); toc
Elapsed time is 0.000930 seconds.

有没有更有效的方法来聚合这些数据？

---

时间结果

将每个响应放在一个单独的函数中,以下是我timeit使用Intel i7在Windows 7上使用Matlab 2015b 获得的时序结果:

    original | 1.32451
      felix1 | 0.35446
      felix2 | 0.16432
    divakar1 | 0.41905
    divakar2 | 0.30509
    divakar3 | 0.16738
matthewGunn1 | 0.02678
matthewGunn2 | 0.01977

澄清 groupIndex

2D的一个例子groupIndex是为1980 - 2015年的一组日常数据指定年份编号和周数:

a2 = rand(36*52*5, 10);
b2 = [sort(repmat(1980:2015, [1 52*5]))' repmat(1:52, [1 36*5])'];

因此,"年 - 周"期间由一行唯一标识groupIndex.这是通过调用unique(groupIndex, 'rows')和获取第三个输出来有效处理的,所以可以随意忽略这部分问题.

Answer 1

方法#1

您可以创建对应的面具grIdx在所有 groups一气呵成用bsxfun(@eq,..).现在,collapseFn因为@sum,你可以引入matrix-multiplication,因此有一个完全矢量化的方法,像这样 -

M = squeeze(all(bsxfun(@eq,groupIndex,permute(groups,[3 2 1])),2))
aggArray = M.'*array

对于collapseFn作为@mean,你需要做更多的工作,如下所示-

M = squeeze(all(bsxfun(@eq,groupIndex,permute(groups,[3 2 1])),2))
aggArray = bsxfun(@rdivide,M,sum(M,1)).'*array

方法#2

如果您正在使用泛型collapseFn,则可以使用使用M先前方法创建的2D掩码来索引行array,从而将复杂度从更改O(n^2)为O(n).一些快速测试表明,这可以比原始的loopy代码提供明显的加速.这是实施 -

n = size(groups,1);
M = squeeze(all(bsxfun(@eq,groupIndex,permute(groups,[3 2 1])),2));
out = zeros(n,size(array,2));
for iGr = 1:n
    out(iGr,:) = collapseFn(array(M(:,iGr),:),1);
end

请注意,1in collapseFn(array(M(:,iGr),:),1)表示collapseFn将应用的尺寸,因此在1那里必不可少.

奖金

通过它的名称groupIndex似乎可以保存整数值,通过将每一行视为索引元组并因此将每行转换为标量并最终获得1D数组版本,可以滥用它来更高效地M创建.这必须更高效,因为现在数据量.这可以用于本文中列出的所有方法.所以,我们会这样 -groupIndexgroupIndexgroupIndex0(n)MM

dims = max(groupIndex,[],1);
agg_dims = cumprod([1 dims(end:-1:2)]);
[~,~,idx] = unique(groupIndex*agg_dims(end:-1:1).'); %//'

m = size(groupIndex,1);
M = false(m,max(idx));
M((idx-1)*m + [1:m]') = 1;

Answer 2

Mex功能1

HAMMER TIME:用于粉碎它的Mex功能:使用问题原始代码的基本案例测试在我的机器上花了1.334139秒.恕我直言,来自@Divakar的第二快答案是:

groups2 = unique(groupIndex); 
aggArray2 = squeeze(all(bsxfun(@eq,groupIndex,permute(groups,[3 2 1])),2)).'*array; 

经过的时间是0.589330秒.

那我的MEX功能:

[groups3, aggArray3] = mg_aggregate(array, groupIndex, @(x) sum(x, 1));

经过时间为0.079725秒.

测试我们得到相同的答案:norm(groups2-groups3)返回0和norm(aggArray2 - aggArray3)返回2.3959e-15.结果也符合原始代码.

用于生成测试条件的代码:

array = rand(20006,10);
groupIndex = transpose([ones(1,5) 2*ones(1,6) sort(repmat((3:4001), [1 5]))]);

对于纯粹的速度,去mex.如果编译c ++代码/复杂性的想法太痛苦了,那就去看Divakar的答案吧.另一个免责声明:我没有对我的功能进行强有力的测试.

Mex方法2

有点令我惊讶的是,在某些情况下,此代码看起来比完整的Mex版本更快(例如,在此测试中花费约0.05秒).它使用mex函数mg_getRowsWithKey来计算组的索引.我想这可能是因为我在完整的mex函数中复制的数组并不像调用'feval'那样快和/或开销.它与其他版本的算法复杂度基本相同.

[unique_groups, map] = mg_getRowsWithKey(groupIndex);

results = zeros(length(unique_groups), size(array,2));

for iGr = 1:length(unique_groups)
   array_subset             = array(map{iGr},:);

   %// do your collapse function on array_subset. eg.
   results(iGr,:)           = sum(array_subset, 1);
end

当您array(groups(1)==groupIndex,:)提取与完整组关联的数组条目时,您正在搜索groupIndex的整个长度.如果你有数百万行输入,这将完全糟糕.array(map{1},:)效率更高.

仍有不必要的内存复制和与在崩溃函数上调用'feval'相关的其他开销.如果您在c ++中有效地实现聚合器功能以避免复制内存,则可能实现另外2倍的加速.

Answer 3

聚会晚了一点，但是使用一个循环accumarray就产生了很大的不同：

function aggArray = aggregate_gnovice(array, groupIndex, collapseFn)

  [groups, ~, index] = unique(groupIndex, 'rows');
  numCols = size(array, 2);
  aggArray = nan(numel(groups), numCols);
  for col = 1:numCols
    aggArray(:, col) = accumarray(index, array(:, col), [], collapseFn);
  end

end

使用timeitMATLAB R2016b中的时间对此问题中的示例数据进行计时：

original | 1.127141
 gnovice | 0.002205

加速超过500倍！