Брутфорс перебор over100 миллионов матриц 10x10 в Delphi

[longstreet]

Пусть некоторый алгоритм, без особых оптимизаций, написан в виде кода на Delphi7.
В состав алгоритма входит сложение/вычитание матриц 10x10, причём часть матриц перебором берётся из более сотни миллионов возможных матриц 10x10.
Будет ли такой код выдавать ответ, будучи запущенным на среднем компьютере за умеренное время?

(Оффтоп)

В программировании я не шарю, просьба не пинать.

[rockclimber]

Зависит от того, что вы называете сложением и вычитанием матриц, средним компьютером и умеренным временем.
Могу предложить запустить расчет сначала для 1000 матриц, потом для 10000 и т. д. На 100 миллионов потом проэкстраполируете.
Время можно засекать, например, с помощью API функции Windows GetTickCount.

И еще отдельно зависит от того, что вы делаете с промежуточными результатами. Если вы с ними обращаетесь слишком неправильно, то ваша программа съест всю доступную оперативную память и подвесит компьютер. Один из вариантов развития событий - программа съест не всю память, а почти всю. Windows начнет свопить ее на диск, а программа будет еле шевелиться.

[longstreet]

rockclimber в сообщении #782226 писал(а):

Могу предложить запустить расчет сначала для 1000 матриц, потом для 10000 и т. д. На 100 миллионов потом проэкстраполируете.

Спрашиваю потому, что кода у меня нет.
Я только думаю что придётся писать (и в программировании чуть разобраться).
Соответственно, спрашиваю возможен ли будет такой перебор, или заранее ясно что комп зависнет, память кончится, считать год будет...
То есть меня устроит ответ самый приблизительный.

rockclimber в сообщении #782226 писал(а):

Зависит от того, что вы называете сложением и вычитанием матриц, средним компьютером и умеренным временем.

Компьютер -- 3 ГГц, 8 ГБ оперативки, например.
Умеренное время -- это в смысле менее суток.
Сложение/вычитание матриц -- самое обычное ж, какое в Delphi7 есть.

rockclimber в сообщении #782226 писал(а):

И еще отдельно зависит от того, что вы делаете с промежуточными результатами.

Сравнивать, чтобы найти некоторое минимальное значение.

[rockclimber]

Хм, мне казалось, что все будет значительно хуже, но тем не менее!
Мой код:

var a, b: array[0..9, 0..9] of integer;
  i, j: integer;

procedure TForm1.Button1Click(Sender: TObject);
var k:integer;
  t:TDate;
begin
  t:=Now;
  Prepare;
  for k:=1 to StrToInt(Edit1.Text) do
    OneRun;

  t:=now-t;

  ShowMessage('Время выполнения: ' + FormatDateTime('hh:mm:ss', t));
end;

procedure TForm1.OneRun;
var x, xmin: integer;
begin
  xmin:=0;
  for i:=0 to 9 do
    for j:=0 to 9 do
      begin
        x:=a[i,j]+b[i,j];
        if xmin > x then
           xmin:=x;
      end;
end;

procedure TForm1.Prepare;
begin
  for i:=0 to 9 do
    for j:=0 to 9 do
      begin
        a[i,j]:=random(1000);
        b[i,j]:=random(1000);
      end;
end;

Один раз два массива 10 на 10 заполняются случайными цифрами, потом в цикле вызывается процедура, выполняет 100 сложений (каждый элемент массива а с элементом массива b на той же позиции), а потом вычисляет минимальное число получившегося массива.
В поле Edit1.Text я вписывал число запусков. 100 миллионов циклов обработались на моем ноутбуке за 45 секунд.
Брутфорсьте на здоровье!

[longstreet]

Wow! rockclimber, большое спасибо за приведённый код!
Быстродействие здорово впечатляет -- не ожидал совсем.

[g______d]

Я не программист, но советую на всякий случай в подобных тестах отключать оптимизацию кода. В Delphi это, кажется, {$O-}. Из программы, которая 100000000 раз подряд делает абсолютно одно и тоже, а потом еще и не использует конечный результат, некоторые особо умные компиляторы могут просто выкинуть "неиспользуемые" куски кода и создавать иллюзию быстрой работы.

[longstreet]

Первый раз слышу.
Попытаюсь учесть, спасибо.

[Pavia]

longstreet
Задача очень расплывчата.
Если правильно напишете, то работать будет около 1-10 минут.
Если неправильно, то 10-20 суток.


g______d

g______d в сообщении #782449 писал(а):

не использует конечный результат

Лучше использовать результат. К примеру сделать вывод и все дела.

[rockclimber]

g______d в сообщении #782449 писал(а):

Я не программист, но советую на всякий случай в подобных тестах отключать оптимизацию кода. В Delphi это, кажется, {$O-}. Из программы, которая 100000000 раз подряд делает абсолютно одно и тоже, а потом еще и не использует конечный результат, некоторые особо умные компиляторы могут просто выкинуть "неиспользуемые" куски кода и создавать иллюзию быстрой работы.

Неиспользуемые куски кода обычно откидывают функциональные языки, к которым дэлфи не относится. В функциональном программировании эта концепция называется "ленивые вычисления". "Обычные отпимизаторы" занимаются вещами попроще о попредсказуемее - например, заменяют умножение и деление на степени двойки битовым сдвигом.

[Xaositect]

rockclimber в сообщении #782498 писал(а):

Неиспользуемые куски кода обычно откидывают функциональные языки, к которым дэлфи не относится. В функциональном программировании эта концепция называется "ленивые вычисления". "Обычные отпимизаторы" занимаются вещами попроще о попредсказуемее - например, заменяют умножение и деление на степени двойки битовым сдвигом.

Не знаю конкретно про Delphi, но, современные компиляторы C/C++ неиспользуемые куски выкидывают. Например, для такой программы цикл while(x < 0) выкидывается:

Используется синтаксис C

#include <stdlib.h>
#include <stdio.h>

inline int f(int x)
{
  int r = 1;
  while (x < 0) {
    r *= (r + 1);
    x++;
  }
  return r;
}

int main()
{
  int x;
  scanf("%d", &x);
  printf("%d\n", f(abs(x)));
}
 

[Alexu007]

Xaositect в сообщении #782634 писал(а):

Например, для такой программы цикл while(x < 0) выкидывается.

Чего это вдруг? Если в функцию передаётся -100, и выполняется, пока x<0?

[Xaositect]

Alexu007 в сообщении #782638 писал(а):

Чего это вдруг?

Потому что f вызывается только от abs(x), а abs(x) может быть отрицательным только в случае появления UB.

[longstreet]

Pavia в сообщении #782489 писал(а):

Если правильно напишете, то работать будет около 1-10 минут.
Если неправильно, то 10-20 суток.

Вы имеете в виду, что нужно будет как-то оптимизировать алгоритм?

Pavia в сообщении #782489 писал(а):

Лучше использовать результат. К примеру сделать вывод и все дела.

Файл с одной матрицей 10x10 в формате txt занимает около 4 КБ.
Получается, что вывод 100 миллионов таких матриц займёт под 400 ГБ.
У меня столько свободного нет места.

[arseniiv]

Это был совет для программы проверки (компилятор мог бы увидеть, что результаты тех операций никуда не попадают, и весь соответствующий затратный код вырезать, из-за чего она работала бы быстрее, чем работала бы реальная), а не для вашей планирующейся.

-- Пт ноя 01, 2013 14:43:42 --

Наоборот, если бы вы стали выводить промежуточные результаты, выполнение бы могло значительно замедлиться.

[rockclimber]

Xaositect в сообщении #782634 писал(а):

Не знаю конкретно про Delphi, но, современные компиляторы C/C++ неиспользуемые куски выкидывают.

Delphi 7 не является современным языком программирования - он вышел 11 лет назад
7-я версия, насколько я знаю, вообще мало что умела оптимизировать. Хотя я в такие тонкости не вникал.