自分用にC++疎ベクトルクラスを書いてみた
最近、色々と学習器を作って遊んでいるときに気軽にコピペで使える疎ベクトル(sparse vector)クラスが欲しくなってきたので勉強を兼ねて書いてみた。必要最低限の機能は付いている(はず)。
サポートしている演算は加算(減算)とスカラー倍と内積の3つ。加えてノルムも取得できるようにしている。ベクトルが大きくなってくるとノルムの計算時間がバカにならないので加算、スカラー倍時に差分を計算するようにした。ベクトルはIDだけを与えるか、"ID\tkey:value,..."という文字列で初期化する。
あくまで自分用なので、さしあたり必要な機能だけ作っておいた。
#ifndef SPARSE_VECTOR_H #define SPARSE_VECTOR_H #include <iostream> #include <string> #include <vector> #include <map> #include <cstdlib> #include <cmath> class sparse_vector { public: std::map<int, double> v_; int cid_; double b_; double norm2_; sparse_vector(int cid) : cid_(cid), b_(1.0), norm2_(1.0) {} sparse_vector(const char *line); sparse_vector(const sparse_vector &sv); sparse_vector &operator=(const sparse_vector &sv); sparse_vector &operator+=(const sparse_vector &sv); sparse_vector &operator*=(double scalar); double dot(const sparse_vector &sv); double norm() { return std::sqrt(this->norm2_); } void print(std::ostream &os); }; sparse_vector::sparse_vector(const char *line) : b_(1.0), norm2_(1.0) { std::string t = ""; while (*line != '\t') { t += *line; line++; } this->cid_ = std::atoi(t.c_str()); t = ""; while (1) { while (*line != ':') { t += *line; line++; } int key = std::atoi(t.c_str()); t = ""; line++; while (*line != ',' && *line != '\0') { t += *line; line++; } double value = std::atof(t.c_str()); this->v_[key] = value; this->norm2_ += (value * value); if (*line == '\0') { break; } t = ""; line++; } return; } sparse_vector::sparse_vector(const sparse_vector &sv) { std::map<int, double>::const_iterator i = sv.v_.begin(); std::map<int, double>::const_iterator e = sv.v_.end(); this->v_.clear(); while (i != e) { this->v_[i->first] = i->second; i++; } this->cid_ = sv.cid_; this->b_ = sv.b_; this->norm2_ = sv.norm2_; return; } sparse_vector &sparse_vector::operator=(const sparse_vector &sv) { std::map<int, double>::const_iterator i = sv.v_.begin(); std::map<int, double>::const_iterator e = sv.v_.end(); this->v_.clear(); while (i != e) { this->v_[i->first] = i->second; i++; } this->cid_ = sv.cid_; this->b_ = sv.b_; this->norm2_ = sv.norm2_; return *this; } sparse_vector &sparse_vector::operator+=(const sparse_vector &sv) { std::map<int, double>::const_iterator i = sv.v_.begin(); std::map<int, double>::const_iterator e = sv.v_.end(); while (i != e) { double &v = this->v_[i->first]; this->norm2_ -= (v * v); v += i->second; this->norm2_ += (v * v); i++; } this->norm2_ -= (this->b_ * this->b_); this->b_ += sv.b_; this->norm2_ += (this->b_ * this->b_); return *this; } sparse_vector &sparse_vector::operator*=(double scalar) { std::map<int, double>::iterator i = this->v_.begin(); std::map<int, double>::iterator e = this->v_.end(); while (i != e) { i->second *= scalar; i++; } this->b_ *= scalar; this->norm2_ *= (scalar * scalar); return *this; } double sparse_vector::dot(const sparse_vector &sv) { double dp = (this->b_ * sv.b_); std::map<int, double>::const_iterator i1 = sv.v_.begin(); std::map<int, double>::const_iterator e1 = sv.v_.end(); std::map<int, double>::const_iterator e2 = this->v_.end(); while (i1 != e1) { std::map<int, double>::const_iterator i2 = this->v_.find(i1->first); if (i2 != e2) { dp += (i1->second * i2->second); } i1++; } return dp; } void sparse_vector::print(std::ostream &os) { os << "cid\t" << this->cid_ << std::endl; os << "norm^2\t" << this->norm2_ << std::endl; os << "b\t" << this->b_ << std::endl; std::map<int, double>::const_iterator i = this->v_.begin(); std::map<int, double>::const_iterator e = this->v_.end(); while (i != e) { os << i->first << "\t" << i->second << std::endl; i++; } return; } #endif
これを"sparse_vector.h"として保存。
以下、サンプルコード。
#include "sparse_vector.h" using namespace std; int main() { sparse_vector sv1("1\t1:3,2:5,3:1"); sparse_vector sv2("2\t1:1,4:3,5:5"); cout << "sv1:" << endl; sv1.print(cout); cout << endl; cout << "sv2:" << endl; sv2.print(cout); cout << endl; cout << "sv1 * sv2 = " << sv1.dot(sv2) << endl; cout << endl; sv1 += sv2; cout << "sv1 + sv2:" << endl; sv1.print(cout); cout << endl; sv1 *= (1/sv1.norm()); cout << "(sv1 + sv2)/|sv1 + sv2|:" << endl; sv1.print(cout); cout << endl; return 0; }
コンパイル、実行すると以下のようになる。
$$ g++ test.cc $$ ./a.out sv1: cid 1 norm^2 36 b 1 1 3 2 5 3 1 sv2: cid 2 norm^2 36 b 1 1 1 4 3 5 5 sv1 * sv2 = 4 sv1 + sv2: cid 1 norm^2 80 b 2 1 4 2 5 3 1 4 3 5 5 (sv1 + sv2)/|sv1 + sv2|: cid 1 norm^2 1 b 0.223607 1 0.447214 2 0.559017 3 0.111803 4 0.33541 5 0.559017