2

我想为MATLAB编写一个非常非常慢的程序。我说的是 O(2^n) 或更糟。它必须完成，并且必须确定地缓慢，所以不要“如果 rand() = 123,123，退出！” 这听起来很疯狂，但它实际上是针对分布式系统测试的。我需要创建一个 .m 文件，编译它（使用MCC），然后在我的分布式系统上运行它以执行一些调试操作。

该程序必须不断地工作，因此sleep()不是一个有效的选择。

我尝试制作一个随机的大矩阵并找到它的逆矩阵，但这完成得太快了。有任何想法吗？

4

11 回答 11

4

数到 2 n。或者，在每次迭代中进行慢速函数调用。

于 2009-10-23T22:55:08.830 回答
4

如果您想要真正的工作，易于设置并强调 CPU 对内存的压力：

  • 大的密集矩阵求逆（不够慢？让它变大。）
  • 分解一个RSA 数字
于 2009-10-23T22:57:51.163 回答
4

对于我的 1.86 GHz 单核机器上的 2048 长输入向量 x，离散傅里叶变换的这种简单实现需要大约 9 秒。使用 4096 个输入将时间延长到 ~ 35 秒，接近我对 O(N^2) 的预期的 4 倍。我没有耐心尝试更长的输入:)

function y = SlowDFT(x)

t = cputime;
y = zeros(size(x));
for c1=1:length(x)
    for c2=1:length(x)
        y(c1) = y(c1) + x(c2)*(cos((c1-1)*(c2-1)*2*pi/length(x)) - ...
                            1j*sin((c1-1)*(c2-1)*2*pi/length(x)));
    end
end
disp(cputime-t);

编辑：或者，如果您希望对内存的压力超过 CPU：

function y = SlowDFT_MemLookup(x)

t = cputime;
y = zeros(size(x));
cosbuf = cos((0:1:(length(x)-1))*2*pi/length(x));
for c1=1:length(x)
    cosctr = 1;
    sinctr = round(3*length(x)/4)+1;
    for c2=1:length(x)
         y(c1) = y(c1) + x(c2)*(cosbuf(cosctr) ...
                            -1j*cosbuf(sinctr));
         cosctr = cosctr + (c1-1);
         if cosctr > length(x), cosctr = cosctr - length(x); end
         sinctr = sinctr + (c1-1);
         if sinctr > length(x), sinctr = sinctr - length(x); end
    end
end
disp(cputime-t);

这比在每次迭代中计算 sin 和 cos 更快。一个 2048 长的输入大约需要 3 秒，一个 16384 长的输入大约需要 180 秒。

于 2009-10-23T23:37:33.907 回答
3

使用 inv 怎么样？据说速度很慢。

于 2009-10-23T22:00:24.550 回答
2

我不会说 MATLAB，但与以下内容等效的东西可能会起作用。

loops = 0
counter = 0
while (loops < MAX_INT) {
    counter = counter + 1;
    if (counter == MAX_INT) {
        loops = loops + 1;
        counter = 0;
    }
}

这将迭代 MAX_INT*MAX_INT 次。如果这还不够，您可以将一些计算量大的东西放入循环中以使其花费更长的时间。

于 2009-10-23T22:02:03.473 回答
2

循环做一些工作。您可以使用循环迭代次数调整完成所需的时间。

于 2009-10-23T22:02:30.450 回答
2

简单的！回到你的图灵机根源，想想 O(2^n) 或更糟的过程。

这是一个相当简单的（警告，未经测试，但你明白了）

N = 12; radix = 10;
odometer = zeros(N, 1);
done = false;
while (~done)
    done = true;
    for i = 1:N
        odometer(i) = odometer(i) + 1;
        if (odometer(i) >= radix)
            odometer(i) = 0;
        else
            done = false;
            break;
        end
    end
end

更好的是，递归计算斐波那契数怎么样？运行时间为 O(2^N)，因为 fib(N) 必须进行两次函数调用 fib(N-1) 和 fib(N-2)，但堆栈深度为 O(N)，因为只有其中一个函数调用一次发生。

function y = fib(n)
   if (n <= 1)
      y = 1;
   else
      y = fib(n-1) + fib(n-2);
   end
end
于 2009-10-29T04:44:10.617 回答
1

您可以要求它factor(X)提供一个适当大的 X

于 2009-10-23T21:59:51.963 回答
1

您还可以通过将其除以所有较小的数字来测试给定的输入是否为素数。这会给你 O(n^2)。

于 2009-10-23T22:41:48.747 回答
1

试试这个：

tic
isprime( primes(99999999) );
toc

编辑：

对于更广泛的测试集，请使用这些基准（甚至可能用于多次重复）：

disp(repmat('-',1,85))
disp(['MATLAB Version ' version])
disp(['Operating System: ' system_dependent('getos')])
disp(['Java VM Version: ' version('-java')]);
disp(['Date: ' date])
disp(repmat('-',1,85))

N = 3000;   % matrix size
A = rand(N,N);  
A = A*A;

tic;  A*A; t=toc;
fprintf('A*A \t\t\t%f sec\n', t)

tic; [L,U,P] = lu(A); t=toc; clear L U P
fprintf('LU(A)\t\t\t%f sec\n', t)

tic; inv(A); t=toc;
fprintf('INV(A)\t\t\t%f sec\n', t)

tic; [U,S,V] = svd(A); t=toc; clear U S V
fprintf('SVD(A)\t\t\t%f sec\n', t)

tic; [Q,R,P] = qr(A); t=toc; clear Q R P
fprintf('QR(A)\t\t\t%f sec\n', t)

tic; [V,D] = eig(A); t=toc; clear V D
fprintf('EIG(A)\t\t\t%f sec\n', t)

tic; det(A); t=toc;
fprintf('DET(A)\t\t\t%f sec\n', t)

tic; rank(A); t=toc;
fprintf('RANK(A)\t\t\t%f sec\n', t)

tic; cond(A); t=toc;
fprintf('COND(A)\t\t\t%f sec\n', t)

tic; sqrtm(A); t=toc;
fprintf('SQRTM(A)\t\t%f sec\n', t)

tic; fft(A(:)); t=toc;
fprintf('FFT\t\t\t%f sec\n', t)

tic; isprime(primes(10^7)); t=toc;
fprintf('Primes\t\t\t%f sec\n', t)

以下是我的机器上仅使用 N=1000 进行一次迭代的结果（注意素数用作上限 10^7 而不是 10^8 [需要更多时间！]）

A*A             0.178329 sec
LU(A)           0.118864 sec
INV(A)          0.319275 sec
SVD(A)          15.236875 sec
QR(A)           0.841982 sec
EIG(A)          3.967812 sec
DET(A)          0.121882 sec
RANK(A)         1.813042 sec
COND(A)         1.809365 sec
SQRTM(A)        22.750331 sec
FFT             0.113233 sec
Primes          27.080918 sec
于 2009-10-24T00:53:09.110 回答
1

这将在 WANTED_TIME 秒内运行 100% cpu

WANTED_TIME = 2^n; % seconds
t0=cputime; 
t=cputime; 
while (t-t0 < WANTED_TIME)
    t=cputime; 
end;
于 2009-11-07T10:42:19.690 回答