C++ valarray против вектора
Я очень люблю векторы. Они изящны и быстры. Но я знаю, что существует то, что называется valarray. Зачем мне использовать valarray вместо вектора? Я знаю, что у valarrays есть некоторый синтаксический сахар, но кроме этого, когда они полезны?
10 ответов
Valarrays (массивы значений) предназначены для переноса части скорости Fortran в C++. Вы не сделаете множество указателей, чтобы компилятор мог делать предположения о коде и лучше его оптимизировать. (Основная причина того, что Fortran такой быстрый, состоит в том, что нет типа указателя, поэтому не может быть псевдонима указателя.)
В Valarrays также есть классы, которые позволяют достаточно легко их нарезать, хотя в этой части стандарта может потребоваться немного больше работы. Изменение их размера разрушительно, и им не хватает итераторов.
Так что, если вы работаете с числами, а удобство не так уж важно, используйте значения. В противном случае векторы намного удобнее.
Валаррей - своего рода сирота, которая родилась не в то время и не в том месте. Это попытка оптимизации, особенно для машин, которые использовались для тяжелой математики, когда она была написана, в частности, для векторных процессоров, таких как Crays.
Для векторного процессора вы обычно хотели применить одну операцию ко всему массиву, затем применить следующую операцию ко всему массиву и так далее, пока вы не сделаете все, что вам нужно сделать.
Однако, если вы не имеете дело с достаточно маленькими массивами, это плохо работает с кэшированием. На большинстве современных машин вы, как правило, предпочитаете (насколько это возможно) загружать часть массива, выполнять на нем все необходимые операции, а затем переходить к следующей части массива.
Также предполагается, что valarray исключает любую возможность создания псевдонимов, что (по крайней мере, теоретически) позволяет компилятору повысить скорость, поскольку он более свободен для хранения значений в регистрах. В действительности, однако, я совсем не уверен, что любая реальная реализация в значительной степени использует это в своих интересах. Я подозреваю, что это скорее проблема типа "курица и яйцо" - без поддержки компилятора она не стала бы популярной, и пока она не популярна, никто не собирается работать над своим компилятором для ее поддержки.
Есть также изумительный (буквально) массив вспомогательных классов, которые можно использовать с valarray. Вы получаете slice, slice_array, gslice и gslice_array, чтобы играть с частями valarray, и заставить его действовать как многомерный массив. Вы также получаете mask_array, чтобы "маскировать" операцию (например, добавлять элементы от x до y, но только в тех местах, где z не равен нулю). Чтобы использовать более чем тривиальное использование valarray, вы должны много узнать об этих вспомогательных классах, некоторые из которых довольно сложны, и ни один из них не кажется (по крайней мере мне) хорошо документированным.
Итог: хотя в нем есть моменты блеска, и он может делать некоторые вещи довольно аккуратно, есть также несколько очень веских причин, по которым он (и почти наверняка останется) неясным.
Редактировать (восемь лет спустя, в 2017 году): Некоторые из предыдущих устарели, по крайней мере, до некоторой степени. Например, Intel внедрила оптимизированную версию valarray для своего компилятора. Он использует Intel Integrated Performance Primitives (Intel IPP) для повышения производительности. Хотя точное улучшение производительности, несомненно, варьируется, быстрый тест с простым кодом показывает увеличение скорости примерно в 2:1 по сравнению с идентичным кодом, скомпилированным со "стандартной" реализацией valarray,
Итак, хотя я не совсем уверен, что программисты на C++ начнут использовать valarray в огромных количествах есть, по крайней мере, некоторые обстоятельства, при которых это может обеспечить улучшение скорости.
Во время стандартизации C++98, valarray был разработан, чтобы позволить какие-то быстрые математические вычисления. Тем не менее, примерно в то же время Тодд Вельдхуйзен изобрел шаблоны выражений и создал blitz ++, и были изобретены аналогичные методы метаданных шаблонов, что сделало valarra-ы в значительной степени устаревшими еще до выпуска стандарта. IIRC, первоначальный разработчик (и) valarray, отказался от него на полпути к стандартизации, что (если верно) тоже не помогло.
ISTR считает, что основная причина, по которой он не был удален из стандарта, заключается в том, что никто не нашел время тщательно оценить проблему и написать предложение по ее устранению.
Имейте в виду, однако, что все это смутно помнят слухи. Возьмите это с зерном соли и надейтесь, что кто-то исправит или подтвердит это.
Я знаю, у valarrays есть синтаксический сахар
Я должен сказать, что я не думаю, std::valarrays есть много способов синтаксического сахара. Синтаксис другой, но я бы не назвал разницу "сахар". API странный. Раздел о std::valarray s в языке программирования C++ упоминает этот необычный API и тот факт, что, так как std::valarray Ожидается, что они будут высоко оптимизированы, и любые сообщения об ошибках, которые вы получаете при их использовании, вероятно, будут не интуитивно понятными.
Из любопытства около года назад я без косточек std::valarray против std::vector, У меня больше нет кода или точных результатов (хотя это не должно быть трудно написать свой собственный). Используя GCC я получил небольшое преимущество в производительности при использовании std::valarray для простой математики, но не для моих реализаций, чтобы вычислить стандартное отклонение (и, конечно, стандартное отклонение не так сложно, насколько математика идет). Я подозреваю, что операции над каждым элементом в большом std::vector лучше играть с кешем, чем с операциями на std::valarray s. (ПРИМЕЧАНИЕ, следуя совету от musiphil, мне удалось получить почти одинаковую производительность от 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 s (последняя строка в 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); это интересная разработка, учитывая, что их набор инструкций SIMD SSE с 4 путями собирается соединиться с инструкциями AVX с 8 путями и инструкциями Larrabee с 16 путями, и в интересах переносимости, вероятно, будет намного лучше кодировать с такой абстракцией, как 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 вы можете использовать стандартные математические обозначения, например v1 = a*v2 + v3из коробки. Это невозможно с векторами, если вы не определите свои собственные операторы.
По сутиstd::valarrayявляются векторами в более математическом смысле, которые допускают четко определенные математические операции, такие какc = a + b, а являются динамическими массивами. Названия просто вводят в заблуждение.
В векторе размерность фиксирована, и все его элементы ограничены переменными, которые допускают арифметические операции, и если вы создадите вектор с яблоками, компилятор немедленно сообщит, что яблоки не являются переменными, поддерживающими арифметические операции.
Кроме того, математические функции, такие какsqrt(),log(),sin()и т. д. принимают векторы в качестве входных данных и выполняют операцию с каждым элементом, что отлично подходит для архитектур с одной инструкцией и несколькими данными с очень большим количеством ядер. Например, графические процессоры очень хорошо работают с векторами.
Вот почему вектор может иметь гораздо более сложную структуру памяти. Его элементы могут быть распределены по нескольким узлам, при этом по сути представляет собой контейнер с указателем на непрерывную память.
И я до сих пор вижу людей, пытающихся использовать CUDA. Нет, извините, несмотря на вводящее в заблуждение название, вы не можете использоватьstd::vectorпотому что это не вектор. Я знаю, они признают, что это историческая ошибка, но даже не попытались ее исправить.
Std ::valarray предназначен для тяжелых числовых задач, таких как вычислительная гидродинамика или вычислительная динамика структуры, в которых у вас есть массивы с миллионами, иногда десятками миллионов элементов, и вы перебираете их в цикле с миллионами временных шагов. Возможно, сегодня std::vector имеет сопоставимую производительность, но около 15 лет назад valarray был почти обязательным, если вы хотели написать эффективный числовой решатель.