Целенаправленно медленная функция MATLAB?

Question

Я хочу написать действительно очень медленную программу для MATLAB . Я говорю как, O (2 ^ n) или хуже. Это должно закончиться, и это должно быть детерминистически медленно, так что нет "if rand () = 123,123, выход!" Это звучит безумно, но на самом деле это тест для распределенных систем. Мне нужно создать файл .m, скомпилировать его (с MCC ), а затем запустить его в моей распределенной системе для выполнения некоторых операций отладки.

Программа должна постоянно выполнять работу, поэтому sleep() не является допустимым параметром.

Я пытался создать случайную большую матрицу и найти ее обратную, но это завершалось слишком быстро. Есть идеи?

Answer 1

Эта наивная реализация дискретного преобразования Фурье занимает ~ 9 секунд для входного вектора x длиной 2048 на моей одноядерной машине с частотой 1,86 ГГц. Переход к 4096 входам увеличивает время до ~ 35 секунд, что близко к 4-кратному значению, которое я ожидал бы для O (N ^ 2). У меня нет терпения, чтобы попробовать более длинные входы:)

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);

РЕДАКТИРОВАТЬ: Или, если вы хотите нагрузить память больше, чем процессор:

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 секунд.

Answer 2

Считать до 2 ⁿ . Необязательно, выполняйте медленный вызов функции в каждой итерации.

Answer 3

Если вам нужна настоящая работа, которую легко настроить и которая загружает центральный процессор из памяти:

• Большая плотная матричная инверсия (недостаточно медленно? Сделать ее больше.)
• Фактор RSA номер

Answer 4

Как насчет использования inv? Сообщалось, что довольно медленно .

Answer 5

Легко! Вернитесь к корням машины Тьюринга и подумайте о процессах, которые 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

Answer 6

Сделайте некоторую работу в цикле. Вы можете настроить время, необходимое для выполнения, используя количество итераций цикла.

Answer 7

Я не говорю на 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 раз. Вы можете поместить в цикл некоторую вычислительно тяжелую вещь, чтобы она заняла больше времени, если этого недостаточно.

Answer 8

это будет запускать 100% процессор в течение WANTED_TIME секунд

WANTED_TIME = 2^n; % seconds
t0=cputime; 
t=cputime; 
while (t-t0 < WANTED_TIME)
    t=cputime; 
end;

Answer 9

Попробуйте это:

tic
isprime( primes(99999999) );
toc

---

EDIT

Для более обширного набора тестов используйте следующие тесты (возможно, даже для нескольких повторений):

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

Answer 10

Вы также можете проверить, является ли данный вход простым, просто разделив его на все меньшие числа. Это даст вам O (n ^ 2).