2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение30.10.2013, 16:08 
Пусть некоторый алгоритм, без особых оптимизаций, написан в виде кода на Delphi7.
В состав алгоритма входит сложение/вычитание матриц 10x10, причём часть матриц перебором берётся из более сотни миллионов возможных матриц 10x10.
Будет ли такой код выдавать ответ, будучи запущенным на среднем компьютере за умеренное время?

(Оффтоп)

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

 
 
 
 Re: Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение30.10.2013, 16:16 
Зависит от того, что вы называете сложением и вычитанием матриц, средним компьютером и умеренным временем.
Могу предложить запустить расчет сначала для 1000 матриц, потом для 10000 и т. д. На 100 миллионов потом проэкстраполируете.
Время можно засекать, например, с помощью API функции Windows GetTickCount.

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

 
 
 
 Re: Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение30.10.2013, 21:32 
rockclimber в сообщении #782226 писал(а):
Могу предложить запустить расчет сначала для 1000 матриц, потом для 10000 и т. д. На 100 миллионов потом проэкстраполируете.

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

rockclimber в сообщении #782226 писал(а):
Зависит от того, что вы называете сложением и вычитанием матриц, средним компьютером и умеренным временем.

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

rockclimber в сообщении #782226 писал(а):
И еще отдельно зависит от того, что вы делаете с промежуточными результатами.

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

 
 
 
 Re: Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение30.10.2013, 22:09 
Хм, мне казалось, что все будет значительно хуже, но тем не менее!
Мой код:
Код:
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 секунд.
Брутфорсьте на здоровье! :mrgreen:

 
 
 
 Re: Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение31.10.2013, 00:55 
Wow! :-) rockclimber, большое спасибо за приведённый код!
Быстродействие здорово впечатляет -- не ожидал совсем.

 
 
 
 Re: Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение31.10.2013, 01:06 
Аватара пользователя
Я не программист, но советую на всякий случай в подобных тестах отключать оптимизацию кода. В Delphi это, кажется, {$O-}. Из программы, которая 100000000 раз подряд делает абсолютно одно и тоже, а потом еще и не использует конечный результат, некоторые особо умные компиляторы могут просто выкинуть "неиспользуемые" куски кода и создавать иллюзию быстрой работы.

 
 
 
 Re: Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение31.10.2013, 01:11 
:shock: Первый раз слышу.
Попытаюсь учесть, спасибо.

 
 
 
 Re: Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение31.10.2013, 06:46 
Аватара пользователя
longstreet
Задача очень расплывчата.
Если правильно напишете, то работать будет около 1-10 минут.
Если неправильно, то 10-20 суток.


g______d
g______d в сообщении #782449 писал(а):
не использует конечный результат

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

 
 
 
 Re: Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение31.10.2013, 07:31 
g______d в сообщении #782449 писал(а):
Я не программист, но советую на всякий случай в подобных тестах отключать оптимизацию кода. В Delphi это, кажется, {$O-}. Из программы, которая 100000000 раз подряд делает абсолютно одно и тоже, а потом еще и не использует конечный результат, некоторые особо умные компиляторы могут просто выкинуть "неиспользуемые" куски кода и создавать иллюзию быстрой работы.
Неиспользуемые куски кода обычно откидывают функциональные языки, к которым дэлфи не относится. В функциональном программировании эта концепция называется "ленивые вычисления". "Обычные отпимизаторы" занимаются вещами попроще о попредсказуемее - например, заменяют умножение и деление на степени двойки битовым сдвигом.

 
 
 
 Re: Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение31.10.2013, 13:41 
Аватара пользователя
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)));
}
 

 
 
 
 Re: Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение31.10.2013, 13:48 
Xaositect в сообщении #782634 писал(а):
Например, для такой программы цикл while(x < 0) выкидывается.


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

 
 
 
 Re: Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение31.10.2013, 13:52 
Аватара пользователя
Alexu007 в сообщении #782638 писал(а):
Чего это вдруг?
Потому что f вызывается только от abs(x), а abs(x) может быть отрицательным только в случае появления UB.

 
 
 
 Re: Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение01.11.2013, 11:30 
Pavia в сообщении #782489 писал(а):
Если правильно напишете, то работать будет около 1-10 минут.
Если неправильно, то 10-20 суток.

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

Pavia в сообщении #782489 писал(а):
Лучше использовать результат. К примеру сделать вывод и все дела.

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

 
 
 
 Re: Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение01.11.2013, 11:41 
Это был совет для программы проверки (компилятор мог бы увидеть, что результаты тех операций никуда не попадают, и весь соответствующий затратный код вырезать, из-за чего она работала бы быстрее, чем работала бы реальная), а не для вашей планирующейся. :-)

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

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

 
 
 
 Re: Брутфорс перебор over100 миллионов матриц 10x10 в Delphi
Сообщение01.11.2013, 15:18 
Xaositect в сообщении #782634 писал(а):
Не знаю конкретно про Delphi, но, современные компиляторы C/C++ неиспользуемые куски выкидывают.
Delphi 7 не является современным языком программирования - он вышел 11 лет назад :wink:
7-я версия, насколько я знаю, вообще мало что умела оптимизировать. Хотя я в такие тонкости не вникал.

 
 
 [ Сообщений: 23 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group