2

私はMATLAB用の本当に本当に遅いプログラムを書きたいと思っています。私は、O（2 ^ n）以下のように話している。それは終了する必要があり、決定論的に遅くなければならないので、「rand（）= 123,123の場合、終了します！」これはおかしなことに聞こえますが、実際には分散システムのテスト用です。.mファイルを作成し、（MCCを使用して）コンパイルしてから、分散システムで実行してデバッグ操作を実行する必要があります。

プログラムは常に作業を行っている必要があるためsleep()、有効なオプションではありません。

ランダムな大きな行列を作成してその逆行列を見つけようとしましたが、これはあまりにも早く完了しました。何か案は？

4

11 に答える 11

4

セットアップが簡単で、メモリよりも CPU に負荷をかける実際の作業が必要な場合は、次のようにします。

  • 大規模な密行列反転 (遅くない? 大きくしてください。)
  • RSA 番号を因数分解する
于 2009-10-23T22:57:51.163 に答える
4

2 nまで数えます。必要に応じて、反復ごとに遅い関数呼び出しを行います。

于 2009-10-23T22:55:08.830 に答える
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

簡単！Turing マシンのルートに戻って、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

さらに良いことに、フィボナッチ数を再帰的に計算するのはどうですか? fib(N) は fib(N-1) と fib(N-2) の 2 つの関数呼び出しを行う必要があるため、実行時間は O(2^N) ですが、これらの関数呼び出しの 1 つだけであるため、スタックの深さは 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

これにより、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 に答える
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)

以下は、1 回の反復のみに 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 に答える