重复数组元素的副本：MATLAB中的运行长度解码

Question

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

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.

Answer 1

问题陈述

我们有一系列的值， vals 和runlength， 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 并将“适当”值放在零数组上的“键”位置，以便之后”cumsum“应用了，我们最终将重复一系列 vals 的 runlens 时代。

脚步： 让我们编号上述步骤，以使预期方法更容易：

1）初始化零数组：长度必须是多少？由于我们正在重复 runlens 时间，零阵列的长度必须是所有的总和 runlens.

2）查找关键位置/指数：现在，这些关键位置是沿零数组的位置 vals 开始重复。因此，是 runlens = [2,2,1,3], ，映射到零数组的钥匙位置将是：

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

3）找到适当的值：使用之前要锤击的最终指甲 cumsum 将把“适当的”值放入这些关键位置。现在，因为我们会做 cumsum 不久之后，如果您仔细考虑，您将需要一个 differentiated 版本的 values 和 diff, ， 以便 cumsum 那会 带回来 values. 。由于这些差异值将放置在零阵列上的位置 runlens 距离，使用后 cumsum 我们每个 vals 元素重复 runlens 作为最终输出的时间。

解决方案代码

这是实现上述所有步骤 -

% 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)

分配前黑客

可以看出，以上列出的代码使用零的前分配。现在，据此 无证件的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 与映射相比 sum(runLengths) 元素的数量 cumsum-only 方法和这个数字必须比 n 因此，采用这种新方法的明显加速！

Answer 2

基准

更新了R2015B: repelem 现在最快的所有数据尺寸。

---

测试功能：

1. Matlab的内置 repelem R2015A中添加的功能
2. gnovice的 cumsum 解决方案 （rld_cumsum)
3. Divakar的 cumsum+diff 解决方案 （rld_cumsum_diff)
4. 纳德尔斯普的 accumarray 解决方案 （knedlsepp5cumsumaccumarray） 从 这个帖子
5. 基于天真循环的实现（naive_jit_test.m）测试即时编译器

结果 test_rld.m 在R2015上b:

使用R2015的旧计时图一个 这里.

发现:

• repelem 始终是最快的，大约是2倍。
• rld_cumsum_diff 始终比 rld_cumsum.
• repelem 对于小数据尺寸（小于300-500个元素）来说，最快的是最快的）
• rld_cumsum_diff 变得比 repelem 大约5000个元素
• repelem 变得比慢 rld_cumsum 在30 000到300 000个元素之间
• rld_cumsum 与表现大致相同 knedlsepp5cumsumaccumarray
• naive_jit_test.m 几乎持续的速度，并且与 rld_cumsum 和 knedlsepp5cumsumaccumarray 对于较小的尺寸，大尺寸的速度更快

使用R2015的旧费率图一个 这里.

结论

利用 repelem 以下约5000个元素 cumsum+diff 上方解决方案.

Answer 3

我知道没有内置功能，但是这里有一个解决方案：

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, ，但这似乎比上述溶液长20-100倍，最多10,000个元素：

c = arrayfun(@(x,y) x.*ones(1,y),a,b,'UniformOutput',false);
c = [c{:}];

Answer 4

终于有（就像 R2015A）一个内置和记录的功能来执行此操作， repelem. 。以下语法，其中第二个参数是向量，在这里很重要：

W = repelem(V,N), ，与矢量 V 和向量 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

Answer 5

MATLAB内置的性能问题 repelem 从R2015B开始固定。我已经运行了 test_rld.m ChappJC在R2015B的帖子中的程序，以及 repelem 现在，比其他算法要快于另一个因素2：