snz ak ioi

浅谈valarray

2018-12-01 19:49:33


valarray是C++中很冷门的容器之一。尽管冷门,其实挺有意思的。

valarray是什么?

cppreference.com是这么介绍valarray的:

std::valarray 是表示并操作值数组的类。它支持逐元素数学运算与多种形式的广义下标运算符、切片及间接访问。

换句话说,valarray就是一种数组的替代品而已,和vector基本相同。但是valarray比vector慢很多,如果需要vector的(更快的)替代品,basic_string能够胜任。

既然这么慢,还要它干嘛呢?因为它对数值操作提供了一些简写和优化。

valarray的定义和基本操作

前面说了valarray和vector基本相同,定义也是类似的。

valarray<int> v; // 一个空的valarray
valarray<int> v(2,3); // 由3个2组成的valarray
valarray<int> v{2,3,4}; // 需要C++11,一个内容为2,3,4三个数的valarray

valarray的访问和数组一样,可以直接访问下标:v[i]表示(从0开始标号的)第i个元素。用v.size()获取v的大小。

如果使用C++11,可以和大部分其他的STL一样使用range-based for遍历:

for(int i:v)printf("%d\n",i);

valarray独有的操作

valarray支持像std::bitset一样的,把数组看成一个整体的操作。比如把一个valarray中的元素逐个地加到另一个valarray的对应位置上,可以直接写 u+=v这样的语句。 这在写高斯消元等等算法的时候会方便很多,让普通的高斯消元和异或方程组的消元一样简短。

举一个例子吧:

#include<bits/stdc++.h>
using namespace std;
valarray<double> a{2,3,4},b{1,2,3},c{3,2,1};
double s(double x){return 1/(1+exp(-x));} //相信大家都知道这个函数
int main(){
    c+=a;         //此时c为{5,5,5}
    c/=2.5+b;     //此时c为{1.429,1.111,0.909}
    b=cos(c)+log(a);   //此时b为{0.835,1.542,2.001}
    a=b.apply(s); //此时a为{0.697,0.824,0.881}
    return 0;
}

这里的2.5+b指把b中的每个元素加上2.5,cos(c)是c中的每个元素的cos值组成的valarray(表面上)。b.apply(s)指b中的每个元素的s函数值组成的valarray。

为什么不能直接写s(b)呢?因为cos、log之类的函数是C++自带的,已经对于valarray重载了,而自定义的s函数没有对于valarray重载,所以必须写b.apply(s)。(经管理员大大提醒,把s声明成模板函数就可以直接s(b)了)

valarray有min()max()sum()三个成员函数,用以计算一个数组的最小值、最大值与和。还有一个cshift()函数用于循环移位:比如如果a是{1,2,3},a.cshift(1)就是{2,3,1}。

更加高端的操作

如果说valarray只有这些功能的话,和手工写一个for循环有什么区别呢?

当然不是这样。valarray还支持slicegslicemask_array这些操作。(这里可能表述不够精准)

slice

slice(start,size,stride)表示一个从第start位开始的,相邻两位间隔为stride,长度为size的切片。有点类似于python的a[2:4]这样的概念。

比如a为{2,3,4,5,6},a[slice(1,2,2)]就是{3,5}。

slice最常见的应用就是表示一个子串,可以配合使用valarray和C++11的其它特性简化代码。也有更加精妙的应用,比如这个使用一维数组的矩阵类:

class Matrix{
    valarray<int> data;
    int dim;
 public:
    Matrix(int r,int c):data(r*c),dim(c){}
    int& operator()(int r,int c){return data[r*dim+c];}
    int trace()const{
        return data[slice(0,dim,dim+1)].sum();
    }
};

这个trace()函数计算的是主对角线的元素和,stride是dim+1的意思是每次往下跳一行再右移一格。你会发现使用slice,可以统一地表示矩阵的各行、各列、各对角线,并且把这些元素当成一维数组处理。

gslice

表示一些slice组成的集合。(对我来讲)没什么用。

mask_array

表示一个valarray中符合某个条件的元素的下标集合。比如把a数组中所有奇数值加上b数组中对应位置的值,一句话就够了:

a[a%2==1]+=b;

此处的a%2不是一个数,(表面上)是另一个valarray;a%2==1不是一个bool,是一个mask_array。

是不是感觉这C++已经写的不像C++了?

总结

valarray可以简化C++中各种批量数值操作的代码,但常数较大

这里的常数较大是相对不封装的写法,比你自己封装的肯定要快。为什么?因为valarray使用了一个叫做“表达式模板”的技巧。这也是前面我特别加上了几个“表面上”的原因,这个返回值实际是一个完整的表达式树,然后被隐式转换成了valarray。这样可以去掉所有的临时赋值。

这个常数较大也并不绝对,某些编译器针对valarray进行了并行计算之类的优化,可以在速度上碾压手写的代码。

如果想要更高级的数值算法支持,可以使用python的NumPy。

最后来张图展示一下C++17、valarray一个别的特性还有我的gedit主题:

UPD:使用注意事项

今天我用valarray尝试着写了一道高斯消元题,发现一个玄学问题。关键代码如下:

for(int j=0;j<=n;j++)if(!vis[j])
    v[j]-=v[f[i]]/v[f[i]][i]*v[j][i];

我的高斯消元是不swap的,所以开了一个vis数组。(表面上)毫无问题。调试了好久之后终于发现问题还是出在valarray上。

valarray的表现并不像表面上那样是先把等于号右侧算出来再赋值到左侧的。使用valarray的时候千万不要忘记它的结果类型是一棵表达式树,具体来说是这样的:

_Expr<_BinClos<std::__minus, _ValArray, _Expr, typename _BinClos<__multiplies, _Expr, _Constant, _BinClos<__divides, _ValArray, _Constant, double, double>, double>::value_type, std::_BinClos<std::__multiplies, _Expr, _Constant, std::_BinClos<std::__divides, _ValArray, _Constant, double, double>, double> >, typename __fun<__minus, typename _BinClos<__multiplies, _Expr, _Constant, _BinClos<__divides, _ValArray, _Constant, double, double>, double>::value_type>::result_type>

于是经过编译器的复杂化简之后,等效于如下的语句(就是普通的写法循环顺序写反了):

for(int j=0;j<=n;j++)if(!vis[j])
    for(int k=0;k<=n+1;k++)
        v[j][k]-=v[f[i]][k]/v[f[i]][i]*v[j][i];

这当然是错的,因为右侧的比例因子v[j][i]一边计算一边变化的。所以不能这么偷懒。把它预存下来就正确了:

#define vad valarray<double>
......

for(int j=0;j<=n;j++)if(!vis[j]){
    vad c=v[f[i]]/v[f[i]][i]*v[j][i];
    v[j]-=c;
}

所以能够吸取这样一个教训:valarray的语法糖和循环写法之间几乎没有区别,循环顺序的错valarray中一样会犯

这里顺便介绍一个小技巧,用来显示C++中的变量类型,利用了typeid运算符libstdc++的demangle:

#include<bits/stdc++.h>
#include<cxxabi.h>
using namespace std;

template<class T> void printType(const T&x){
    cout<<abi::__cxa_demangle(typeid(x).name(),0,0,NULL)<<endl;
}

然后调用printType函数就会输出变量的类型。

printType(qsort) 输出:void (void*, unsigned long, unsigned long, int (*)(void const*, void const*))

printType(valarray<int>{2,3,4}/10*5) 输出:std::_Expr<std::_BinClos<std::__multiplies, std::_Expr, std::_Constant, std::_BinClos<std::__divides, std::_ValArray, std::_Constant, int, int>, int>, int>