Как сделать оптимизацию

[SubaroMows]

Имею дело с матрицами размером 20 x 1000000, по сути в этой матрице храню -1 или 1.(бинарные изображения).
Хотелось бы спросить, какую структуру выбрать для представления этой матрицы, чтобы работало быстрее.

Пока остановился на quint8[][]

[V1KT0P]

Имею дело с матрицами размером 20 x 1000000, по сути в этой матрице храню -1 или 1.(бинарные изображения).
Хотелось бы спросить, какую структуру выбрать для представления этой матрицы, чтобы работало быстрее.

Пока остановился на quint8[][]

Смотря как ты их будешь обрабатывать. Думаю лучше всего quint32 для 32 битных систем и quint64 для 64 битных.

[kambala]

почему бы не использовать тип bool для уменьшения потребления памяти?

[V1KT0P]

почему бы не использовать тип bool для уменьшения потребления памяти?

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

[Igors]

почему бы не использовать тип bool для уменьшения потребления памяти?

Это скользкое дело - bool может быть и 4 байта (замешан компилятор, за это получал когда переходили на Xcode)

Имею дело с матрицами размером 20 x 1000000, по сути в этой матрице храню -1 или 1.(бинарные изображения).
Хотелось бы спросить, какую структуру выбрать для представления этой матрицы, чтобы работало быстрее.

Пока остановился на quint8[][]

Если хранятся бинарные данные - то и хранить их надо бинарно (в виде битов). А с матрицей надо подровняться на строку. Итого

Код

C++ (Qt)
struct CBinMatrix {
 CBinMatrix (int row, int col )  // row = 100000, col = 20
 {
   mColBytes = (col + 7) / 8;
   mRow = row;
   mData = new unsigned char[mColBytes * mRow);
 }
 
 ~CBinMatrix( void ) 
  {
    delete [] mData;
  }
 
 bool Get( int row, int col ) const 
 {
   unsigned char src = *(mData + row * mColBytes + col / 8); 
   return (src & (1 << (col % 8))) != 0;
 }
 
 bool Set( int row, int col. bool val ) 
 {
// напишите по образцу Get
 }
 
// data 
 size_t mColBytes. mRow;
 unsigned char * mData;
};
 

почему бы не использовать тип bool для уменьшения потребления памяти?

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

Ой  

Edit: пропустил сдвиг, подправил

[m_ax]

Код

C++ (Qt)
 bool Get( int row, int col ) const 
 {
   unsigned char src = *(mData + row * mColBytes + col / 8); 
   return (src & (col % 8)) != 0;
 }
 

Да, это конечно же, будет быстрый доступ к элементу)

Опять смайлик забыл поставить.. 

[Igors]

Да, это конечно же, будет быстрый доступ к элементу)

Опять смайлик забыл поставить.. 

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

Код

C++ (Qt)
*(data + row * mColBytes + col);   // data[row][col]
 

Все равно умножение, сложение потом инкремент указателя. Сравнивая этот вариант с предыдущим - да, у того на неск действий больше, но каждое из них - практически одна машинная команда. Вес операций доступа не так уж велик, поэтому брать в 8(!) раз больше памяти чтобы ускориться на пару процентов - никак не правильно. Не то это место где выжимать скорость

[SubaroMows]

Igors, спасибо. Сделаю замеры по времени работы вышей структуры и просто массива. Выложу результаты

[V1KT0P]

Igors, спасибо. Сделаю замеры по времени работы вышей структуры и просто массива. Выложу результаты

Я вот тут сделал замеры(просто перебор всех значений):

Массив CBinMatrix bool to bool uint8 to bool quint32 to bool uint8 to uint8 uint32 to uint32

Затраченное время 0.055737 0.0408991 0.0408365 0.0408429 0.00579459 0.00578789

Отношение к самому быстрому 9.5 7 7 7 1 1

Как я и говорил приведение к биту довольно таки тяжелая операция, в данном случае замедлила все в 7 раз. Самодельная структура так вообще почти в 10 раз медленее тупого массива.
Странно что разницы между uint8 и uint32 нету.

[Igors]

Как я и говорил приведение к биту довольно таки тяжелая операция, в данном случае замедлила все в 7 раз. Самодельная структура так вообще почти в 10 раз медленее тупого массива.
Странно что разницы между uint8 и uint32 нету.

Интересно, только выложите проект. Меня удивляет откуда "bool to bool" 7 

[V1KT0P]

Как я и говорил приведение к биту довольно таки тяжелая операция, в данном случае замедлила все в 7 раз. Самодельная структура так вообще почти в 10 раз медленее тупого массива.
Странно что разницы между uint8 и uint32 нету.

Интересно, только выложите проект. Меня удивляет откуда "bool to bool" 7 

Ну там массив bool и результирующая переменная bool.
Можно попробовать еще какие-то варианты =).

[m_ax]

Тест какой то неадекватный..

Согласен лишь с тем, что вариант Igors будет в любом случае самым медленным.

Да и ещё, можно сравнить c std::vector<dool>. Для bool у вектора написана специализация, оптимизированная под все эти операции. Думаю с вектором получатся самые лучшие характеристики.
Но это нужно проверять... На нормальных тестах) 

[V1KT0P]

Тест какой то неадекватный..
Чем это неадекватный? Тестируется скорость доступа к элементу, что тут неадекватного?

[m_ax]

Чем это неадекватный? Тестируется скорость доступа к элементу, что тут неадекватного?

Во-первых нафига для этого прикручивать Qt гуй? К тому же всё равно прога работает только под виндос.. Обидно..
Во-вторых:
сравним вариант для binMatrix

Код

C++ (Qt)
Timer timer;
    CBinMatrix binMatrix(ROWS, COLS);
    bool d = false;
    timer.Init();
    for (size_t i=0; i<ROWS; i++) {
        for (size_t k=0; k<COLS; k++) {
            d += binMatrix.Get(i, k);
        }
    }
    double delta = timer.GetDelta();
    qDebug() << d << "BinM " << delta;
 

с вариантом:

Код

C++ (Qt)
Timer timer;
    bool **matrix = new bool*[ROWS];
    for (size_t i=0; i<ROWS; i++)
        matrix[ROWS] = new bool[COLS];
    bool d = false;
    timer.Init();
    for (size_t i=0; i<ROWS; i++) {
        for (size_t k=0; k<COLS; k++) {
            d += matrix[ROWS][COLS];
        }
    }
    for (size_t i=0; i<ROWS; i++)
        delete matrix[i];
    delete *matrix;
    double delta = timer.GetDelta();
    qDebug() << d << "bool " << delta;
 

В последним варианте учитывается ещё время на уничтожение массива, в то время, как в первом варианте, при замере времени, массив ещё был жив и разрушится уже после.

В-третьих..

Короче, лучше переписать это нормально, без всяких привлечений "windows.h" и вообще гуя...  

Да, и ещё:
Лучше удалять массив так:

Код

C++ (Qt)
 for (size_t i=0; i<ROWS; i++)
        delete []matrix[i];
 delete []matrix;
 

   

[Igors]

Ну там массив bool и результирующая переменная bool.
Можно попробовать еще какие-то варианты =).

Не могу откомпилить на своей платформе (не имею windows.h). Ладно, вот мой тест, у меня (icc release) печатает

TestMatr
fill with qrand time = 5.97 s                     // заполнить случайными 0/1
fill time = 0.82 s                                     // заполнить чередующимися 0/1
sum = 167772160, read time = 0.41 s     // сумма всех элементов
sumNear = 364904216, time = 3.13 s      // сумма матриц 3x3

TestArray
fill with qrand time = 5.88 s
fill time = 0.38 s
sum = 167772160, read time = 0.10 s
sumNear = 364904332, time = 1.43 s

Я оцениваю это дело так: когда идет "только (голое) обращение" - массив быстрее в 4 раза (хотя и не в 10). Но как только вмешивается др код - зффект быстро исчезает. Напр sumNear складывает всех соседей пикселя - вроде тоже обращение, добавлены лишь проверки на границы. Тем не менее выигрыш уже только в 2 раза. А вызов скромного qrand вообще убивает в ноль.

Также возможно что при бОльших размерах данных (сотни мегабайт) битовые данные будут "просто быстрее" за счет того что используемый диапазон адресов меньше (дела кэша)