C ++ valarray против вектора
https://stackoverflow.com/questions/1602451
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я очень люблю векторы. Они изящны и быстры. Но я знаю, что существует то, что называется valarray. Зачем мне использовать valarray вместо вектора? Я знаю, что у valarrays есть некоторый синтаксический сахар, но кроме этого, когда они полезны?
Решение
Valarrays (массивы значений) предназначены для того, чтобы повысить скорость Fortran до C ++. Вы не сделаете множество указателей, чтобы компилятор мог делать предположения о коде и лучше его оптимизировать. (Основная причина того, что Fortran такой быстрый, заключается в том, что нет типа указателя, поэтому не может быть псевдонима указателя.)
В Valarrays также есть классы, которые позволяют достаточно легко их нарезать, хотя в этой части стандарта может потребоваться немного больше работы. Изменение их размера разрушительно, и им не хватает итераторов.
Итак, если вы работаете с числами, а удобство не так уж важно, используйте значения. В противном случае векторы намного удобнее.
Другие советы
valarray является своего рода сиротой, которая родилась в неправильном месте в неподходящее время. Это попытка оптимизации, особенно для машин, которые использовались для тяжелой математики, когда она была написана - в частности, для векторных процессоров, таких как Crays.
Для векторного процессора вы обычно хотели применить одну операцию ко всему массиву, затем применить следующую операцию ко всему массиву и так далее, пока вы не сделаете все, что вам нужно сделать.
Однако, если вы не имеете дело с довольно маленькими массивами, это плохо работает с кэшированием. На большинстве современных машин вы, как правило, предпочитаете (насколько это возможно) загружать часть массива, выполнять на нем все необходимые операции, а затем переходить к следующей части массива. Предполагается, что
valarray исключает любую возможность создания псевдонимов, что (по крайней мере, теоретически) позволяет компилятору повысить скорость, поскольку он более свободен для хранения значений в регистрах. В действительности, однако, я совсем не уверен, что любая реальная реализация в значительной степени использует это в своих интересах. Я подозреваю, что это скорее проблема типа "курица с яйцом" - без поддержки компилятора она не стала бы популярной, и пока она не популярна, никто не собирается работать над своим компилятором для ее поддержки.
Существует также изумительный (буквально) массив вспомогательных классов, которые можно использовать с valarray. Вы получаете slice , slice_array , gslice и gslice_array для игры с частями valarray и заставить его действовать как многомерный массив. Вы также получаете mask_array для " mask " операция (например, добавить элементы от x до y, но только в местах, где z не равен нулю). Чтобы сделать более чем тривиальное использование valarray , вам нужно много узнать об этих вспомогательных классах, некоторые из которых довольно сложны и ни один из которых не кажется (по крайней мере мне) очень хорошо задокументированным.
Итог: хотя в нем есть моменты блеска, и он может делать некоторые вещи довольно аккуратно, есть также несколько очень веских причин, по которым он (и почти наверняка останется) неясным.
Редактировать (восемь лет спустя, в 2017 году). Некоторые из предыдущих пунктов устарели, по крайней мере, до некоторой степени. Например, Intel внедрила оптимизированную версию valarray для своего компилятора. Он использует Intel Integrated Performance Primitives (Intel IPP) для повышения производительности. Хотя точное повышение производительности, несомненно, варьируется, быстрый тест с простым кодом показывает увеличение скорости примерно в 2: 1 по сравнению с идентичным кодом, скомпилированным с помощью «стандартного» кода. реализация valarray .
Итак, хотя я не совсем уверен, что программисты на C ++ начнут использовать valarray в огромных количествах, есть некоторые обстоятельства, при которых это может обеспечить повышение скорости.
Во время стандартизации C ++ 98, valarray был разработан, чтобы позволить некоторые виды быстрых математических вычислений. Однако примерно в то же время Тодд Вельдхуйзен изобрел шаблоны выражений и создал blitz ++ , и были изобретены похожие методы метаданных шаблонов. , что сделало valarrays в значительной степени устаревшими еще до выпуска стандарта. IIRC, первоначальный разработчик (и) valarray, оставил его на полпути к стандартизации, что (если верно) также не помогло.
ISTR, что главная причина, по которой он не был удален из стандарта, заключается в том, что никто не нашел время тщательно оценить проблему и написать предложение по ее устранению.
Имейте в виду, однако, что все это смутно запомнилось слухами. Примите это с недоверием и надейтесь, что кто-то исправит или подтвердит это.
Я знаю, что у valarrays есть некоторый синтаксический сахар
Я должен сказать, что не думаю, что у std :: valarrays есть много синтаксического сахара. Синтаксис другой, но я бы не назвал разницу "сахар". API странный. В разделе std :: valarray на языке программирования C ++ упоминается этот необычный API и тот факт, что, поскольку std :: valarray являются ожидается, что он будет оптимизирован, и любые сообщения об ошибках, которые вы получите во время их использования, вероятно, будут не интуитивно понятными.
Из любопытства около года назад я сравнил std :: valarray с std :: vector . У меня больше нет кода или точных результатов (хотя это не должно быть трудно написать свой собственный). Используя GCC, я сделал немного выиграл в производительности, когда использовал std :: valarray для простой математики, но не для своих реализаций для вычисления стандартного отклонения (и, конечно, стандартного отклонения). не так сложно, насколько математика идет). Я подозреваю, что операции с каждым элементом в большом (< strong> ПРИМЕЧАНИЕ . Следуя совету musiphil , мне удалось добиться почти одинаковой производительности от std :: vector лучше работают с кэшами, чем операции с std :: valarray s. vector и valarray ).
В конце я решил использовать std :: vector , уделяя пристальное внимание таким вещам, как выделение памяти и создание временных объектов.
И std :: vector , и std :: valarray хранят данные в непрерывном блоке. Однако они получают доступ к этим данным с использованием разных шаблонов, и, что более важно, API для std :: valarray поддерживает шаблоны доступа, отличные от API для std :: vector .
В примере со стандартным отклонением на конкретном этапе мне нужно было найти среднее значение для коллекции и разницу между значением каждого элемента и средним значением.
Для std :: valarray я сделал что-то вроде:
std::valarray<double> original_values = ... // obviously I put something here
double mean = original_values.sum() / original_values.size();
std::valarray<double> temp(mean, original_values.size());
std::valarray<double> differences_from_mean = original_values - temp;
Возможно, я был умнее с std :: slice или std :: gslice . Прошло уже более пяти лет.
Для std :: vector я сделал что-то вроде:
std::vector<double> original_values = ... // obviously, I put something here
double mean = std::accumulate(original_values.begin(), original_values.end(), 0.0) / original_values.size();
std::vector<double> differences_from_mean;
differences_from_mean.reserve(original_values.size());
std::transform(original_values.begin(), original_values.end(), std::back_inserter(differences_from_mean), std::bind1st(std::minus<double>(), mean));
Сегодня я бы, конечно, написал это по-другому. Если бы не что иное, я бы воспользовался лямбдами C ++ 11.
Очевидно, что эти два фрагмента кода делают разные вещи. Например, пример std :: vector не создает промежуточную коллекцию, как в примере std :: valarray . Тем не менее, я думаю, что было бы справедливо сравнивать их, поскольку различия связаны с различиями между std :: vector и std :: valarray .
Когда я писал этот ответ, я подозревал, что вычитание значения элементов из двух std :: valarray (последняя строка в примере std :: valarray ) будет быть менее дружественным к кешу, чем соответствующая строка в примере std :: vector (которая также является последней строкой).
Однако оказывается, что
std::valarray<double> original_values = ... // obviously I put something here
double mean = original_values.sum() / original_values.size();
std::valarray<double> differences_from_mean = original_values - mean;
Делает то же самое, что и пример std :: vector , и имеет почти идентичную производительность. В конце концов, вопрос в том, какой API вы предпочитаете.
valarray должен был позволить чему-то хорошему в векторной обработке FORTRAN на C ++. Каким-то образом необходимой поддержки компилятора никогда не было.
Книги Josuttis содержат несколько интересных (несколько уничижительных) комментариев о valarray ( здесь и здесь ).
Однако теперь Intel, похоже, пересматривает valarray в своих последних выпусках компилятора (например, см. слайд 9 ); это интересная разработка, учитывая, что их 4-сторонний набор инструкций SIMD SSE собирается соединиться с 8-позиционными AVX и 16-позиционными инструкциями Larrabee, и в интересах переносимости, вероятно, будет гораздо лучше кодировать с такой абстракцией, как valarray, чем (скажем) внутренности.
Я нашел одно хорошее применение для valarray. Это использовать valarray так же, как массивы numpy.
auto x = linspace(0, 2 * 3.14, 100);
plot(x, sin(x) + sin(3.f * x) / 3.f + sin(5.f * x) / 5.f);
Мы можем реализовать выше с Valarray.
valarray<float> linspace(float start, float stop, int size)
{
valarray<float> v(size);
for(int i=0; i<size; i++) v[i] = start + i * (stop-start)/size;
return v;
}
std::valarray<float> arange(float start, float step, float stop)
{
int size = (stop - start) / step;
valarray<float> v(size);
for(int i=0; i<size; i++) v[i] = start + step * i;
return v;
}
string psstm(string command)
{//return system call output as string
string s;
char tmp[1000];
FILE* f = popen(command.c_str(), "r");
while(fgets(tmp, sizeof(tmp), f)) s += tmp;
pclose(f);
return s;
}
string plot(const valarray<float>& x, const valarray<float>& y)
{
int sz = x.size();
assert(sz == y.size());
int bytes = sz * sizeof(float) * 2;
const char* name = "plot1";
int shm_fd = shm_open(name, O_CREAT | O_RDWR, 0666);
ftruncate(shm_fd, bytes);
float* ptr = (float*)mmap(0, bytes, PROT_WRITE, MAP_SHARED, shm_fd, 0);
for(int i=0; i<sz; i++) {
*ptr++ = x[i];
*ptr++ = y[i];
}
string command = "python plot.py ";
string s = psstm(command + to_string(sz));
shm_unlink(name);
return s;
}
Также нам нужен скрипт на Python.
import sys, posix_ipc, os, struct
import matplotlib.pyplot as plt
sz = int(sys.argv[1])
f = posix_ipc.SharedMemory("plot1")
x = [0] * sz
y = [0] * sz
for i in range(sz):
x[i], y[i] = struct.unpack('ff', os.read(f.fd, 8))
os.close(f.fd)
plt.plot(x, y)
plt.show()
Стандарт C ++ 11 гласит:
Классы массивов valarray определены как свободные от определенных форм создание псевдонимов, что позволяет оптимизировать операции над этими классами.
См. C ++ 11 26.6.1-2.
std :: valarray предназначен для тяжелых числовых задач, таких как «Динамика вычислительной жидкости» или «Динамика вычислительной структуры», в которых у вас есть массивы с миллионами, иногда десятками миллионов элементов, и вы выполняете их в цикле с миллионами временных шагов. Возможно, сегодня std :: vector имеет сопоставимую производительность, но около 15 лет назад valarray был почти обязателен, если вы хотели написать эффективный числовой решатель.
