给定一个整数 n,我想得到如下向量。例如,如果n=3
,那么向量应该是[1,1,2,1,2,3]
,如果n=4
,那么向量应该是[1,1,2,1,2,3,1,2,3,4]
,等等。有没有简单的方法来做到这一点?谢谢。
问问题
137 次
4 回答
3
您可以使用此快速解决方案
w=ones(1,n*(n+1)/2);
w(1+cumsum(1:n-1))=-(0:n-2);
w=cumsum(w);
在我的机器上,Dennis 的解决方案是最快的n<=8
,但之后这种方法是最快的。
使用此基准测试代码:
n=2000;
N=1e6/n;
tic
for k=1:N
A = repmat((1 : n)', 1, n);
A = A(triu(ones(n)) ~= 0);
end
toc
tic
for k=1:N
w=ones(1,n*(n+1)/2);
w(1+cumsum(1:n-1))=-(0:n-2);
w=cumsum(w);
end
toc
tic
for k=1:N
%// Fast vector growing
v=[];
for t = 1:n
x = 1:t;
v(end+x) = x;
end
end
toc
为了n=4
Elapsed time is 5.688693 seconds.
Elapsed time is 3.576366 seconds.
Elapsed time is 1.878887 seconds.
为了n=8
Elapsed time is 2.985184 seconds.
Elapsed time is 1.851967 seconds.
Elapsed time is 1.834574 seconds.
为了n=100
Elapsed time is 1.084404 seconds.
Elapsed time is 0.352033 seconds.
Elapsed time is 2.502724 seconds.
为了n=1000
Elapsed time is 15.625361 seconds.
Elapsed time is 3.949131 seconds.
Elapsed time is 11.497764 seconds.
为了n=2000
Elapsed time is 29.940548 seconds.
Elapsed time is 7.649394 seconds.
Elapsed time is 22.846367 seconds.
于 2013-11-01T15:41:45.733 回答
2
这是一个使用“上三角矩阵”函数从完整序列的简单重复中选择所需条目的解决方案:
A = triu(repmat((1 : n)', 1, n));
A = A(A ~= 0)'
triu
将对角线以下的所有内容设置为零。这种方法只有在原始序列不包含零时才有效,这当然是针对1 : n
. 不过,更好的解决方案可能是将结果triu
仅用于索引:
A = repmat((1 : n)', 1, n);
A = A(triu(ones(n)) ~= 0);
这非常快,在我的机器上 n = 10,000 的运行时间低于 1 秒。
正如 Dennis Jaheruddin 指出的那样,这种方法暂时需要的内存比结果所需的内存少两倍(精确因子是 2 n / (n + 1))。
于 2013-11-01T14:04:13.500 回答
1
以下是其他三种方法。我希望它们比@A 的矢量化解决方案更节省内存。Donda 或@Mohsen,但当然对于 n = 1000 或更少,这不太可能是一个问题。
最有趣的部分是这两种方法的速度差异,第二种和第三种方法也可以n=10000
在不到一秒的时间内工作,但第一种方法要慢得多!
n = 1000;
% Slow vector growing
tic
v=[];
for t = 1:n
v = [v 1:t];
end
toc % 0.6 sec
tic
% Fast vector growing
v=[];
for t = 1:n
x = 1:t;
v(end+x) = x;
end
toc % 0.01 sec
tic
% Preallocated loop
v=zeros(n*(n+1)/2,1);
count = 0;
for t = 1:n
x = 1:t;
v(count+x) = x;
count = count+t;
end
toc % 0.01 sec as well
于 2013-11-01T14:57:59.333 回答
0
使用稀疏矩阵我们可以做到:
p = 1:4;
x = cumsum(sparse(1,cumsum(p)+1,-p)+1);
x(end) = []
结果:
x =
1 1 2 1 2 3 1 2 3 4
这种方法的最大优点是它也适用于无序序列长度:
p = [2 3 2 4];
x = cumsum(sparse(1,cumsum(p)+1,-p)+1);
x(end) = []
结果:
x =
1 2 1 2 3 1 2 1 2 3 4
于 2020-01-07T09:22:21.557 回答