数组元素的重复拷贝：matlab中的游程解码

Question

数组元素的重复拷贝：matlab中的游程解码我试图使用“值”数组和“计数器”数组向数组中插入多个值。例如，如果：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以及奔跑的长度，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并将“适当”值放置在零数组的“key”位置，以便在“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 = c
umsum(runlens)% Initalize zeros arrayarray = zeros(1,(clens(end)))% Find key positions/indiceskey_pos = [1 clens(1:end-1)+1]% Find appro
priate valuesapp_vals = diff([0 vals])% Map app_values at key_pos on arrayarray(pos) = app_vals% cumsum array for final outputoutput = cum
sum(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 = cu
msum(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 benchm
arkedfor 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);
    endendfigure,      % Plot runtimesloglog(datasizes,tsec(1,:),'-bo'), hold onloglog(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 speedupssemilogx(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方法，这是关于3x!

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

嗯，原因的本质在于cumsum-only需要将“累计”值映射到vals..在新的cumsum+diff基于方法，我们正在做diff(vals)相反，matlab只对其进行处理。n元素(其中n是运行长度的数目)与sum(runLengths)的元素数。cumsum-only接近时，这个数字必须是这个数字的许多倍。n因此，这一新方法的显著加速！

Answer 2

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

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]

---

编辑：为了完整起见是另一种选择阿瑞芬，但是这似乎需要花费20到100倍的时间才能运行到上面的向量长达10，000个元素的解决方案：

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