C ++ valarray против вектора

159

Я очень люблю векторы. Они изящны и быстры. Но я знаю, что существует то, что называется valarray. Зачем мне использовать valarray вместо вектора? Я знаю, что у valarrays есть некоторый синтаксический сахар, но кроме этого, когда они полезны?

rlbond
источник
2
Просто обдумывал это на днях тоже. Насколько я знаю, это действительно просто специализированный математический вектор.
GManNickG
Разве valarray не делает шаблоны выражений?
Mooing Duck
Физик Ульрих Мутце дает пример использования valarray здесь и здесь
спасательный баланс

Ответы:

70

Valarrays (массивы значений) предназначены для переноса части скорости Fortran в C ++. Вы не сделаете множество указателей, чтобы компилятор мог делать предположения о коде и лучше его оптимизировать. (Основная причина того, что Fortran такой быстрый, заключается в том, что нет типа указателя, поэтому не может быть псевдонима указателя.)

В Valarrays также есть классы, которые позволяют довольно легко их нарезать, хотя в этой части стандарта может потребоваться немного больше работы. Изменение их размера разрушительно, и им не хватает итераторов.

Итак, если вы работаете с числами, а удобство не так уж важно, используйте значения. В противном случае векторы намного удобнее.

Тим Аллман
источник
11
Они не предназначены для того, чтобы избегать указателей. C ++ 11 определяет begin () и end () в valarray, которые возвращают им итераторы
Мохаммед эль-Накиб,
3
@ user2023370: именно поэтому так много пользователей Fortran предпочитают Fortran 77. :)
Майкл
152

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

Джерри Гроб
источник
1
Это специально запрещено для хранения произвольных типов объектов внутри valarray?
user541686 9.12.12
6
@Mehrdad: Да, список [Numeric.Requirements] (довольно длинный) ограничен. Только для пары примеров все абстрактные классы и исключения запрещены. Это также требует эквивалентности между (например) конструкцией копии и последовательностью конструкции по умолчанию, за которой следует присваивание.
Джерри Коффин
@JerryCoffin это страшно. мы обещаем, что не будем его использовать.
Хани Гок
4
Я бы не решил, основываясь на страхе. Я бы решил, основываясь на том, нужно ли вам хранить элементы, которые используют функции, которые он запрещает.
Джерри Гроб
3
@annoying_squid: Если у вас есть более конкретная и (вы считаете) точная информация для добавления, пожалуйста, не стесняйтесь добавлять ответ, показывающий ее. В настоящее время ваш комментарий не добавляет полезной информации.
Джерри Гроб
39

Во время стандартизации C ++ 98, valarray был разработан, чтобы позволить какие-то быстрые математические вычисления. Тем не менее, примерно в то же время Тодд Вельдхуйзен изобрел шаблоны выражений и создал blitz ++ , и были изобретены похожие методы метаданных шаблонов, что сделало valarra-ы в значительной степени устаревшими еще до выпуска стандарта. IIRC, первоначальный разработчик (и) valarray, отказался от него на полпути к стандартизации, что (если верно) тоже не помогло.

ISTR считает, что основная причина, по которой он не был удален из стандарта, заключается в том, что никто не нашел время тщательно оценить проблему и написать предложение по ее устранению.

Имейте в виду, однако, что все это смутно помнят слухи. Возьмите это с зерном соли и надейтесь, что кто-то исправит или подтвердит это.

SBI
источник
Шаблоны выражений могут быть в равной степени зачислены в Vandevoorde, верно?
Никос Атанасиу
@ Никос: Не то, что я знаю. Хотя я могу ошибаться. Что вы имеете в пользу этого чтения?
СБИ
1
это упомянуто в книге «Шаблоны C ++ - Полное руководство», я думаю, что общепризнанно, что они оба изобрели их независимо .
Никос Атанасиу
27

Я знаю, у valarrays есть некоторый синтаксический сахар

Я должен сказать, что я не думаю std::valarrays, что есть много в смысле синтаксического сахара. Синтаксис другой, но я бы не назвал разницу "сахар". API странный. Раздел std::valarrays на языке программирования C ++ упоминает этот необычный API и тот факт, что, поскольку std::valarrayожидается, что s будет сильно оптимизирован, любые сообщения об ошибках, которые вы получаете при их использовании, вероятно, будут не интуитивно понятными.

Из любопытства около года назад я выступил std::valarrayпротив std::vector. У меня больше нет кода или точных результатов (хотя это не должно быть трудно написать свой собственный). С помощью GCC я сделал получить немного выигрыша в производительности при использовании std::valarrayдля простой математики, но не для моих реализаций для вычисления стандартного отклонения (и, конечно же , стандартное отклонение не так сложен, насколько это математика идет). Я подозреваю, что операции с каждым элементом в целом std::vectorлучше работают с кешами, чем с std::valarrays. ( ПРИМЕЧАНИЕ , следуя советам от musiphil , мне удалось получить почти одинаковую производительность от vectorи valarray).

В конце концов я решил использовать std::vector, уделяя пристальное внимание таким вещам, как выделение памяти и создание временных объектов.


Оба std::vectorи std::valarrayхранят данные в непрерывном блоке. Однако они получают доступ к этим данным с использованием разных шаблонов, и, что более важно, API for 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::valarrays (последняя строка в 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 вы предпочитаете.

Макс Либберт
источник
Я не могу придумать причину, почему a std::vectorбудет лучше играть с кешами, чем a std::valarray; они оба выделяют один непрерывный блок памяти для своих элементов.
Musiphil
1
@musiphil Мой ответ слишком длинный для комментария, поэтому я обновил ответ.
Макс Либберт
1
В valarrayприведенном выше примере вам не нужно было создавать temp valarrayобъект, но вы могли бы просто сделать std::valarray<double> differences_from_mean = original_values - mean;, и тогда поведение кэша должно быть таким же, как в vectorпримере. (Кстати, если meanна самом деле int, нет double, вам может понадобиться static_cast<double>(mean).)
musiphil
Спасибо за предложение убрать valarray. Мне нужно посмотреть, улучшает ли это производительность. Что касается meanтого, чтобы быть int: это было ошибкой. Первоначально я написал пример с использованием ints, а затем понял, meanчто тогда он будет очень далек от реального среднего из-за усечения. Но я пропустил несколько необходимых изменений в моем первом раунде правок.
Макс Либберт
@musiphil Ты прав; это изменение привело к тому, что пример кода стал почти идентичным.
Макс Либберт
23

Предполагалось, что valarray позволит немного улучшить качество векторной обработки FORTRAN на C ++. Каким-то образом необходимой поддержки компилятора никогда не было.

Книги Josuttis содержат некоторые интересные (несколько уничижительные) комментарии о valarray ( здесь и здесь ).

Однако теперь Intel, похоже, пересматривает valarray в своих последних выпусках компилятора (например, см. Слайд 9 ); это интересная разработка, учитывая, что их набор инструкций SIMD SSE с 4 путями собирается соединиться с инструкциями AVX с 8 путями и инструкциями Larrabee с 16 путями, и в интересах переносимости, вероятно, будет намного лучше кодировать с такой абстракцией, как valarray, чем (скажем) внутренности.

timday
источник
16

Я нашел одно хорошее использование для 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()
Zeta
источник
2
У меня были точно такие же мысли, как и у вас, когда я узнал о Валарре сегодня на работе. Я думаю, что теперь для задач математической обработки в c ++ я буду использовать valarray, так как код выглядит намного проще для понимания с математической точки зрения.
Захария Крауса
8

Стандарт C ++ 11 гласит:

Классы массивов valarray определены как свободные от определенных форм псевдонимов, что позволяет оптимизировать операции с этими классами.

См. C ++ 11 26.6.1-2.

Линси
источник
Поскольку я предполагаю, что Стандарт определяет, какие формы, можете ли вы их процитировать? Кроме того, они реализованы с использованием трюков кодирования, или они основаны на компиляторе исключений из правил наложения имен в других местах языка?
underscore_d
2

С ним std::valarrayвы можете использовать стандартные математические обозначения, как v1 = a*v2 + v3из коробки. Это невозможно с векторами, если вы не определите свои собственные операторы.

Пол Юрчак
источник
0

std :: valarray предназначен для сложных числовых задач, таких как «Динамика вычислительной жидкости» или «Динамика вычислительной структуры», в которых у вас есть массивы с миллионами, иногда десятками миллионов элементов, и вы выполняете их в цикле с миллионами шагов. Возможно, сегодня std :: vector имеет сопоставимую производительность, но около 15 лет назад valarray был почти обязателен, если вы хотели написать эффективный числовой решатель.

mrpivello
источник