基于起始值和结束值创建索引向量

Question

基于一个包含起始索引（第一列）和结束索引（第二列）区间的矩阵，我希望创建一个所有索引的向量。例如，如果 A=[2 4; 8 11 ; 12 16]，那么我想得到以下向量 index = [2 3 4 8 9 10 11 12 13 14 15 16]。

我正在寻找最快的方法来实现这个目标。目前，我只发现两种可能性：

1）使用循环

index = [];
for n = 1:size(A, 1)
    index = [index A(n, 1):A(n, 2)];
end

2) 使用arrayfun

index = cell2mat(arrayfun(@(n) A(n, 1):A(n, 2), 1:size(A, 1), 'uni', 0));

有趣的是，arrayfun 比循环版本快得多，我不知道为什么。而且我使用了从单元格到 mat 的转换，所以这很奇怪。你对此有什么想法吗？你有其他建议吗？

感谢你的帮助。

- andrew_077

---

抱歉，我犯了一个错误，向量索引应该是 [2 3 4 8 9 10 11 12 13 14 15 16]。 - andrew_077

"arrayfun"只是一个循环的封装器，它之所以更快，只是因为你在循环版本中没有预先分配内存，所以在每次迭代中都会进行一些（缓慢的）内存分配。 - Andras Deak -- Слава Україні

@Divakar，你的重复答案似乎没有给出正确的结果。 - Robert Seifert

@thewaywewalk 啊谢谢，确实是个bug！现在应该已经修复了。 - Divakar

欢迎来到 StackOverflow！请考虑通过点击左侧的绿色勾号接受其中一个答案来告知系统您的问题已解决。谢谢！ - Robert Seifert

Answer 1

难以确定速度有多快，但至少没有循环：

A = [1,3;11,13;31,33;41,42;51,54;55,57;71,72];

%// prepare A
A = A.';

%// create index matrix
idx = bsxfun(@plus, A, [0; 1]);
%// special case: 54 and 55 are basically superfluous
%// need to be removed, but 71 and 72 shouldn't
A = A(:); 
dA = diff(A); dA(1:2:end) = 0;
idx = idx(~( [0;dA] == 1 | [dA;0] == 1 ));

%// create mask
mask = zeros(max(A),1);
mask(idx(:)) = (-1).^(0:numel(idx)-1);

%// index vector
out = find(cumsum(mask))

---

out.' =

      1  2  3 11 12 13 31 32 33 41 42 51 52 53 54 55 56 57 71 72

- Robert Seifert

---

非常好！写idx = [A(1,:); A(2,:)+1]比调用bsxfun简单/快速得多，不是吗？另外，在infex中有一个小错别字，并且out是列向量。 - EBH

@EBH 我认为 idx = [A(1,:); A(2,:)+1] 更简单，但速度可能会更慢。out 是一个列向量，确实，我只是为了显示目的将其转置了。 - Robert Seifert

您的解决方案生成了部分结果，请使用A=[1, 3;11,15;21,25;31,33;41,48; 51,54;61,67;71,72;81,82;91,94];进行测试。 - rahnema1

@thewaywewalk 看起来可行！已加入基准测试。 - rahnema1

Answer 2

这里是一些方法的集合：

方法1 来自 https://stackoverflow.com/a/39422485/6579744 ：

lo = A(:,1);
up=A(:,2);
index=cumsum(accumarray(cumsum([1;up(:)-lo(:)+1]),[lo(:);0]-[0;up(:)]-1)+1);
index= index(1:end-1);

方法2：这个方法来自https://dev59.com/Z5nga4cB1Zd3GeqPUCE1#38507276。我也提供了相同的答案，但因为Divakar的答案在我的之前，他的（修改后的）答案被优先选择：

start_idx = A(:,1)';
end_idx = A(:,2)';
lens = end_idx - start_idx + 1;
shift_idx = cumsum(lens(1:end-1))+1;
id_arr = ones(1,sum(lens));
id_arr([1 shift_idx]) = [start_idx(1) start_idx(2:end) - end_idx(1:end-1)];
index = cumsum(id_arr);

方法3：这是我的。

N = A(:,2) - A(:,1) +1;
s=cumsum([ 1; N]);
index=(1:s(end)-1) -repelem(s(1:end-1),N) + repelem(A(:,1),N);
%octave    index=(1:s(end)-1) -repelems(s(1:end-1),[1:numel(N);N']) + repelems(A(:,1),[1:numel(N);N']);

方法四：本主题的另一个答案，来自thewaywewalk

A = A.';
idx = bsxfun(@plus, A, [0; 1]);
A = A(:); 
dA = diff(A); dA(1:2:end) = 0;
idx = idx(~( [0;dA] == 1 | [dA;0] == 1 ));
mask = zeros(max(A),1);
mask(idx(:)) = (-1).^(0:numel(idx)-1);
index = find(cumsum(mask));

方法5：您的第二种方法：

index = cell2mat(arrayfun(@(n) A(n, 1):A(n, 2), 1:size(A, 1), 'uni', 0));

方法六 来自 https://stackoverflow.com/a/39423102/6579744 ：

sz= size(A, 1);
index_c = cell(1,sz);
for n = 1:sz
    index_c{n} = [A(n, 1):A(n, 2)];
end
index = cell2mat(index_c);

Method 7 只适用于Octave：

idx = 1:size(A ,1);
index_a =bsxfun(@(a,b) (a(b):A (b,2))',A (:,1),idx);
index = index_a(index_a ~= 0); 

方法八：你的第一种方法：

index = [];
for n = 1:size(A, 1)
    index = [index A(n, 1):A(n, 2)];
end

测试数据：

i= 1:500:10000000;
j= i+randi([1 490],1, numel(i));
A = [i', j'];

结果在Octave中进行了测试，在Matlab中可能会有所不同

method1: 0.077063 seconds
method2: 0.094579 seconds
method3: 0.145004 seconds
method4: 0.180826 seconds
method5: 0.317095 seconds
method6: 0.339425 seconds
method7: 3.242287 seconds
method8: doesn't complete in 15 seconds

用于基准测试的代码在在线演示中。

- rahnema1

---

你的基准测试代码是什么？ - Robert Seifert

@thewaywewalk 在在线演示中 http://rextester.com/SGFWGE11375 - rahnema1