4

给定一个整数 n，我想得到如下向量。例如，如果n=3，那么向量应该是[1,1,2,1,2,3]，如果n=4，那么向量应该是[1,1,2,1,2,3,1,2,3,4]，等等。有没有简单的方法来做到这一点？谢谢。

4

4 回答 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 回答