search

divyang4481 / mipt-hw

Automatically exported from code.google.com/p/mipt-hw
0 stars 0 forks source link

task03 TMatrix (Яковенко) #196

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
iakovenko_pavel\task03_TMatrix

На размере матрицы больше 1024 умножение 
очень долго работает. Но, опять же, динамика 
уже прослеживается. К сожалению, я сделал 
алгоритм Штрассена только для квадратных 
матриц.

Original issue reported on code.google.com by iakovenk...@gmail.com on 2 Apr 2013 at 9:20

Attachments:

GoogleCodeExporter commented 9 years ago 
Думайте, как оптимизировать. 500 секунд для 
матриц 1024 на 1024 - очень долго...

У меня следующие результаты на Core i7:
---------------------------------------------
N=64
    time1: 0ms
    time2: 0ms
---------------------------------------------
N=128
    time1: 4ms
    time2: 2ms
---------------------------------------------
N=256
    time1: 25ms
    time2: 22ms
---------------------------------------------
N=512
    time1: 274ms
    time2: 155ms
---------------------------------------------
N=1024
    time1: 9909ms
    time2: 1130ms
---------------------------------------------
N=2048
    time1: 90176ms
    time2: 7863ms

Думайте, как оптимизировать. Пока не буду 
смотреть Ваш код.

Original comment by aivyu...@gmail.com on 6 Apr 2013 at 9:44

GoogleCodeExporter commented 9 years ago 
0. ошибки компиляции:
TMatrix.cpp:18: error: ‘mat’ was not declared in this scope
TMatrix.cpp:18: error: ‘>>’ should be ‘> >’ within a nested template 
argument list
TMatrix.cpp: In function ‘int random()’:
TMatrix.cpp:374: error: new declaration ‘int random()’
/usr/include/stdlib.h:224: error: ambiguates old declaration ‘long int 
random()’

Я исправил ошибки сам, т.к. это гл обр 
связано с разницей в компиляторах. Не 
забудьте сделать svn update.

1. Приложите, пожалуйста, таблицу с 
результатами

2. Хочется запустить Вашу программу и она 
начнет на моей машине делать тесты и мерять 
время. Доработайте, пожалуйста.
Пример можете посмотреть в комментариях. Я 
присылал Вам вывод своей программы.

3. Это ведь дико неудобно постоянно писать 
(float)t/CLOCKS_PER_SEC. Заведите функцию, например 
такую:
  typedef long long i64;
  i64 GetClock() {
       return clock() * 1000 / CLOCKS_PER_SEC;
  }
Она возвращает время в миллисекундах. Я 
лично сделал себе небольшой классик:
  class TTimePrinter {
      i64 Start;
  public:
      TTimePrinter()
          : Start(GetClock()) {
      }

      void Print() const {
          cout << "\tTime: " << this->GetTime() << " sec" << endl;
      }

      double GetTime() const {
          return (GetClock() - Start) * 0.001;
      }

      void Reset() {
          Start = GetClock();
      }
  };

Пользоваться им очень просто:

TTimePrinter tp;
...
tp.PrintTime(); // печатает время от момента 
создания объекта tp
...
tp.PrintTime(); // печатает время от момента 
создания объекта tp
...
tp.Reset();
...
tp.PrintTime(); // печатает время от момента 
последнего вызова Reset

4. Вспомогательные функции типа quater нужно 
скрывать от пользователя в private. Это детали 
реализации.

5. Ваш operator= невозможно использовать 
каскадно:
a = b = c; // такой код не компилируется

6. Вы реализуете operator+= (и все подобные) c 
использованием доп памяти через бинарные 
операторы. Это нерационально. Подумайте, 
как не исользовать доп память.

Original comment by aivyu...@gmail.com on 28 Apr 2013 at 11:08

GoogleCodeExporter commented 9 years ago 
Все поправил, кроме 4 пункта. Я немножко не 
понимаю, ведь у меня функция "StrassenMultiply" 
является внешней к классу, и там 
используется метод quater. Если его сделать 
приватным, функция не сможет его вызвать. 
Еще, прикладываю файл с оценкой работы 
метода Штрассена. У меня получилось 
уменьшить время где-то на 100 секунд при 
1024*1024, но не смог и близко приблизится к 
вашим результатам.

Original comment by iakovenk...@gmail.com on 28 Apr 2013 at 10:08

Attachments:

GoogleCodeExporter commented 9 years ago 
По поводу пункта 4.
Такие функции все равно нужно убирать из 
интерфейса. Если же к ним нужен доступ 
какой-нибудь функции (или классу) foo, то эту 
функцию (класс) нужно сделать 
дружественным.

Original comment by aivyu...@gmail.com on 28 Apr 2013 at 11:02

GoogleCodeExporter commented 9 years ago 
Я немножко поправил код, он не собирался 
моим компилятором.

Original comment by aivyu...@gmail.com on 10 May 2013 at 7:44

GoogleCodeExporter commented 9 years ago 
Запускаю Вашу программу. Получаю следующий 
вывод:
First Test Matrix:
__________________________________
7   9   3   
8   0   2   
4   8   3   
__________________________________
Second Test Matrix:
__________________________________
9   0   5   
2   2   7   
3   7   9   
__________________________________
First Matrix plus Second Matrix
__________________________________
16  9   8   
10  2   9   
7   15  12  
__________________________________
First Matrix minus Second Matrix
__________________________________
-2  9   -2  
6   -2  -5  
1   1   -6  
__________________________________
First Matrix multiplied by Second Matrix (usual method)
__________________________________
90  39  125 
78  14  58  
61  37  103 
__________________________________
First Matrix multiplied by number 
5__________________________________
35  45  15  
40  0   10  
20  40  15  
__________________________________
First Matrix now 
__________________________________
35  45  15  
40  0   10  
20  40  15  
__________________________________
Checking operator = 
__________________________________
9   0   5   
2   2   7   
3   7   9   
__________________________________
First Test Matrix:
__________________________________
0   2   3   9   9   
7   0   3   9   8   
6   5   7   6   2   
7   0   3   9   9   
9   1   7   2   3   
__________________________________
Second Test Matrix:
__________________________________
6   5   5   8   1   
4   7   1   3   8   
4   8   0   4   6   
0   3   2   6   9   
4   1   3   7   8   
__________________________________
Strassen Multiply matrices test1 and test2
__________________________________
56  74  47  135 187 
86  94  77  178 170 
92  141 53  141 158 
90  95  80  185 178 
98  117 59  136 101 
__________________________________
Transopsing first test matrix 
__________________________________
0   7   6   7   9   
2   0   5   0   1   
3   3   7   3   7   
9   9   6   9   2   
9   8   2   9   3   
__________________________________
changing size
 __________________________________
0   
2   
__________________________________
__________________________________
0   7   6   7   
2   0   5   0   
__________________________________

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

Кстати, Вы проверяете корректность 
алгоритма Штрассена с помощью алгоритма 
умножения в лоб?
Я к тому, что результаты должны совпадать.

Original comment by aivyu...@gmail.com on 10 May 2013 at 7:47

GoogleCodeExporter commented 9 years ago 
Я поправил. Сейчас при умножением методом 
Штрассена показывается все меньшие 
матрицы, которые перемножаются. Для 
простого перемножения я не стал выводить 
все суммы. В конце, матрицы сравниваются и 
выводится результат.

Original comment by iakovenk...@gmail.com on 17 May 2013 at 8:15

GoogleCodeExporter commented 9 years ago 
Программа снова выводит мне какие-то 
непонятные чиселки:

First Test Matrix:
__________________________________
7   9   3   
8   0   2   
4   8   3   
__________________________________
Second Test Matrix:
__________________________________
9   0   5   
2   2   7   
3   7   9   
__________________________________
First Matrix plus Second Matrix
__________________________________
16  9   8   
10  2   9   
7   15  12  
__________________________________
First Matrix minus Second Matrix
__________________________________
-2  9   -2  
6   -2  -5  
1   1   -6  
__________________________________
First Matrix multiplied by Second Matrix (usual method)
__________________________________
90  39  125 
...

Я ведь выше присылал Вам образец, что 
хочется. Не обязательно ИМЕННО так, но идея.

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

Original comment by aivyu...@gmail.com on 17 May 2013 at 12:09

GoogleCodeExporter commented 9 years ago 
Юлий Романович, я все таки не понимаю что 
конкретно мне надо выводить.

Original comment by iakovenk...@gmail.com on 17 May 2013 at 3:14

GoogleCodeExporter commented 9 years ago 
Я приводил выше пример вывода своей 
программы:
---------------------------------------------
N=64
    time1: 0ms
    time2: 0ms
---------------------------------------------
N=128
    time1: 4ms
    time2: 2ms
---------------------------------------------
N=256
    time1: 25ms
    time2: 22ms
---------------------------------------------
N=512
    time1: 274ms
    time2: 155ms
---------------------------------------------
N=1024
    time1: 9909ms
    time2: 1130ms
---------------------------------------------
N=2048
    time1: 90176ms
    time2: 7863ms

Т.е. задается какое-то начальное N. Потом оно 
растет и для каждого N генерируется 
рандомом пара матриц. Вычисляется их 
произведение алгоритмом "по определению" и 
Штрассена. Для каждого выводится время. В 
коде делается проверка, что результаты 
вычисления разными алгоритмами совпадают. 
Если не совпали: кидаем исключение или 
пишем Achtung! в stdout.

Напоминаю, что нужно измерять время работы 
самих алгоритмов без доп расходов: 
генерации матриц (это очень затратная 
операция), вывода на экран и пр.

Original comment by aivyu...@gmail.com on 17 May 2013 at 3:30

GoogleCodeExporter commented 9 years ago 
Я неправильно понял :) Я почему-то думал, что 
вам нужно показать, как прямо алгоритм 
работает, какие циферки перемножает. 
Теперь я исправил все)

Original comment by iakovenk...@gmail.com on 17 May 2013 at 4:38

GoogleCodeExporter commented 9 years ago 
0. Я все меняю имя функции random на Random, а Вы - 
обратно :)
У меня компилятор конфликт имен выдает:
TMatrix.cpp: In function ‘int random()’:
TMatrix.cpp:410: error: new declaration ‘int random()’
/usr/include/stdlib.h:224: error: ambiguates old declaration ‘long int 
random()’

1. Вижу у Вас структуру:
 10 struct str{
 11         int p;
 12         str (){ Created++;}
 13         ~str (){Deleted++;}
 14 };
Вы ее не используете в этой задаче, но 
имейте в виду, что она не совсем корректно 
подсчитывает кол-во объектов, т.к. не 
переопределен конструктор копирования.

2. Прогнал Вашу программу. Получил:
N = 128
Strassen method for num=128 time: 0.101
Usual method for num=128 time: 0.099
Matrices are equal

N = 256
Strassen method for num=256 time: 0.704
Usual method for num=256 time: 0.807
Matrices are equal

N = 512
Strassen method for num=512 time: 4.97
Usual method for num=512 time: 6.592
Matrices are equal

N = 1024
Strassen method for num=1024 time: 35.395
Usual method for num=1024 time: 60.677

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

3. Для проверки корректности можно было не 
запускать заново умножение, а сохранять 
результаты и потом их сравнивать. Это 
работало бы в 2 раза быстрее.

Решение принято.
Минус 40% за сдачу через 9 дней после 
дедлайна.

Original comment by aivyu...@gmail.com on 19 May 2013 at 10:46