#include <vector>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
vvi array;
int main() {
array.push(vvi());
array[0].push(vi());
array[0][0].push(5);
printf("array[0][0][0] = %d", array[0][0][0]);
}
3х мерный динамический массив
Это похоже на извращение, но мне нужно создать, заполнить а также, если понадобиться, добавлять в него данные. Плизз напишите пример :)
Код:
Вроде должно работать.
Это на C++, с использованием stl;
В C# наверняка есть анологичный вектору тип данных
Цитата: P*t*
Код:
#include <vector>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
vvi array;
int main() {
array.push(vvi());
array[0].push(vi());
array[0][0].push(5);
printf("array[0][0][0] = %d", array[0][0][0]);
}
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
vvi array;
int main() {
array.push(vvi());
array[0].push(vi());
array[0][0].push(5);
printf("array[0][0][0] = %d", array[0][0][0]);
}
Вроде должно работать.
Это на C++, с использованием stl;
В C# наверняка есть анологичный вектору тип данных
Здесь ты не создаешь трехмерный массив.
Обращение к любой другой ячейки, а не к (0,0,0) приведет к ошибке.
Кроме того, в С++ лучше уж пользоваться typedef, а не #define.
С учетом сказанного:
Код:
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
vvvi array(size0, vvi(size1, vi(size2))); // создание массива
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
vvvi array(size0, vvi(size1, vi(size2))); // создание массива
ну или так:
Код:
typedef vector< vector< vector<int> > > vector3d;
vector3d array(size0, vector3d::value_type(size1, vector3d::value_type::value_type(size2)));
vector3d array(size0, vector3d::value_type(size1, vector3d::value_type::value_type(size2)));
P.S. А вообще, нужно пользоваться поиском по форуму. Мы как-то даже обсуждали шаблон N-мерного массива.
boost::multi_array
http://boost.org/libs/multi_array/doc/index.html
http://boost.org/libs/multi_array/doc/index.html
Цитата: cheburator
boost::multi_array
http://boost.org/libs/multi_array/doc/index.html
http://boost.org/libs/multi_array/doc/index.html
Хотя boost-ом пользуюсь, но его::multi_array не видел.
Забавно, что он внешне похож на мой (ради разминки написанный):
http://forum.codenet.ru/showpost.php?p=155443&postcount=12
Задание размерностей в boost, конечно, по-изящнее, чем мой dims.
Надо будет запомнить этот прием.
А руками считать не проще?
array [ i + j*i_size + k*i_size*j_size]
Быстрее и никаких проблем и тормозов с классами.
Код:
i_size x j_size x k_size
* * * * * * * * * * k_size
/ /*
/ k / *
0 / i / *
* * * * * * * * * * *
* * * * * * * * * * *
* * * * * * * * * * *
j * * * * * * * * * * /
* * * * * * * * * * /
* * * * * * * * * * /
j_size * * * * * * * * * *
i_size
offset = i + j*i_size + k*i_size*j_size
* * * * * * * * * * k_size
/ /*
/ k / *
0 / i / *
* * * * * * * * * * *
* * * * * * * * * * *
* * * * * * * * * * *
j * * * * * * * * * * /
* * * * * * * * * * /
* * * * * * * * * * /
j_size * * * * * * * * * *
i_size
offset = i + j*i_size + k*i_size*j_size
array [ i + j*i_size + k*i_size*j_size]
Быстрее и никаких проблем и тормозов с классами.
Цитата: Vov4ick
А руками считать не проще?
array [ i + j*i_size + k*i_size*j_size]
Быстрее и никаких проблем и тормозов с классами.
array [ i + j*i_size + k*i_size*j_size]
Быстрее и никаких проблем и тормозов с классами.
Это уже C
Цитата: Vov4ick
А руками считать не проще?
array [ i + j*i_size + k*i_size*j_size]
Быстрее и никаких проблем и тормозов с классами.
array [ i + j*i_size + k*i_size*j_size]
Быстрее и никаких проблем и тормозов с классами.
Конечно же проще, а еще очень просто считать руками если потребуется расширить размерность массива.. :D
Dart Bobr Нет проблем. Думаю по аналогии несложно самому достроить многочлен для необходимой размерности ;-)
Цитата:
А мы с классами не "тормозим"...
Ну так и программу выполняем не мы ;-P
Цитата: Vov4ick
Dart Bobr Нет проблем. Думаю по аналогии несложно самому достроить многочлен для необходимой размерности ;-)
Ну так и программу выполняем не мы ;-P
Ну так и программу выполняем не мы ;-P
А какое отношение имеют классы к быстродействию? :P
Цитата: Vov4ick
Dart Bobr Нет проблем. Думаю по аналогии несложно самому достроить многочлен для необходимой размерности ;-)
Ну так и программу выполняем не мы ;-P
Ну так и программу выполняем не мы ;-P
Дострой и встрой это в класс.
"Тормозов" не вижу. Если они и есть - они должны оптимизироваться компилятором.
Видимо, под "тормозами" подразумевается передача "лишнего" параметра this? Хорошо, а тот же array, передаваемый в функцию, не являющуюся методом класса - не параметр?
P. S. Многие короткие, редко вызываемые и т. п. функции "превращаются" в инлайн. Даже виртуальные и рекурсивные. Если нет - пора менять компилятор. Хотя это имеет мало отношения к теме.
В любом случае, Green прав ровно на 100%. В данном конкретном случае ООП никакого отношения к "тормозам" не имеет.
Все равно, что считать, будто
Код:
int make2x (int x)
{
return 2*x;
}
int make5x(int x)
{
return 5*x;
}
{
return 2*x;
}
int make5x(int x)
{
return 5*x;
}
будет работать хуже, чем
Код:
template <int I>
int makeIx (int x)
{
return I*x;
}
int makeIx (int x)
{
return I*x;
}
Я не думаю, что метод класса работает именно так, как вы описали)
Вообще выбор - личное дело каждого ;-)
Вообще выбор - личное дело каждого ;-)
Цитата: Vov4ick
Я не думаю, что метод класса работает именно так, как вы описали)
Вообще выбор - личное дело каждого ;-)
Вообще выбор - личное дело каждого ;-)
Собственно говоря, уважаемый, а что именно, по вашему, должно тормозить в реализации с классами?
выбор! выбор будет тормозить )))
Который личное дело )
Который личное дело )
//----------создает массив--------------------------
int ***Init(int ***ss,int size1,int size2,int size3)
{
int i,j,k;
ss=malloc(size1*sizeof(int));
for(i=0;i<size1;i++)
ss=malloc(size2*sizeof(int));
for(j=0;j<size2;j++)
for(k=0;k<size3;k++)
ss[j][k]=malloc(size3*sizeof(int));
return ss;
}
//----------заполняет массив--------------------------
void FillBigMas(int ***tt,int size1,int size2,int size3)
{
int i,j,k;
for(i=0;i<size1;i++)
for(j=0;j<size2;j++)
for(k=0;k<size3;k++)
tt[j][k]=i;
}
//-------выводит на экран-----------------------------
void ShowBigMas(int ***uu,int size1,int size2, int size3)
{
int i,j,k;
for(i=0;i<size1;i++)
for(j=0;j<size2;j++)
for(k=0;k<size3;k++)
printf("%4d",uu[j][k]);
}
//----------удаляет массив--------------------------
void AntiInit(int ***pp,int size1,int size2,int size3)
{
int i,j,k;
for(j=size2-1;j>0;j--)
for(k=size3-1;k>0;k--)
free(pp[j][k]);
for(i=size1-1;i>0;i--)
free(pp);
free(pp);
}
P.S. В функции main() нужно описать тройной указатель (на пример int ***A)
int ***Init(int ***ss,int size1,int size2,int size3)
{
int i,j,k;
ss=malloc(size1*sizeof(int));
for(i=0;i<size1;i++)
ss=malloc(size2*sizeof(int));
for(j=0;j<size2;j++)
for(k=0;k<size3;k++)
ss[j][k]=malloc(size3*sizeof(int));
return ss;
}
//----------заполняет массив--------------------------
void FillBigMas(int ***tt,int size1,int size2,int size3)
{
int i,j,k;
for(i=0;i<size1;i++)
for(j=0;j<size2;j++)
for(k=0;k<size3;k++)
tt[j][k]=i;
}
//-------выводит на экран-----------------------------
void ShowBigMas(int ***uu,int size1,int size2, int size3)
{
int i,j,k;
for(i=0;i<size1;i++)
for(j=0;j<size2;j++)
for(k=0;k<size3;k++)
printf("%4d",uu[j][k]);
}
//----------удаляет массив--------------------------
void AntiInit(int ***pp,int size1,int size2,int size3)
{
int i,j,k;
for(j=size2-1;j>0;j--)
for(k=size3-1;k>0;k--)
free(pp[j][k]);
for(i=size1-1;i>0;i--)
free(pp);
free(pp);
}
P.S. В функции main() нужно описать тройной указатель (на пример int ***A)
(ц) Borland help. Ради трёхмерного массива разводить канитель с массивами указателей - увольте. Уж куда проще и быстрее сделать ...alloc необходимого куска памяти и обращаться к элементам массива как я написал когда-то выше, минуя последовательность указателей и разное ООП.
Этот метод напоминает очень отдалённо метод Айлиффа, но не даёт его главного преимущества - скорости доступа. Да и метод Айлиффа применяется при составлении массивов сложных структур, где размер структуры много больше размера указателя.
Этот метод напоминает очень отдалённо метод Айлиффа, но не даёт его главного преимущества - скорости доступа. Да и метод Айлиффа применяется при составлении массивов сложных структур, где размер структуры много больше размера указателя.
М-да... не ищите легких путей...
Цитата: Vov4ick
минуя последовательность указателей и разное ООП.
а это смешно и характеризует Vov4ick как программиста... :)
Не стыдился бы хоть.
Green, я имел в виду не этот пост, а предыдущие конечно. Не цепляйтесь к словам.
Vov4ick, а вы MFC используете, или предпочитаете рисовать кнопочки вручную, чтоб проще было и "тормозов" с класами не было?? Ну, согласитесь, что легче использовать то, что уже давным-давно написано, миллионы раз протестировано и реально работает, чем писать каждый раз свой код. А учитывая то, что STL написан гибко, то использовать его намного проще, чем каждый раз "изобретать велосипед". Не хватает STL - boost в помощь. И нет никаких "тормозов с классами", это просто популярный миф, так как вызов процедуры и метода класса происходят практически одинаково, единственным "тормозом" может служить использование виртуальных методов, да и то, вы этого в своей программе скорей всего не ощутите.
Цитата: Dart Bobr
единственным "тормозом" может служить использование виртуальных методов
Ага! В общем случае, аж на целых две инструкции mov больше! :D
Угу)) Я ж и написал "тормозом", а не тормозом))
У всех разные понятия о велосипеде. Очевидную формулу, которую получит даже школьник за пару минут и запрограмит за полминуты, извините меня, но я велосипедом ну никак назвать не могу. К тому же я знаю, как эта реализация работает, в отличие от реализации STL)
Green Не будем голословны. Листинг в студию! :-P
Green Не будем голословны. Листинг в студию! :-P
Цитата: Vov4ick
К тому же я знаю, как эта реализация работает, в отличие от реализации STL)
STL не работает? :D
Не будь голословным, нерабочий тест в студию.
Цитата: Vov4ick
Green Не будем голословны. Листинг в студию! :-P
Я знаю, как устроены вызовы обычных и виртуальных методов.
А ты знаешь? Думаю, тебе будет полезнее сделать такой листинг.
Хочу отметить немаловажные моменты обоих подходов реализации (через один линейный массив и через массив массивов) - используемая память и призводительность.
1. В реализации мульти-массива используемая память зависит не только от размерностей массива, но и от того, в каком порядке они следуют(!). Возьмем шаблон, предложенный Green, и переставим размерности:
и
Для этих двух вариантов посмотрите объем используемой памяти и все станет ясно. Все дело в том, что массив кушает памяти больше чем нужно для хранения одних элементов. Поэтому чем больше мелких массивов, тем больший объем используется в служебных целях.
Для реализации через линейный массив с памятью все замечательно.
2. Производительность конечно же падает при использовании линейного массива на вычисление адреса в массиве (умножение и сложение). При использовании же мульти-массива никакой арифметики нет, время расходуется только на переход от адреса к адресу.
1. В реализации мульти-массива используемая память зависит не только от размерностей массива, но и от того, в каком порядке они следуют(!). Возьмем шаблон, предложенный Green, и переставим размерности:
Код:
typedef std::vector<int> vi;
typedef std::vector<vi> vvi;
typedef std::vector<vvi> vvvi;
const int size0 = 4;
const int size1 = 100;
const int size2 = 10000;
vvvi arr(size0, vvi(size1, vi(size2)));
typedef std::vector<vi> vvi;
typedef std::vector<vvi> vvvi;
const int size0 = 4;
const int size1 = 100;
const int size2 = 10000;
vvvi arr(size0, vvi(size1, vi(size2)));
и
Код:
typedef std::vector<int> vi;
typedef std::vector<vi> vvi;
typedef std::vector<vvi> vvvi;
const int size0 = 10000;
const int size1 = 100;
const int size2 = 4;
vvvi arr(size0, vvi(size1, vi(size2)));
typedef std::vector<vi> vvi;
typedef std::vector<vvi> vvvi;
const int size0 = 10000;
const int size1 = 100;
const int size2 = 4;
vvvi arr(size0, vvi(size1, vi(size2)));
Для этих двух вариантов посмотрите объем используемой памяти и все станет ясно. Все дело в том, что массив кушает памяти больше чем нужно для хранения одних элементов. Поэтому чем больше мелких массивов, тем больший объем используется в служебных целях.
Для реализации через линейный массив с памятью все замечательно.
2. Производительность конечно же падает при использовании линейного массива на вычисление адреса в массиве (умножение и сложение). При использовании же мульти-массива никакой арифметики нет, время расходуется только на переход от адреса к адресу.
1. Ну, мне например сложно представить задачу для решения которой требйется больше чем 3д-массив.. Количество памяти.. ну да.. будет больше. Обычная логика показывает, что необходимо для массива n^3 еще (n^2 + n) памяти..
2. Ну, как мне кажется, что все-таки в случае с STL реализацией адрес все-таки тоже вычисляется, просто неявно.. Быстрее будет вряд ли, но удобней - однозначно..
Vov4iсk, ну, если вы считаете, что описывать массив таким образом и вычислять каждый раз адрес элемента, а при необходимости расширить массив пересчитывать индексы, не является "изобретением велосипеда", то что я еще могу тут сказать. Мне почему-то кажется, что написать 3 строчки для иннициализации массива, проще, учитывая, что потом при обращение к его элементам не нужно ничего вычислять(да-да, это не сложно, а если у вас в коде 200 раз происходит такое обращение, 2000 раз? напишите функцию для этого, которая сможет из трех индексов вычислять исходный? а для 2д массивов еще одну функцию? а для 4д еще одну?а пока вы будете этим заниматься я с помощью STL уже буду иметь готовый код, причем заметьте без лишнего геморроя. :P ).
2. Ну, как мне кажется, что все-таки в случае с STL реализацией адрес все-таки тоже вычисляется, просто неявно.. Быстрее будет вряд ли, но удобней - однозначно..
Vov4iсk, ну, если вы считаете, что описывать массив таким образом и вычислять каждый раз адрес элемента, а при необходимости расширить массив пересчитывать индексы, не является "изобретением велосипеда", то что я еще могу тут сказать. Мне почему-то кажется, что написать 3 строчки для иннициализации массива, проще, учитывая, что потом при обращение к его элементам не нужно ничего вычислять(да-да, это не сложно, а если у вас в коде 200 раз происходит такое обращение, 2000 раз? напишите функцию для этого, которая сможет из трех индексов вычислять исходный? а для 2д массивов еще одну функцию? а для 4д еще одну?а пока вы будете этим заниматься я с помощью STL уже буду иметь готовый код, причем заметьте без лишнего геморроя. :P ).
Привожу сравнительную характеристику для трех реализаций с разной конфигурацией массивов:
500,500,500: Green - 1.329, Vov4ick - 6.578, Boost: 4.563
10000,100,100: Green - 1.063, Vov4ick - 1.219, Boost: 3.656
100,100,10000: Green - 1.063, Vov4ick - 5.078, Boost: 3.641
Код:
{
typedef std::vector<char> vi;
typedef std::vector<vi> vvi;
typedef std::vector<vvi> vvvi;
vvvi A(size0, vvi(size1, vi(size2)));
const clock_t t = clock();
for (int i=0; i < size0; i++)
for (int j=0; j < size1; j++)
for (int k=0; k < size2; k++)
A[j][k] = char(i*j*k);
cout << "Green: " << float(clock() - t) / CLOCKS_PER_SEC << std::endl;
}
{
std::vector<char> A(size0 * size1 * size2);
const clock_t t = clock();
for (int i=0; i < size0; i++)
for (int j=0; j < size1; j++)
for (int k=0; k < size2; k++)
A[i + j * size0 +k * size0 * size1] = char(i*j*k);
cout << "Vov4ick: " << float(clock() - t) / CLOCKS_PER_SEC << std::endl;
}
{
typedef boost::multi_array<char, 3> array_type;
array_type A(boost::extents[size0][size1][size2]);
const clock_t t = clock();
for (int i=0; i < size0; i++)
for (int j=0; j < size1; j++)
for (int k=0; k < size2; k++)
A[j][k] = char(i*j*k);
cout << "Boost: " << float(clock() - t) / CLOCKS_PER_SEC << std::endl;
}
typedef std::vector<char> vi;
typedef std::vector<vi> vvi;
typedef std::vector<vvi> vvvi;
vvvi A(size0, vvi(size1, vi(size2)));
const clock_t t = clock();
for (int i=0; i < size0; i++)
for (int j=0; j < size1; j++)
for (int k=0; k < size2; k++)
A[j][k] = char(i*j*k);
cout << "Green: " << float(clock() - t) / CLOCKS_PER_SEC << std::endl;
}
{
std::vector<char> A(size0 * size1 * size2);
const clock_t t = clock();
for (int i=0; i < size0; i++)
for (int j=0; j < size1; j++)
for (int k=0; k < size2; k++)
A[i + j * size0 +k * size0 * size1] = char(i*j*k);
cout << "Vov4ick: " << float(clock() - t) / CLOCKS_PER_SEC << std::endl;
}
{
typedef boost::multi_array<char, 3> array_type;
array_type A(boost::extents[size0][size1][size2]);
const clock_t t = clock();
for (int i=0; i < size0; i++)
for (int j=0; j < size1; j++)
for (int k=0; k < size2; k++)
A[j][k] = char(i*j*k);
cout << "Boost: " << float(clock() - t) / CLOCKS_PER_SEC << std::endl;
}
500,500,500: Green - 1.329, Vov4ick - 6.578, Boost: 4.563
10000,100,100: Green - 1.063, Vov4ick - 1.219, Boost: 3.656
100,100,10000: Green - 1.063, Vov4ick - 5.078, Boost: 3.641
Цитата: Dart Bobr
Обычная логика показывает, что необходимо для массива n^3 еще (n^2 + n) памяти..
Вот эта самая обычная логика показывает, что объем имеет квадратичную зависимость. Вам не кажется, что это многовато?
Цитата: vAC
Привожу сравнительную характеристику для трех реализаций с разной конфигурацией массивов:
500,500,500: Green - 1.329, Vov4ick - 6.578, Boost: 4.563
10000,100,100: Green - 1.063, Vov4ick - 1.219, Boost: 3.656
100,100,10000: Green - 1.063, Vov4ick - 5.078, Boost: 3.641
Код:
{
typedef std::vector<char> vi;
typedef std::vector<vi> vvi;
typedef std::vector<vvi> vvvi;
vvvi A(size0, vvi(size1, vi(size2)));
const clock_t t = clock();
for (int i=0; i < size0; i++)
for (int j=0; j < size1; j++)
for (int k=0; k < size2; k++)
A[j][k] = char(i*j*k);
cout << "Green: " << float(clock() - t) / CLOCKS_PER_SEC << std::endl;
}
{
std::vector<char> A(size0 * size1 * size2);
const clock_t t = clock();
for (int i=0; i < size0; i++)
for (int j=0; j < size1; j++)
for (int k=0; k < size2; k++)
A[i + j * size0 +k * size0 * size1] = char(i*j*k);
cout << "Vov4ick: " << float(clock() - t) / CLOCKS_PER_SEC << std::endl;
}
{
typedef boost::multi_array<char, 3> array_type;
array_type A(boost::extents[size0][size1][size2]);
const clock_t t = clock();
for (int i=0; i < size0; i++)
for (int j=0; j < size1; j++)
for (int k=0; k < size2; k++)
A[j][k] = char(i*j*k);
cout << "Boost: " << float(clock() - t) / CLOCKS_PER_SEC << std::endl;
}
typedef std::vector<char> vi;
typedef std::vector<vi> vvi;
typedef std::vector<vvi> vvvi;
vvvi A(size0, vvi(size1, vi(size2)));
const clock_t t = clock();
for (int i=0; i < size0; i++)
for (int j=0; j < size1; j++)
for (int k=0; k < size2; k++)
A[j][k] = char(i*j*k);
cout << "Green: " << float(clock() - t) / CLOCKS_PER_SEC << std::endl;
}
{
std::vector<char> A(size0 * size1 * size2);
const clock_t t = clock();
for (int i=0; i < size0; i++)
for (int j=0; j < size1; j++)
for (int k=0; k < size2; k++)
A[i + j * size0 +k * size0 * size1] = char(i*j*k);
cout << "Vov4ick: " << float(clock() - t) / CLOCKS_PER_SEC << std::endl;
}
{
typedef boost::multi_array<char, 3> array_type;
array_type A(boost::extents[size0][size1][size2]);
const clock_t t = clock();
for (int i=0; i < size0; i++)
for (int j=0; j < size1; j++)
for (int k=0; k < size2; k++)
A[j][k] = char(i*j*k);
cout << "Boost: " << float(clock() - t) / CLOCKS_PER_SEC << std::endl;
}
500,500,500: Green - 1.329, Vov4ick - 6.578, Boost: 4.563
10000,100,100: Green - 1.063, Vov4ick - 1.219, Boost: 3.656
100,100,10000: Green - 1.063, Vov4ick - 5.078, Boost: 3.641
Случай вовчика оптимизируется вот так:
i + j * size0 +k * size0 * size1 в i + size0 * ( j +k * size1)
к тому же, думаю он будет против вектора в своей реализации :)
многовато? отнюдь. если у нас есть набор массив, то для того чтобы сделать двумерный массив мы грубо говоря создаем массив указателей на исходные масивы. следовательно получаем для n^2 еще нужно дополнительно n памяти.. Для n^3 рассуждения аналогичны.
Цитата: Dart Bobr
Случай вовчика оптимизируется вот так:
i + j * size0 +k * size0 * size1 в i + size0 * ( j +k * size1)
к тому же, думаю он будет против вектора в своей реализации :)
i + j * size0 +k * size0 * size1 в i + size0 * ( j +k * size1)
к тому же, думаю он будет против вектора в своей реализации :)
Если использовать компилятор от дяди Васи, то это действительно поможет :)
Цитата: Dart Bobr
многовато? отнюдь. если у нас есть набор массив, то для того чтобы сделать двумерный массив мы грубо говоря создаем массив указателей на исходные масивы. следовательно получаем для n^2 еще нужно дополнительно n памяти.. Для n^3 рассуждения аналогичны.
Dart Bobr, больше практики, что вы нам математику за 6-й класс рассказываете.
В приведенном мной примере объем используемой памяти был от 4 Мб до 32Мб при одинаковой размерности. (Сейчас наверно скажут: "да сейчас объем памяти дешевеет, а время программиста дорожает" - неприемлю такого подхода :)). Я бы задумался перед тем как использовать ту или иную реализацию. Я не говорою, что что-то - хорошее, а что-то - плохое. Нужно иметь на вооружении все реализации и применять каждую исходя из требований, нет оптимального решения для всех задач. А фразы типа таких: "Я сомневаюсь, что такое где-либо понадобиться..." принадлежат обычно тем, у кого мало практического опыта.
Собственно говоря никто не сомневается, что где-нибудь, возможно тот или иной метод понадобится. Всегда могут быть разные условия. Ну, как минимум предложеный метод с постоянным вычислением адреса, может пригодиться при решеии олимпиадных задач, где нельзя использовать ничего кроме стандарта языка. :) И все же время - это самое ценное что у нас есть. Именно время разработки :) Все, иду работать, и так тут много времени потратил на демагогию, щас коситься начнут. :)
Совсем забыл... Во втором тесте заполнение делалось таким образом, что адреса обращений сильно разнились. Поэтому это тоже немаловажный фактор - порядок заполнения. В связи с этим поменял структуру циклов для этого теста и добавил еще один тест...назову это не реализацией, а подходом заполнения, на практике очень часто пользуюсь :)
500,500,500: Green - 1.359; Vov4ick - 0.516; Boost - 4.578; vAC - 0.234
10000,100,100: Green - 1.063; Vov4ick - 0.375; Boost - 3.672; vAC - 0.187
100,100,10000: Green - 1.063; Vov4ick - 0.359; Boost - 3.672; vAC - 0.187
Поэтому производительность может скакать очень :)
Код:
for (int i=0; i < size0; i++)
{
p_a = &A[i * size1 * size2];
for (int j=0; j < size1; j++)
{
p_b = p_a + j * size2;
for (int k=0; k < size2; k++)
{
p_b[k] = char(i*j*k);
}
}
}
{
p_a = &A[i * size1 * size2];
for (int j=0; j < size1; j++)
{
p_b = p_a + j * size2;
for (int k=0; k < size2; k++)
{
p_b[k] = char(i*j*k);
}
}
}
500,500,500: Green - 1.359; Vov4ick - 0.516; Boost - 4.578; vAC - 0.234
10000,100,100: Green - 1.063; Vov4ick - 0.375; Boost - 3.672; vAC - 0.187
100,100,10000: Green - 1.063; Vov4ick - 0.359; Boost - 3.672; vAC - 0.187
Поэтому производительность может скакать очень :)
А теперь результаты со случайным доступом к элементам (индексы заранее сформированы и одинаковые для каждого теста).
500,500,500: Green - 2.453; Vov4ick - 2.11; Boost - 5.703; vAC - хотелось бы :)
10000; 100; 100: Green: 1.968; Vov4ick - 1.594; Boost - 4.578;
100; 100; 10000: Green: 2.016; Vov4ick - 1.625; Boost - 4.594;
победила дружба :)
500,500,500: Green - 2.453; Vov4ick - 2.11; Boost - 5.703; vAC - хотелось бы :)
10000; 100; 100: Green: 1.968; Vov4ick - 1.594; Boost - 4.578;
100; 100; 10000: Green: 2.016; Vov4ick - 1.625; Boost - 4.594;
победила дружба :)
VC2005 ?
А ты не пробовал отключить проверку доступа вектора?
Для этого есть спец макрос.
Но это все мелочи.
Опять же, при таком подходе к анализу, в погоне за мнимой (малозначительной) оптимизацией проигрываете в скорости разработки, допускаете множество трудно детектируемых ошибок, не сосредоточиваетесь на действительно важной более глобальной оптимизации.
Короче, повторю избитую истину: преждевременная оптимизация - зло.
А ты не пробовал отключить проверку доступа вектора?
Для этого есть спец макрос.
Но это все мелочи.
Опять же, при таком подходе к анализу, в погоне за мнимой (малозначительной) оптимизацией проигрываете в скорости разработки, допускаете множество трудно детектируемых ошибок, не сосредоточиваетесь на действительно важной более глобальной оптимизации.
Короче, повторю избитую истину: преждевременная оптимизация - зло.
Цитата: vAC
Совсем забыл... Во втором тесте заполнение делалось таким образом, что адреса обращений сильно разнились. Поэтому это тоже немаловажный фактор - порядок заполнения. В связи с этим поменял структуру циклов для этого теста и добавил еще один тест...назову это не реализацией, а подходом заполнения, на практике очень часто пользуюсь :)
500,500,500: Green - 1.359; Vov4ick - 0.516; Boost - 4.578; vAC - 0.234
10000,100,100: Green - 1.063; Vov4ick - 0.375; Boost - 3.672; vAC - 0.187
100,100,10000: Green - 1.063; Vov4ick - 0.359; Boost - 3.672; vAC - 0.187
Поэтому производительность может скакать очень :)
Код:
for (int i=0; i < size0; i++)
{
p_a = &A[i * size1 * size2];
for (int j=0; j < size1; j++)
{
p_b = p_a + j * size2;
for (int k=0; k < size2; k++)
{
p_b[k] = char(i*j*k);
}
}
}
{
p_a = &A[i * size1 * size2];
for (int j=0; j < size1; j++)
{
p_b = p_a + j * size2;
for (int k=0; k < size2; k++)
{
p_b[k] = char(i*j*k);
}
}
}
500,500,500: Green - 1.359; Vov4ick - 0.516; Boost - 4.578; vAC - 0.234
10000,100,100: Green - 1.063; Vov4ick - 0.375; Boost - 3.672; vAC - 0.187
100,100,10000: Green - 1.063; Vov4ick - 0.359; Boost - 3.672; vAC - 0.187
Поэтому производительность может скакать очень :)
Кстати, а для "тройного вектора" ты так же реализовал?
Код:
for (int i=0; i < size0; i++) {
vvi& vv = A;
for (int j=0; j < size1; j++) {
vi& v = vv[j];
for (int k=0; k < size2; k++)
v[k] = char(i*j*k);
}
}
vvi& vv = A;
for (int j=0; j < size1; j++) {
vi& v = vv[j];
for (int k=0; k < size2; k++)
v[k] = char(i*j*k);
}
}
Но опять же некрасиво это, захламляет код. Зачем?
Цитата: Green
VC2005 ?
А ты не пробовал отключить проверку доступа вектора?
Для этого есть спец макрос.
Но это все мелочи.
Опять же, при таком подходе к анализу, в погоне за мнимой (малозначительной) оптимизацией проигрываете в скорости разработки, не сосредотачиваетесь на действительно важной более глобальной оптимизации.
Короче, повторю избитую истину: преждевременная оптимизация - зло.
А ты не пробовал отключить проверку доступа вектора?
Для этого есть спец макрос.
Но это все мелочи.
Опять же, при таком подходе к анализу, в погоне за мнимой (малозначительной) оптимизацией проигрываете в скорости разработки, не сосредотачиваетесь на действительно важной более глобальной оптимизации.
Короче, повторю избитую истину: преждевременная оптимизация - зло.
Вы про это?
Код:
#if !defined (_HAS_ITERATOR_DEBUGGING)
#if defined (_DEBUG)
#define _HAS_ITERATOR_DEBUGGING 1 /* for range checks, etc. */
#else
#define _HAS_ITERATOR_DEBUGGING 0
#endif /* defined (_DEBUG) */
#else
.....
reference operator[](size_type _Pos)
{ // subscript mutable sequence
#if _HAS_ITERATOR_DEBUGGING
if (size() <= _Pos)
{
_DEBUG_ERROR("vector subscript out of range");
_SCL_SECURE_OUT_OF_RANGE;
}
#endif /* _HAS_ITERATOR_DEBUGGING */
_SCL_SECURE_VALIDATE_RANGE(_Pos < size());
return (*(_Myfirst + _Pos));
}
#if defined (_DEBUG)
#define _HAS_ITERATOR_DEBUGGING 1 /* for range checks, etc. */
#else
#define _HAS_ITERATOR_DEBUGGING 0
#endif /* defined (_DEBUG) */
#else
.....
reference operator[](size_type _Pos)
{ // subscript mutable sequence
#if _HAS_ITERATOR_DEBUGGING
if (size() <= _Pos)
{
_DEBUG_ERROR("vector subscript out of range");
_SCL_SECURE_OUT_OF_RANGE;
}
#endif /* _HAS_ITERATOR_DEBUGGING */
_SCL_SECURE_VALIDATE_RANGE(_Pos < size());
return (*(_Myfirst + _Pos));
}
Вообще-то все тестировалось в Release, все проверки отключаются и vector становиться обычным указателем - в этом и суть STL - обходиться без потери скорости.
Откуда вы узнали что это малозначительно? У вас есть ТЗ автора топика? :) А если вас попросят написать программу, которая только и будет заполнять массив и чем быстрее - тем больше вам денег дадут, будете писать как по-красивее? :)
Если уж надо сделать быстро, но в последствии сделать более эффективно, то есть такая замечательная весчь в ООП как инкапсуляция. Быстро разработайте простую реализацию, а потом при необходимости замените более быстрой, не затронув клиентский код. Этого наверно не понять ярым противникам ООП ;)
Цитата: Green
Кстати, а для "тройного вектора" ты так же реализовал?
...
Но опять же некрасиво это, захламляет код. Зачем?
...
преждевременная оптимизация - зло
...
Но опять же некрасиво это, захламляет код. Зачем?
...
преждевременная оптимизация - зло
Нет :)
А насчет захламляет или нет - я же не говорю, что все массивы надо так заполнять. Если найдется такое узкое место в программе, то думаю будет целесообразно немного захломить небольшой участок кода.
Я как-то работал в одном проекте по космической радиолокации - так там не до красоты было, поставили в жесткие рамки - "20 минут и снимок должен быть готов!". Конечно скорость выжималась не из массивов, а из алгоритмов.
Какая преждевременная оптимизация? В этом топике вроде разработка ПО вцелом не рассматривается, поэтому оптимизируем только массивы :) Может автор топика хочет сделать быструю библиотеку линейной алгебры? Для каждой задачи свои главные критерии - производительность, расход памяти, расширяемость, красота кода - все это определяется на этапе анализа, а уж потом, при разработке, принимаются решения о реализации, исходя из требований. Например для систем реального времени вообще может придется отказаться от динамической памяти. Представьте сбой в системе управления спутником или медицинским оборудованием...
З.Ы.
Поправка к методу Green:
500;500;500: 0.468;
10000;100;100: 0.407;
100;100;10000: 0.36.
Думаю кэш процессора сыграл свою роль...
Цитата: vAC
Вы про это?
Вообще-то все тестировалось в Release, все проверки отключаются и vector становиться обычным указателем - в этом и суть STL - обходиться без потери скорости.
Код:
#if !defined (_HAS_ITERATOR_DEBUGGING)
#if defined (_DEBUG)
#define _HAS_ITERATOR_DEBUGGING 1 /* for range checks, etc. */
#else
#define _HAS_ITERATOR_DEBUGGING 0
#endif /* defined (_DEBUG) */
#else
.....
reference operator[](size_type _Pos)
{ // subscript mutable sequence
#if _HAS_ITERATOR_DEBUGGING
if (size() <= _Pos)
{
_DEBUG_ERROR("vector subscript out of range");
_SCL_SECURE_OUT_OF_RANGE;
}
#endif /* _HAS_ITERATOR_DEBUGGING */
_SCL_SECURE_VALIDATE_RANGE(_Pos < size());
return (*(_Myfirst + _Pos));
}
#if defined (_DEBUG)
#define _HAS_ITERATOR_DEBUGGING 1 /* for range checks, etc. */
#else
#define _HAS_ITERATOR_DEBUGGING 0
#endif /* defined (_DEBUG) */
#else
.....
reference operator[](size_type _Pos)
{ // subscript mutable sequence
#if _HAS_ITERATOR_DEBUGGING
if (size() <= _Pos)
{
_DEBUG_ERROR("vector subscript out of range");
_SCL_SECURE_OUT_OF_RANGE;
}
#endif /* _HAS_ITERATOR_DEBUGGING */
_SCL_SECURE_VALIDATE_RANGE(_Pos < size());
return (*(_Myfirst + _Pos));
}
Вообще-то все тестировалось в Release, все проверки отключаются и vector становиться обычным указателем - в этом и суть STL - обходиться без потери скорости.
Нет, я про _SECURE_SCL.
А "суть STL" не в "обходиться без потери скорости".
Цитата: vAC
Откуда вы узнали что это малозначительно?
А от туда, что я умею отделять академические задачи от практических.
Кроме того обладаю методом дедукции и индукции... :)
Цитата: vAC
У вас есть ТЗ автора топика? :)
Да, есть. Цитировать не буду, см. топик.
Цитата: vAC
А если вас попросят написать программу, которая только и будет заполнять массив и чем быстрее - тем больше вам денег дадут, будете писать как по-красивее? :)
Да, сначала буду писать, как красивее. И далее буду придерживаться стройности кода.
Цитата: Green
Нет, я про _SECURE_SCL.
А "суть STL" не в "обходиться без потери скорости".
Да, сначала буду писать, как красивее.
А "суть STL" не в "обходиться без потери скорости".
Да, сначала буду писать, как красивее.
Так оно тоже отключается
Может и не суть, но один из главных моментов.
Думаю вы читали Майерса - он это довольно четко подчеркивает. И также любит покопаться в исходниках STL как и вы :)
Ну тогда я быстрее вас куплю виллу в Испании :)