divyang4481 / mipt-hw

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

task03 Работа с матрицами (Анастасьев) #191

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago
anastasyev_daniil/task03_matrix/

Original issue reported on code.google.com by dan.anas...@gmail.com on 24 Mar 2013 at 8:24

GoogleCodeExporter commented 9 years ago
0. Compilation errors:
main.cpp:14: error: ‘matrix’ was not declared in this scope
main.cpp:14: error: ‘>>’ should be ‘> >’ within a nested template 
argument list
main.cpp: In member function ‘T& TMatrix<T>::At(size_t, size_t) [with T = 
int]’:
main.cpp:248:   instantiated from here
main.cpp:143: warning: comparison between signed and unsigned integer 
expressions
main.cpp:143: warning: comparison between signed and unsigned integer 
expressions
main.cpp: In member function ‘const T& TMatrix<T>::At(size_t, size_t) const 
[with T = int]’:
main.cpp:237:   instantiated from ‘std::ostream& operator<<(std::ostream&, 
const TMatrix<T>&) [with T = int]’
main.cpp:249:   instantiated from here
main.cpp:138: warning: comparison between signed and unsigned integer 
expressions
main.cpp:138: warning: comparison between signed and unsigned integer 
expressions

1. Почему поле matrix public?

2. В конструкторе TMatrix(size_t rowCount, size_t colCount) 
если передать хотя бы один нулевой 
параметр внутренние поля row/col останутся 
неиницилизированными. Значит в них будет 
храниться мусор.

3. В деструкторе нет необходимости вызывать 
clear. Ведь для поля matrix автоматически будет 
вызван деструктор. Собственно, в этом смысл 
использования vector: нет необходимости 
следить за памятью.

4. В конструкторе копирования и операторе 
operator= копи-паст. Стоит реализовать один из 
этих методов. А во втором вызывать первый.

5. Ваши операторы +=,-=, ... реализованы 
неоптимально, т.к. они выделяют доп память. 
Правильнее наоборот: реализовать их. А 
через них реализовать бинарные операторы 
+,-,...

6. operator*, operator*= принимают аргумент по 
значению. При этом происходит копирование. 
Для матриц это очень тяжелая операция. 
Правильнее передавать по ссылке, как Вы 
делаете это, например, в operator+=.

7. At возвращает значение, если индексы 
валидны. А если невалидны - возвращает 
мусор. Причем такая ошибка плоха тем, что 
может вызвать Access Violation. Выходит, Ваша 
проверка не решает никакую проблему. 
Предлагаю эту проверку реализовать как-то 
более логично, либо вообще убрать (как мы и 
договаривались: невалидные аргументы - 
undefined behaviour).

8. Ваш метод Transpose имеет квадратичную 
сложность. Подумайте, как можно улучшить.

9. Где табличка и график с результатами 
сравнения работы разных алгоритмов 
умножения?

Решение не принято.

Original comment by aivyu...@gmail.com on 6 Apr 2013 at 8:32

GoogleCodeExporter commented 9 years ago

Original comment by dan.anas...@gmail.com on 24 May 2013 at 9:11

Attachments:

GoogleCodeExporter commented 9 years ago
1. Прогоняю Ваше решение:
...
N = 256
Strassen method: 0.666
Usual method: 0.743
N = 512
Strassen method: 4.752
Usual method: 6.82
N = 1024
Strassen method: 33.626
Usual method: 65.582

Выходит, алгоритм Штрассена не дает 
никакого профита?
Вообще, у Вас как-то ооочень медленно все 
работает. Для сравнения, у меня при N=1024 
алгоритм Штрассена работает 1.1 секунды, а 
алгоритм "по определению" - 10 секунд.

2. Стоит делать проверку результата 
вычисления разными алгоритмами и выводить, 
совпадают они или нет. Чтобы понимать, что 
алгоритм Штрассена хотя бы корректно 
работает.

Решение не принято.

Original comment by aivyu...@gmail.com on 26 May 2013 at 11:31

GoogleCodeExporter commented 9 years ago
Оптимизировал обычное умножение. Теперь 
Штрассен действительно профита не дает.
Я, правда, вот этот метод использую, как 
предположительно более быстрый: 
http://ru.wikipedia.org/wiki/%C0%EB%E3%EE%F0%E8%F2%EC_%D8%F2%F0%E0%F1%F1%E5%ED%E
0#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC_.D0.92.D0.B8.D0.BD.D0.BE.D0.B
3.D1.80.D0.B0.D0.B4.D0.B0-.D0.A8.D1.82.D1.80.D0.B0.D1.81.D1.81.D0.B5.D0.BD.D0.B0

Original comment by dan.anas...@gmail.com on 26 May 2013 at 6:27

GoogleCodeExporter commented 9 years ago
Думаю, большие просадки дают не 3 лишних 
умножения, а расточительное использование 
памяти :)

Original comment by aivyu...@gmail.com on 26 May 2013 at 7:15

GoogleCodeExporter commented 9 years ago
Решение принято.

Original comment by aivyu...@gmail.com on 26 May 2013 at 7:17