Разбирал стандартные примеры из CCfits. Эти ребята очень активно(не всегда оправдано) используют стандартную библиотеку C++. Как оказалось, я в ней плаваю. Сегодня я узнал о замечательном шаблоне массива С++ std - valarray и классом - slice,который позволяет очень удобно стучатся одновременно к многим элементам массива. Я провёл некоторую сравнительную характеристику и построил графики быстродействия. Хочу поскорее рассказать вам, что к чему.
valarray - одна из реализаций массива C++.Она действительно удобная. Написана она для выполнения векторных операций. Посмотрите только, какие вкусности нам предлагают. Одна из этих вкусностей - класс slice, который работает как указатель сразу на большое кол-во элементов valarray.
К примеру, у нас есть RGB картинка, записанная в одномерный массив.
std::valarray row(n); и мы хотим дать картинке определённый цвет( каждый 3*i пиксель заменить на значение R, 3*i+1 на значение G, 3*i+2 на значение B). Как мы делали это раньше?
Выполнить
qmake
make
./app
На выходе получите изображение с графиками. Справа - результат на моей машине.
Сделаем выводы:
Зависимость прямо пропорциональная у всех методов. Но у старого дедовского намного -больше коэффициент возрастания.
2 и 3 методы практически идентичны по времени исполнения и активно выигрывают у старого дедовского. Однако, третьим методом пользоваться удобней и быстрей с точки зрения скорости написания кода. Очень советую valarray и slice при обработке массивов больших размерностей в олимпиадах - важность критерия быстродействия программы и скорости написания кода там очевидна.
unsigned char red = 255; unsigned char green = 128; unsigned char blue = 0; for(int i =0;i<n; i = i 3) row[i]=red; for(int i =1;i<n;i =3) row[i]=green; for(int i =2;i<n;i =3) row[i]=blue;А с помощью групповых указателей мы можем поступить так:
slice red(1,n/3,3); slice green(2,n/3,3); slice blue(3,n/3,3); row[red]=255; row[green]=128; row[blue]=0;Удобно не правда ли?
Slice принимает 3 параметра:
Это правда удобно и я захотел проверить быстродействие этого метода, в сравнении со старым-дедовским.
Буду проверять 3 метода:
1-ый : Simple - старый добрый массив указателей в связке с циклом for
2-й : Valarray - массив valarray в связке с циклом for
3-й : Slice - массив valarray в связке с объектом slice
- slice::start - первый элемент в выборке
- slice::size - количество элементов в выборке
- slice::stride - шаг или расстояние между элементами, которые выбраны
1-ый : Simple - старый добрый массив указателей в связке с циклом for
2-й : Valarray - массив valarray в связке с циклом for
3-й : Slice - массив valarray в связке с объектом slice
Суть эксперимента: есть массив из n элементов. В этом массиве нужно заменить каждый 3 элемент массива на какое-либо значение. Замена производится 3 вышеперечисленными способами с замером быстродействия каждого. Кол-во элементов массива варьируется от 1 000 000 до 100 000 000 c с шагом в 1 000 000. Для каждого метода и кол-ва элементов массива проверка осуществляется 50 раз с нахождением среднего времени. По окончании замера производительности, построить графики зависимости времени исполнения замены от кол-ва элементов массива по 3 методам. Проанализировать динамику каждого из методов.
Цель эксперимента:
Сравнить быстродействие 3 методов доступа к элементам массива на запись.
Для построения графиков я использовал библиотеку QT. Рисовал просто на QLable, её и вывел на экран.
Ниже представлена программа реализующая вышеуказанную задачу:
#include <QApplication> #include "QPainter" #include <QLabel> #include <QRect> #include <QPixmap> #include <QDebug> #include <iostream> #include <valarray> #include <unistd.h> #include <time.h> #define ZAMENA 1 using namespace std; long Simple(long count){ int * na = new int[count]; long t1 = clock(); for(int i = 1;i<count;i =3) na[i]=ZAMENA; long t2 = clock(); delete[] na; return t2-t1; } long Valarray(long count){ std::valarray<int> a(count); long t1 = clock(); for(int i = 1;i<count;i =3) a[i]=ZAMENA; long t2 = clock(); return t2-t1; } long Slice(long count){ std::valarray<int> a (count); long t1 = clock(); slice s (1,count/3,3); a[s]=ZAMENA; long t2 = clock(); return t2-t1; } int main(int argc, char *argv[]) { int w =500; int h = 500; QColor SimplePen(255,0,0); QColor SlicePen(0,255,0); QColor ValarrayPen(0,0,255); QApplication app(argc, argv); QLabel *MainLable = new QLabel("Graphs"); MainLable->setBaseSize(w,h); QPixmap MainPixMap(w,h); MainPixMap.fill(MainLable,0,0); QPainter MainPainter(&MainPixMap); MainPainter.fillRect(MainPainter.viewport(),QColor(255,255,255)); MainPainter.setPen(SimplePen); MainPainter.drawLine(10,10,100,10); MainPainter.drawText(110,10,"Simple"); MainPainter.setPen(SlicePen); MainPainter.drawLine(10,25,100,25); MainPainter.drawText(110,25,"Slice"); MainPainter.setPen(ValarrayPen); MainPainter.drawLine(10,40,100,40); MainPainter.drawText(110,40,"Valarray"); /* * Example of drawing y = f%u043E%u043E(x) int count = 1000000; int dx = 1000; double maxy= foo(count); for(double x = dx;x<count;x =dx){ double y = foo(x); double y2 = foo(x dx); double x2 = x dx; MainPainter.drawLine((x/count)*w,h-((y/maxy)*h),(x2/count)*w,h-((y2/maxy)*h)); } */ int count_tests =50; long n = 100000000; long dx = 1000000; long *args = new long[n/dx]; long *SimpleTimes = new long[n/dx]; long *SliceTimes = new long[n/dx]; long *ValarrayTimes = new long[n/dx]; for (int i = 0 ;i<n/dx;i ){ args[i]=dx*i; } long max =0; qDebug()<<"Simple begins"; for (int j=0 ;j<n/dx-1;j ){ long S=0; for (int i = 0;i<count_tests;i ) S =Simple(args[j]); S = S/count_tests; SimpleTimes[j]=S; max = max<S?S:max; if (j%10==0) qDebug()<<j; } qDebug()<<"Simple ends"; qDebug()<<"Valarray begins"; for (int j=0 ;j<n/dx-1;j ){ long S=0; for (int i = 0;i<count_tests;i ) S =Valarray(args[j]); S = S/count_tests; ValarrayTimes[j]=S; max = max<S?S:max; if (j%10==0) qDebug()<<j; } qDebug()<<"ValarrayTimes ends"; qDebug()<<"Slice begins"; for (int j=0 ;j<n/dx-1;j ){ long S=0; for (int i = 0;i<count_tests;i ) S =Slice(args[j]); S = S/count_tests; SliceTimes[j]=S; max = max<S?S:max; if (j%10==0) qDebug()<<j; } qDebug()<<"Slice ends"; qDebug() <<"max"<< max; for (int j=0 ;j<n/dx-2;j ){ MainPainter.setPen(SimplePen); MainPainter.drawLine(w*args[j]/n,h-(h*SimpleTimes[j]/max),w*args[j 1]/n,h-(h*SimpleTimes[j 1]/max)); MainPainter.setPen(SlicePen); MainPainter.drawLine(w*args[j]/n,h-(h*SliceTimes[j]/max),w*args[j 1]/n,h-(h*SliceTimes[j 1]/max)); MainPainter.setPen(ValarrayPen); MainPainter.drawLine(w*args[j]/n,h-(h*ValarrayTimes[j]/max),w*args[j 1]/n,h-(h*ValarrayTimes[j 1]/max)); } MainLable->setPixmap(MainPixMap); MainLable->show(); return app.exec(); }Выполнялась она долго. Если есть желание - компильте на здоровье: текстовку выше выкиньте в файл main.cpp, создайте файл tryValarray.pro следующего содержания:
TARGET = app SOURCES += main.cpp \
Выполнить
qmake
make
./app
На выходе получите изображение с графиками. Справа - результат на моей машине.
Сделаем выводы:
Зависимость прямо пропорциональная у всех методов. Но у старого дедовского намного -больше коэффициент возрастания.
2 и 3 методы практически идентичны по времени исполнения и активно выигрывают у старого дедовского. Однако, третьим методом пользоваться удобней и быстрей с точки зрения скорости написания кода. Очень советую valarray и slice при обработке массивов больших размерностей в олимпиадах - важность критерия быстродействия программы и скорости написания кода там очевидна.
Благодарю за интересную тему. Однако у меня получились несколько иный результаты. Все три метода примерно одно и то же время.
ОтветитьУдалитьМного воды утекло с тех пор...
УдалитьIntel Parralel Studio советует юзать valarray.
УдалитьПри сборке с оптимизацией прирост ощущутим.