Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Попытка улучшить действующий код - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Запрашивание ячеек в grid control http://www.cyberforum.ru/cpp/thread1722973.html
подскажите пожалуйста, как начать программу, (задать область 32*32 клеток) закрашивающая клетки разных цветов в виде G, как на картинке. Заранее спасибо!
C++ OpenAl или Qt либы Хочу написать проигрыватель музыкальный, но появилась проблема в выборе между OpenAl и Qt библиотекой. 1. OpenAL нет документации на русском, но есть пример написания класса звукового. 2.Qt... http://www.cyberforum.ru/cpp/thread1722848.html
Исходник программы тестирования C++
Пишу курсач, есть ли у кого исходники тестов?
Программа C++
Решите пожалуйста в короткие сроки за 1 день нужно решить . 14 вариант . Нужна программа
C++ программа http://www.cyberforum.ru/cpp/thread1720877.html
Помогите написать программу на C++
C++ Написать юнит-тесты и реализовать функцию для матрицы Всем привет. Очередной раз преподы в универе удивляют меня своими заданиями. Необходимо выполнить задание: #################### Написать юнит-тесты и реализовать следующую функцию: Функция... подробнее

Показать сообщение отдельно
Aspromist
0 / 0 / 0
Регистрация: 23.12.2014
Сообщений: 28
04.05.2016, 15:28  [ТС]
в reduceRangeByMatrix 2 пути в зависимости от толщины блоков, если блоки толщины в 1 строку, то запускается for с reduceRangeByRow, иначе for с fastReduceRangeByRange. Толщина блоков регулируется в доп параметрах при запуске уже самой программы. У меня с блоками толщины в 1 строку работает быстрее, но наверняка есть случаи когда выгоднее иначе делать. А в этих функциях в свою очередь есть еще forы. Поэтому очень большое количество итераций reduceRowByRow (они в случае блоков толщины 1), хотя каждая выполняется молниеносно. Вот файл cmatrix.h в котором в 106-й строке описан getCoefByMonom:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
#ifndef CMatrix_h
#define CMatrix_h
/**
\file
Представление матриц и операции над ними.
Определят тип CMatrix, представляющий матрицу, CRow,
представляющий отдельную строку и структуру RowElement соответствующую одному ненулевому элементу строки.
*/
 
#include "settings.h"
#include "monomialmap.h"
 
#include <cmath>
#include <vector>
#include <algorithm>
#include <ostream>
 
namespace F4MPI{
/**
Структура для хранения элемента строки.
Поскольку матрица является разреженной, хранятся только ненулевые элементы строк.
Поэтому вместе с численным значением элемента хранится номер столбца, в котором он расположен.
Является POD-типом.
*/
struct RowElement{
    ///номер столбца матрицы, в котором находится элемент
    int column;
 
    ///значение элемента из поля Z_p (всегда ненулевое)
    CModular value;
};
 
/**
Тип представляющий строку матрицы.
Строка матрицы состоит из массива упорядоченных по возрастанию номера столбца переменных типа RowElement.
Этот массив представлен, как базовый класс PODvector<RowElement>,
от которого строка наследует стандартные операции над STL-контейенерами и тип итератора,
используемый для обхода элементов строки.
*/
struct CRow:public PODvector<RowElement>{
//struct CRow:public vector<RowElement >{
 
    ///добавляет к строке rowTo строку rowFrom, домноженную на multBy
    void addRowMultypliedBy(const CRow& rowFrom, CModular multBy);
 
    ///Базовый контейнер (массив) для хранения отдельных элементов
    typedef PODvector<RowElement> BaseContainer;
 
    typedef BaseContainer::iterator iterator;
    typedef BaseContainer::const_iterator const_iterator;
 
    using BaseContainer::swap;
    using BaseContainer::resize;
    using BaseContainer::begin;
    using BaseContainer::end;
    using BaseContainer::size;
    using BaseContainer::empty;
    
    /**Делает единичным ведущий элемент строки.
    Нормализует строку, т.е. домножает все элементы строки на коэффициент обратный ведущему (первому ненулевому).
    Таким образом ведущий элемент становится единичным.
    */
    void normalize(){
        CModular c  = CModular::inverseMod(HC());   
        for(unsigned i = 0; i<size(); i++){
            (*this)[i].value = (*this)[i].value*c;
        }
    }
 
    /**
    возвращает численное значение ведущего элемента строки.
    Численное значение ведущего элемента строки определено только для строк с по крайней мере одним ненулевым элементом,
    поэтому функцию нельзя вызывать для нулевых строк.
    */
    CModular HC()const{
        return begin()->value;
    }
    
    /**
    Возвращает столбец, содержащий ведущий элемент строки.
    Столбец, содержащий ведущий элемент строки определён только для строк с по крайней мере одним ненулевым элементом,
    поэтому функцию нельзя вызывать для нулевых строк.  
    */
    int HM()const{
        return begin()->column;
    }
 
    /**
    функция сравнения столбцов двух элементов строки.
    Сравнение элементов по номеру столбца соответствует упорядочиванию, соответсвующему хранению элементов строки в массиве.
    Операция сравнения используется в качестве operator< для функций бинарного поиска элемента по номеру столбца.
    */
    static bool rowElementComparator(const RowElement& a, const RowElement& b){
        return a.column<b.column;
    }
    
    /**
    возвращает элемент строки  в заданном столбце.
    Выполняет поиск в массиве ненулевых элементов элемента с заданным номером столбца.
    Если элемент найден, возвращает соответсвующее численное значение, иначе возвращает 0,
    так как в столбцах, которым не соответствует элемент массива, находятся нули.
    В силу упорядоченности массива используется бинарный поиск и время работы процедуры равно
    O(log(число ненулевых элементов)).
    \param columnID столбец, значение элемента в котором нужно вернуть.
    */
    CModular getCoefByMonom(int columnID){
        //Если известно, что элемент в начале, то линейный поиск будет лучше
        //но это не всегда известно, поэтому пусть пока будет бинарный
    
        //порядок индексов соответствует порядку элементов в векторе, поэтому можно применить бинарный поиск
        if (columnID < this->front().column) return 0;
        RowElement searchfor;
        searchfor.column=columnID;
        iterator i;
        i = std::lower_bound(begin(), end(), searchfor, rowElementComparator);
        if (i!=end() && i->column==columnID){
            return i->value;
        }
        return 0;
    }
};
 
/** тип, представляющий матрицу.
Матрица состоит из массива строк #СRow.
Этот массив представлен, как базовый класс vector<СRow>,
от которого матрица наследует стандартные операции над STL-контейенерами и тип итератора,
используемый для обхода строк матрицы.
*/
class CMatrix:public std::vector<CRow>{
  public:
    ///Тип строки матрицы
    typedef CRow Row;
  private:
    ///Базовый контейнер (массив) для хранения строк
    typedef std::vector<Row> BaseContainer;
  public:
    using BaseContainer::back;
    using BaseContainer::clear;
    using BaseContainer::resize;
    using BaseContainer::reserve;
    using BaseContainer::begin;
    using BaseContainer::end;
    using BaseContainer::size;
    using BaseContainer::empty;
 
    typedef Row::iterator Rowit;
    typedef Row::const_iterator ConstRowit;
    typedef BaseContainer::iterator iterator;
    typedef iterator MatrixIterator;
 
private:
    /**соответствие между мономами и номерами столбцов.
    На этапе формирования матрицы из многочленов в матрице сохраняется соответствие между мономами и номерами столбцов,
    которое позже используется для обратного преобразования строк матрицы в многочлены.
    */
    MonomialMap M;
 
public:
 
    /**возвращает ссылку на меременную, в которой должна быть сохранена статистика для данной матрицы.
    Статистика для данной матрицы сохраняется в последний элемент массива со статистикой,
    поэтому возвращаемая значение верно только до тех пор, пока сбор статистики не начнётся для следующей матрицы
    */
    MatrixInfo& getMyStats(const F4AlgData* f4options);
 
    ///Записывает статистику по текущему состоянию матрицы в заданную переменную
    void makeMatrixStats(SingleMatrixInfo &);
 
    /**
    Работа со статистикой до приведения матрицы к ступенчатому виду.
    Добавляет в массив статистических данных новый элемент, соответсвующий текущей матрице,
    записывает статистику по текущему (до редукции) состоянию, также выводит его в файл.
    Если статистика отключена, ничего не делает.
    */
    void doMatrixStatsPre(const F4AlgData* f4options);
 
    /**
    Работа со статистикой после приведения матрицы к ступенчатому виду.
    Записывает статистику по текущему (после редукции) состоянию, время затраченное на редукцию, также выводит это в файл.
    Если статистика отключена, ничего не делает.
    */
    void doMatrixStatsPost(const F4AlgData* f4options);
 
    const Row& getRow(int i)const{
        return (*this)[i];
    }
    
    ///возвращает ссылку на строку матрицы по заданному номеру
    Row& getRow(int i){
        return (*this)[i];
    }
 
    const MonomialMap& getMonomialMap()const{
        return M;
    }
 
    ///возвращает ссылку на соответствие между мономами и номерами столбцов
    MonomialMap& getMonomialMap(){
        return M;
    }
 
    ///Печатает матрицу в заданный поток вывода \a output
    void printMatrix(std::ostream& output);
 
    void printMatrixInfo(FILE *output,const char* name, int ID=0);
 
    /**
    Проводит полную авторедукцию матрицы \a m.
    После проведения полной авторедукции матрица \a mимеет сильно ступенчатый вид -
    в столбце, содержащем ведущий элемент какой-то строки других ненулей нет.
    */
    static void fullAutoReduce(CMatrix& m);
 
    /**
    Проводит полную авторедукцию набора строк.
    После проведения полной авторедукции набор строк [\a from;\a to) имеет сильно ступенчатый вид -
    в столбце, содержащем ведущий элемент какой-то строки других ненулей нет. Последовательная версия.
    */
    static void fullAutoReduce(MatrixIterator from, MatrixIterator to);
 
private:
 
    /**
    Переносит из матрицы набор строк для отсылки на заданный процессор в начале редукции.
    Выбор строк для каждого из процессоров осуществляется так, что матрица представляется в виде
    объединения непересекающихся множеств строк по всем процессорам.
    Распределение строк по процессорам относительно равномерно.
    Из исходной матрицы строки удаляются (чтоб не пришлось их копировать).
    \param res матрица, в которую записываются выбранные строки
    \param id номер процесса, для которого нужно выбрать строки
    \param N общее рассматриваемое число строк в матрице
    \param usefulProcesses общее число процессов, которое будет использоваться для этой матрицы
    \param f4options прочие параметры (размеры блоков, и т.д.)
    */
    void selectRowsForProcessor(CMatrix& res, int id, int N, int usefulProcesses,const F4AlgData* f4options);
 
    /**
    редуцирует строку \a row по строке \a by c известным обратным к ведущему.
    При редукции строки по \a by, последняя вычитается из \a row с таким коэффициентом,
    чтоб обнулить элемент \a row в ведущем столбце \a by.
    \param row строка, которая модифицируется редукцией по \a by
    \param by строка, выступающая в роли редуктора
    \param mb обратный к ведущему элементу строки \a by.
    Для нескольких вызовов с разными \a row строка \a by одинакова,
    и чтоб не вычислять обратный каждый раз заново он вычисляется и передаётся отдельно.
    */
    static void reduceRowByRow(Row& row,const Row& by, CModular mb);
 
    ///удаляет из матрицы пустые строки, начиная поиск таких с \a firstRowToSearch
    void eraseEmptyRows(unsigned firstRowToSearch=0);
 
    ///редуцирует каждую строку набора [\a mfrom;\a mto) по строке by
    static void reduceRangeByRow(MatrixIterator mfrom, MatrixIterator mto,const Row& by);
 
    //для fastReduceRangeByRange. Документировано в реализации
    struct PairCurEnd;
    struct RowCoeff;
    static bool pairCurEndComparer(const PairCurEnd& b, const PairCurEnd& a);
 
    /**
    редуцирует подматрицу по подматрице.
    редуцирует каждую строку набора [\a mfrom;\a mto) по каждой из строк [\a byfrom;\a byto).
    Функция пытается использовать блочность операции и эффективно использовать кеш процессора.
    Требуется, чтоб редуцирующий набор [\a byfrom;\a byto) был полностью авторедуцирован.
    */
    static void fastReduceRangeByRange(MatrixIterator mfrom, MatrixIterator mto, MatrixIterator byfrom, MatrixIterator byto);
public:
    /**
    \details
    используется в реализации fastReduceRangeByRange() с зафиксированным параметром \a willNotOverflow
    \tparam willNotOverflow параметр, определяющий может ли произойти переполнение int
    при простом суммировании всех слагаемых, образующих новый элемент без взятия их по модулю.
    Если он равен \c true, то взятие по модулю происходит только после суммирования,
    иначе взятие по модулю производится для каждого слагаемого (являющегося произведением двух чисел).
    Вынесен в шаблонный параметр, чтоб быть известным во время компиляции, что позволит компилятору породить более оптимальный код в самом главном внутреннем цикле программы.
    */
    template <bool willNotOverflow> static void fastReduceRangeByRangeConstOverflow(MatrixIterator mfrom, MatrixIterator mto, MatrixIterator byfrom, MatrixIterator byto);
 
    /**
    редуцирует подматрицу по матрице с заданным размером блока.
    Редуцирует каждую строку набора [\a mfrom;\a mto) по каждой из строк матрицы \a by.
    Если аргумент \a blocksize равен 1, то использзуется версия редуцирующая строки по одной через reduceRowByRow().
    При больших значениях размера блока используется блочный вариант fastReduceRangeByRange().
    Требуется, чтоб редуцирующая матрица \a by была полностью авторедуцирована.
    */
    static void reduceRangeByMatrix(MatrixIterator mfrom, MatrixIterator mto, CMatrix& by, int blocksize);
 
    /**\details
    редуцирует подматрицу по подматрице (версия для обратного хода).
    Отличается от обычной тем, что есть дополнительное предусловие:
    после редукции гарантированно не могут получиться нулевые строки
    */
    static void backReduceRangeByRange(MatrixIterator mfrom, MatrixIterator mto, MatrixIterator byfrom, MatrixIterator byto);
 
    /**Параллельная версия метода Гаусса.
    Метод Гаусса, распаралелленный с помощью MPI.
    \param f4options параметры, переданные алгоритму F4 (размеры блоков, опции статистики, и т.д.)
    \param doAutoReduce указывает на необходимость проведения авторедукции (доведения до сильно ступенчатого вида)
    */
    void MPIDiagonalForm(const F4AlgData* f4options,int doAutoReduce=true);
 
    ///Параллельно приводит матрицу к сильно ступенчатому виду (с помощью MPIDiagonalForm())
    void toDiagonalNormalForm(const F4AlgData* f4options);
    
    ///Параллельно приводит матрицу к обычному ступенчатому виду (с помощью MPIDiagonalForm())
    void toRowEchelonForm(const F4AlgData* f4options);
};
} //namespace F4MPI
#endif
Для случая толщины этих блоков большей 1 я думаю можно пробовать переводить векторы на массивы, а для случая однострочных блоков надо смотреть addRowMultypliedBy и getCoefByMonom.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru