当前位置：文江博客话题详情

数组元素的重复副本：MATLAB 中的游程解码

发布于 2024-08-15 20:17:49 字数 463 浏览 13 评论 0 原文

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

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()”的变体，但没有成功。

这基本上是运行长度编码。

原文

I'm trying to insert multiple values into an array using a 'values' array and a 'counter' array. For example, if:

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

I want the output of some function

c=somefunction(a,b)

to be

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

Where a(1) recurs b(1) number of times, a(2) recurs b(2) times, etc...

Is there a built-in function in MATLAB that does this? I'd like to avoid using a for loop if possible. I've tried variations of 'repmat()' and 'kron()' to no avail.

This is basically Run-length encoding.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

难如初 2024-08-22 20:17:49

问题陈述

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

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

我们需要重复 vals 中的每个元素乘以运行透镜。因此，最终输出将是：

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

预期方法

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

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

步骤：让我们对上述步骤进行编号，以便为预期方法提供更简单的视角：

1）初始化零数组：长度必须是多少？由于我们重复 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，如果您仔细思考，您将需要 values 的差异化版本，其中diff，以便cumsum 这些将带回我们的价值观。由于这些差异值将放置在由 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 博客，人们可以实现更快的预分配-allocation with -

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 方法与其他< MATLAB 2014B 上基于 code>cumsum-only 的方法 -

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 方法的步骤，需要将“cumsumed”值映射到 vals。在基于 cumsum+diff 的新方法中，我们执行的是 diff(vals)，而 MATLAB 仅处理 n 个元素（其中 n 是runLengths 的数量）与 仅 cumsum 方法的 sum(runLengths) 元素映射数量相比，该数量必须比 多很多倍n 因此，这种新方法带来了显着的加速！

Problem Statement

We have an array of values, vals and runlengths, runlens:

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

We are needed to repeat each element in vals times each corresponding element in runlens. Thus, the final output would be:

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

Prospective Approach

One of the fastest tools with MATLAB is cumsum and is very useful when dealing with vectorizing problems that work on irregular patterns. In the stated problem, the irregularity comes with the different elements in runlens.

Now, to exploit cumsum, we need to do two things here: Initialize an array of zeros and place "appropriate" values at "key" positions over the zeros array, such that after "cumsum" is applied, we would end up with a final array of repeated vals of runlens times.

Steps: Let's number the above mentioned steps to give the prospective approach an easier perspective:

1) Initialize zeros array: What must be the length? Since we are repeating runlens times, the length of the zeros array must be the summation of all runlens.

2) Find key positions/indices: Now these key positions are places along the zeros array where each element from vals start to repeat.
Thus, for runlens = [2,2,1,3], the key positions mapped onto the zeros array would be:

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

3) Find appropriate values: The final nail to be hammered before using cumsum would be to put "appropriate" values into those key positions. Now, since we would be doing cumsum soon after, if you think closely, you would need a differentiated version of values with diff, so that cumsum on those would bring back our values. Since these differentiated values would be placed on a zeros array at places separated by the runlens distances, after using cumsum we would have each vals element repeated runlens times as the final output.

Solution Code

Here's the implementation stitching up all the above mentioned steps -

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

Pre-allocation Hack

As could be seen that the above listed code uses pre-allocation with zeros. Now, according to this UNDOCUMENTED MATLAB blog on faster pre-allocation, one can achieve much faster pre-allocation with -

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

Wrapping up: Function Code

To wrap up everything, we would have a compact function code to achieve this run-length decoding like so -

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;

Benchmarking

Benchmarking Code

Listed next is the benchmarking code to compare runtimes and speedups for the stated cumsum+diff approach in this post over the other cumsum-only based approach on 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')

Associated function code for 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;

Runtime and Speedup Plots

Conclusions

The proposed approach seems to be giving us a noticeable speedup over the cumsum-only approach, which is about 3x!

Why is this new cumsum+diff based approach better than the previous cumsum-only approach?

Well, the essence of the reason lies at the final step of the cumsum-only approach that needs to map the "cumsumed" values into vals. In the new cumsum+diff based approach, we are doing diff(vals) instead for which MATLAB is processing only n elements (where n is the number of runLengths) as compared to the mapping of sum(runLengths) number of elements for the cumsum-only approach and this number must be many times more than n and therefore the noticeable speedup with this new approach!

回复收藏 0 原文

夏夜暖风 2024-08-22 20:17:49

基准

针对 R2015b 进行了更新：repelem 现在对于所有数据大小来说都是最快的。

测试过的函数：

MATLAB内置的 repelem R2015a gnovice 的 cumsum 解决方案中添加的函数
(rld_cumsum)
Divakar 的 cumsum+diff 解决方案 (rld_cumsum_diff)
knedlsepp 的 accumarray 解决方案 (knedlsepp5cumsumaccumarray）来自这篇文章
基于朴素循环的实现（< a href="https://gist.github.com/chappjc/b92dc0ffdd2366341c4b" rel="nofollow noreferrer">naive_jit_test.m) 来测试即时编译器

结果R2015 上的 test_rld.mb:

使用 R2015a 的旧时序图此处。

调查结果：

repelem 始终是最快的，大约是 2 倍。
rld_cumsum_diff 始终比 rld_cumsum 快。
~~repelem 对于小数据量（小于约 300-500 个元素）来说速度最快~~
~~rld_cumsum_diff 明显快于 repelem< /code> 大约 5 000 个元素~~
~~repelem 比 30 000 到 300 000 个元素之间的 rld_cumsum 慢~~
rld_cumsum< /code> 与 knedlsepp5cumsumaccumarray 的性能大致相同
naive_jit_test.m 具有几乎恒定的速度，与 rld_cumsum 和 knedlsepp5cumsumaccumarray 相当code> 对于较小的尺寸，对于大尺寸更快一点

使用 R2015a 的旧速率图此处。

结论

使用 repelem ~~下面大约 5 000 个元素和上面的 cumsum+diff 解决方案~~ 。

回复收藏 0 原文

合久必婚 2024-08-22 20:17:49

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

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< /a>，但这似乎比上面的解决方案（向量长度最多为 10,000 个元素）的运行时间长 20-100 倍：

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

There's no built-in function I know of, but here's one solution:

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

Explanation:

A vector of zeroes is first created of the same length as the output array (i.e. the sum of all the replications in b). Ones are then placed in the first element and each subsequent element representing where the start of a new sequence of values will be in the output. The cumulative sum of the vector index can then be used to index into a, replicating each value the desired number of times.

For the sake of clarity, this is what the various vectors look like for the values of a and b given in the question:

        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]

EDIT: For the sake of completeness, there is another alternative using ARRAYFUN, but this seems to take anywhere from 20-100 times longer to run than the above solution with vectors up to 10,000 elements long:

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

回复收藏 0 原文

十二 2024-08-22 20:17:49

最后（从 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

There is finally (as of R2015a) a built-in and documented function to do this, repelem. The following syntax, where the second argument is a vector, is relevant here:

W = repelem(V,N), with vector V and vector N, creates a vector W where element V(i) is repeated N(i) times.

Or put another way, "Each element of N specifies the number of times to repeat the corresponding element of V."

Example:

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

回复收藏 0 原文