понедельник, 29 октября 2012 г.

std::valarray и std::slice в С++

Разбирал стандартные примеры из 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). Как мы делали это раньше?
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 параметра:
  1.  slice::start  -  первый элемент в выборке 
  2.  slice::size -  количество элементов в выборке
  3.  slice::stride - шаг или расстояние между элементами, которые выбраны
 Это правда удобно и я захотел проверить быстродействие этого метода, в сравнении со старым-дедовским. Буду проверять 3 метода:


   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 при обработке массивов больших размерностей в олимпиадах - важность критерия быстродействия программы и скорости написания кода там очевидна.


3 комментария:

  1. Благодарю за интересную тему. Однако у меня получились несколько иный результаты. Все три метода примерно одно и то же время.

    ОтветитьУдалить
    Ответы
    1. Много воды утекло с тех пор...

      Удалить
    2. Intel Parralel Studio советует юзать valarray.
      При сборке с оптимизацией прирост ощущутим.

      Удалить