Разбирал стандартные примеры из 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). Как мы делали это раньше?
Выполнялась она долго. Если есть желание - компильте на здоровье: текстовку выше выкиньте в файл main.cpp, создайте файл tryValarray.pro следующего содержания:
Выполнить
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 при обработке массивов больших размерностей в олимпиадах - важность критерия быстродействия программы и скорости написания кода там очевидна.
