16

我正在尝试使用“值”数组和“计数器”数组将多个值插入到数组中。例如，如果：

a=[1,3,2,5]
b=[2,2,1,3]

我想要一些函数的输出

c=somefunction(a,b)

成为

c=[1,1,3,3,2,5,5,5]

其中 a(1) 重复 b(1) 次，a(2) 重复 b(2) 次，等等...

MATLAB中有没有内置函数可以做到这一点？如果可能，我想避免使用 for 循环。我尝试了 'repmat()' 和 'kron()' 的变体，但无济于事。

这基本上是Run-length encoding。

4

5 回答 5

21

问题陈述

我们有一个值数组vals和游程长度runlens：

vals     = [1,3,2,5]
runlens  = [2,2,1,3]

我们需要重复每个元素的vals次数runlens。因此，最终输出将是：

output = [1,1,3,3,2,5,5,5]

前瞻性方法

MATLAB 最快的工具之一cumsum在处理处理不规则模式的矢量化问题时非常有用。在所述问题中，不规则性来自 中的不同元素runlens。

现在，为了利用cumsum，我们需要在这里做两件事：初始化一个数组zeros并将“适当的”值放置在 zeros 数组上的“关键”位置，这样在应用“ cumsum”之后，我们将得到一个最终数组多次重复vals。runlens

步骤：让我们对上述步骤进行编号，以使前瞻性方法更容易理解：

1) 初始化 zeros 数组：长度必须是多少？由于我们重复runlens次数，所以 zeros 数组的长度必须是所有 的总和runlens。

2）查找关键位置/索引：现在这些关键位置是沿着 zeros 数组的位置，每个元素从vals开始到重复。因此，对于runlens = [2,2,1,3]，映射到 zeros 数组的关键位置将是：

[X 0 X 0 X X 0 0] % where X's are those key positions.

3）找到合适的值：在使用之前要敲打的最后一颗钉子是cumsum将“合适”的值放入那些关键位置。现在，由于我们很快就会这样做cumsum，如果您仔细考虑，您将需要一个withdifferentiated版本，以便在那些上带回我们的. 由于这些微分值将放置在由距离分隔的位置的 zeros 数组中，因此在使用后，我们将每个元素重复多次作为最终输出。valuesdiffcumsumvaluesrunlenscumsumvalsrunlens

解决方案代码

这是拼接所有上述步骤的实现 -

% Calculate cumsumed values of runLengths. 
% We would need this to initialize zeros array and find key positions later on.
clens = cumsum(runlens)

% Initalize zeros array
array = zeros(1,(clens(end)))

% Find key positions/indices
key_pos = [1 clens(1:end-1)+1]

% Find appropriate values
app_vals = diff([0 vals])

% Map app_values at key_pos on array
array(pos) = app_vals

% cumsum array for final output
output = cumsum(array)

预分配黑客

可以看出，上面列出的代码使用零预分配。现在，根据这个关于更快预分配的 UNDOCUMENTED MATLAB 博客，可以通过以下方式实现更快的预分配 -

array(clens(end)) = 0; % instead of array = zeros(1,(clens(end)))

总结：功能代码

总结一切，我们将有一个紧凑的函数代码来实现这种运行长度解码，如下所示 -

function out = rle_cumsum_diff(vals,runlens)
clens = cumsum(runlens);
idx(clens(end))=0;
idx([1 clens(1:end-1)+1]) = diff([0 vals]);
out = cumsum(idx);
return;

基准测试

基准代码

接下来列出的是基准测试代码，用于比较本文中所述cumsum+diff方法与其他cumsum-only基于方法的运行时和加速MATLAB 2014B-

datasizes = [reshape(linspace(10,70,4).'*10.^(0:4),1,[]) 10^6 2*10^6]; %
fcns = {'rld_cumsum','rld_cumsum_diff'}; % approaches to be benchmarked

for k1 = 1:numel(datasizes)
    n = datasizes(k1); % Create random inputs
    vals = randi(200,1,n);
    runs = [5000 randi(200,1,n-1)]; % 5000 acts as an aberration
    for k2 = 1:numel(fcns) % Time approaches  
        tsec(k2,k1) = timeit(@() feval(fcns{k2}, vals,runs), 1);
    end
end

figure,      % Plot runtimes
loglog(datasizes,tsec(1,:),'-bo'), hold on
loglog(datasizes,tsec(2,:),'-k+')
set(gca,'xgrid','on'),set(gca,'ygrid','on'),
xlabel('Datasize ->'), ylabel('Runtimes (s)')
legend(upper(strrep(fcns,'_',' '))),title('Runtime Plot')

figure,      % Plot speedups
semilogx(datasizes,tsec(1,:)./tsec(2,:),'-rx')        
set(gca,'ygrid','on'), xlabel('Datasize ->')
legend('Speedup(x) with cumsum+diff over cumsum-only'),title('Speedup Plot')

相关功能代码rld_cumsum.m：

function out = rld_cumsum(vals,runlens)
index = zeros(1,sum(runlens));
index([1 cumsum(runlens(1:end-1))+1]) = 1;
out = vals(cumsum(index));
return;

运行时和加速图

在此处输入图像描述

在此处输入图像描述

结论

所提出的方法似乎给我们带来了明显的加速cumsum-only，大约是3 倍！

为什么这种cumsum+diff基于新方法的方法比以前的方法更好cumsum-only？

好吧，原因的本质在于cumsum-only方法的最后一步，需要将“累积”值映射到vals. 在基于新cumsum+diff的方法中，我们正在做diff(vals)的是 MATLAB 仅处理n元素（其中 n 是 runLength 的数量），而不是sum(runLengths)该方法的元素数量的映射，cumsum-only并且该数量必须比该方法多很多倍n，因此这种新方法显着加速！

于 2015-03-16T14:26:44.037 回答
21

基准

为 R2015b 更新：repelem现在所有数据大小的速度最快。

测试功能：

  1. repelemMATLAB在 R2015a 中添加的内置函数
  2. 新手的cumsum解决方案 ( rld_cumsum)
  3. Divakar 的cumsum+diff解决方案 ( rld_cumsum_diff)
  4. knedlsepp 的accumarray解决方案（knedlsepp5cumsumaccumarray）来自这篇文章
  5. 天真的基于循环的实现 ( naive_jit_test.m) 来测试即时编译器

test_rld.mR2015 b的结果：

驱赶时间

此处使用 R2015的 旧时序图。

调查结果：

  • repelem总是最快的，大约是 2 倍。
  • rld_cumsum_diff始终比 快rld_cumsum。
  • repelem对于小数据量（小于约 300-500 个元素）最快
  • rld_cumsum_diff变得比repelem大约 5 000 个元素快得多
  • repelem变得比rld_cumsum30 000 到 300 000 个元素之间的某个地方慢
  • rld_cumsum具有大致相同的性能knedlsepp5cumsumaccumarray
  • naive_jit_test.m具有几乎恒定的速度，与较小的尺寸相当，rld_cumsum对于knedlsepp5cumsumaccumarray大尺寸的速度稍快一些

在此处输入图像描述

此处使用 R2015 a 的 旧利率图。

结论

使用repelem 低于约 5 000 个元素和上述cumsum+diff解决方案。

于 2015-03-16T18:14:40.340 回答
16

我知道没有内置函数，但这里有一个解决方案：

index = zeros(1,sum(b));
index([1 cumsum(b(1:end-1))+1]) = 1;
c = a(cumsum(index));

解释：

首先创建一个与输出数组长度相同的零向量（即 中所有复制的总和b）。然后将一个放在第一个元素中，每个后续元素都表示新值序列的开始将在输出中的位置。index然后可以使用向量的累积和来索引a，将每个值复制所需的次数。

a为了清楚起见，这是问题中给出的值的各种向量的样子b：

        index = [1 0 1 0 1 1 0 0]
cumsum(index) = [1 1 2 2 3 4 4 4]
            c = [1 1 3 3 2 5 5 5]

编辑：为了完整起见，还有另一种使用ARRAYFUN的替代方法，但这似乎比上述具有长达 10,000 个元素的解决方案的运行时间长 20-100 倍：

c = arrayfun(@(x,y) x.*ones(1,y),a,b,'UniformOutput',false);
c = [c{:}];
于 2009-12-29T17:34:02.913 回答
12

最终（从R2015a 开始）有一个内置且记录在案的函数来执行此操作，repelem. 以下语法，其中第二个参数是一个向量，在这里是相关的：

W = repelem(V,N)，使用 vectorV和 vector N，创建一个W元素V(i)重复N(i)次数的向量。

或者换一种说法，“ 的每个元素N指定重复 的对应元素的次数V。”

例子：

>> a=[1,3,2,5]
a =
     1     3     2     5
>> b=[2,2,1,3]
b =
     2     2     1     3
>> repelem(a,b)
ans =
     1     1     3     3     2     5     5     5
于 2014-12-10T23:31:34.623 回答
3

repelem自 R2015b 起，MATLAB 内置的性能问题已得到修复。我已经test_rld.m从 chappjc 在 R2015b 的帖子中运行程序，repelem现在比其他算法快大约 2 倍：

更新了比较不同方法的 repelem 执行时间的图 repelem 在 cumsum+diff 上的加速（大约 2 倍）

于 2015-12-02T19:40:38.750 回答