From 7592b908b684b84bc20ec0cfa2d5d97e16aead7b Mon Sep 17 00:00:00 2001 From: graehl Date: Wed, 11 Aug 2010 02:48:00 +0000 Subject: merge git-svn-id: https://ws10smt.googlecode.com/svn/trunk@512 ec762483-ff6d-05da-a07a-a48fb63a330f --- decoder/hash.h | 54 ----- decoder/small_vector.h | 265 ------------------------- decoder/sparse_vector.h | 512 ------------------------------------------------ 3 files changed, 831 deletions(-) delete mode 100755 decoder/hash.h delete mode 100644 decoder/small_vector.h delete mode 100644 decoder/sparse_vector.h diff --git a/decoder/hash.h b/decoder/hash.h deleted file mode 100755 index 3a60a429..00000000 --- a/decoder/hash.h +++ /dev/null @@ -1,54 +0,0 @@ -#ifndef CDEC_HASH_H -#define CDEC_HASH_H - -#include "murmur_hash.h" - -#include "config.h" -#ifdef HAVE_SPARSEHASH -# include -# define HASH_MAP google::dense_hash_map -# define HASH_MAP_RESERVED(h,empty,deleted) do { h.set_empty_key(empty); h.set_deleted_key(deleted); } while(0) -# define HASH_MAP_EMPTY(h,empty) do { h.set_empty_key(empty); } while(0) -#else -# include -# define HASH_MAP std::tr1::unordered_map -# define HASH_MAP_RESERVED(h,empty,deleted) -# define HASH_MAP_EMPTY(h,empty) -#endif - -#include - -// assumes C is POD -template -struct murmur_hash -{ - typedef MurmurInt return_type; - typedef C /*const&*/ argument_type; - return_type operator()(argument_type const& c) const { - return MurmurHash((void*)&c,sizeof(c)); - } -}; - -// murmur_hash_array isn't std guaranteed safe (you need to use string::data()) -template <> -struct murmur_hash -{ - typedef MurmurInt return_type; - typedef std::string /*const&*/ argument_type; - return_type operator()(argument_type const& c) const { - return MurmurHash(c.data(),c.size()); - } -}; - -// uses begin(),size() assuming contiguous layout and POD -template -struct murmur_hash_array -{ - typedef MurmurInt return_type; - typedef C /*const&*/ argument_type; - return_type operator()(argument_type const& c) const { - return MurmurHash(&*c.begin(),c.size()*sizeof(*c.begin())); - } -}; - -#endif diff --git a/decoder/small_vector.h b/decoder/small_vector.h deleted file mode 100644 index 25c52359..00000000 --- a/decoder/small_vector.h +++ /dev/null @@ -1,265 +0,0 @@ -#ifndef _SMALL_VECTOR_H_ -#define _SMALL_VECTOR_H_ - -/* REQUIRES that T is POD (can be memcpy). won't work (yet) due to union with SMALL_VECTOR_POD==0 - may be possible to handle movable types that have ctor/dtor, by using explicit allocation, ctor/dtor calls. but for now JUST USE THIS FOR no-meaningful ctor/dtor POD types. - - stores small element (<=SV_MAX items) vectors inline. recommend SV_MAX=sizeof(T)/sizeof(T*)>1?sizeof(T)/sizeof(T*):1. may not work if SV_MAX==0. - */ - -#define SMALL_VECTOR_POD 1 - -#include // std::max - where to get this? -#include -#include -#include -#include -#include -//sizeof(T)/sizeof(T*)>1?sizeof(T)/sizeof(T*):1 - -template -class SmallVector { -// typedef unsigned short uint16_t; - public: - typedef SmallVector Self; - SmallVector() : size_(0) {} - - typedef T const* const_iterator; - typedef T* iterator; - typedef T value_type; - typedef T &reference; - typedef T const& const_reference; - - T *begin() { return size_>SV_MAX?data_.ptr:data_.vals; } - T const* begin() const { return const_cast(this)->begin(); } - T *end() { return begin()+size_; } - T const* end() const { return begin()+size_; } - - explicit SmallVector(size_t s) : size_(s) { - assert(s < 0xA000); - if (s <= SV_MAX) { - for (int i = 0; i < s; ++i) new(&data_.vals[i]) T(); - } else { - capacity_ = s; - size_ = s; - data_.ptr = new T[s]; // TODO: replace this with allocator or ::operator new(sizeof(T)*s) everywhere - for (int i = 0; i < size_; ++i) new(&data_.ptr[i]) T(); - } - } - - SmallVector(size_t s, T const& v) : size_(s) { - assert(s < 0xA000); - if (s <= SV_MAX) { - for (int i = 0; i < s; ++i) data_.vals[i] = v; - } else { - capacity_ = s; - size_ = s; - data_.ptr = new T[s]; - for (int i = 0; i < size_; ++i) data_.ptr[i] = v; - } - } - - SmallVector(const Self& o) : size_(o.size_) { - if (size_ <= SV_MAX) { - std::memcpy(data_.vals,o.data_.vals,size_*sizeof(T)); -// for (int i = 0; i < size_; ++i) data_.vals[i] = o.data_.vals[i]; - } else { - capacity_ = size_ = o.size_; - data_.ptr = new T[capacity_]; - std::memcpy(data_.ptr, o.data_.ptr, size_ * sizeof(T)); - } - } - - const Self& operator=(const Self& o) { - if (size_ <= SV_MAX) { - if (o.size_ <= SV_MAX) { - size_ = o.size_; - for (int i = 0; i < SV_MAX; ++i) data_.vals[i] = o.data_.vals[i]; - } else { - capacity_ = size_ = o.size_; - data_.ptr = new T[capacity_]; - std::memcpy(data_.ptr, o.data_.ptr, size_ * sizeof(T)); - } - } else { - if (o.size_ <= SV_MAX) { - delete[] data_.ptr; - size_ = o.size_; - for (int i = 0; i < size_; ++i) data_.vals[i] = o.data_.vals[i]; - } else { - if (capacity_ < o.size_) { - delete[] data_.ptr; - capacity_ = o.size_; - data_.ptr = new T[capacity_]; - } - size_ = o.size_; - for (int i = 0; i < size_; ++i) - data_.ptr[i] = o.data_.ptr[i]; - } - } - return *this; - } - - ~SmallVector() { - if (size_ <= SV_MAX) { - // skip if pod? yes, we required pod anyway. no need to destruct -#if !SMALL_VECTOR_POD - for (int i=0;i SV_MAX) { - delete[] data_.ptr; - } - size_ = 0; - } - - bool empty() const { return size_ == 0; } - size_t size() const { return size_; } - - inline void ensure_capacity(uint16_t min_size) { - assert(min_size > SV_MAX); - if (min_size < capacity_) return; - uint16_t new_cap = std::max(static_cast(capacity_ << 1), min_size); - T* tmp = new T[new_cap]; - std::memcpy(tmp, data_.ptr, capacity_ * sizeof(T)); - delete[] data_.ptr; - data_.ptr = tmp; - capacity_ = new_cap; - } - -private: - inline void copy_vals_to_ptr() { - capacity_ = SV_MAX * 2; - T* tmp = new T[capacity_]; - for (int i = 0; i < SV_MAX; ++i) tmp[i] = data_.vals[i]; - data_.ptr = tmp; - } - inline void ptr_to_small() { - assert(size_<=SV_MAX); - int *tmp=data_.ptr; - for (int i=0;ioperator[](size_ - 1); } - const T& back() const { return this->operator[](size_ - 1); } - T& front() { return this->operator[](0); } - const T& front() const { return this->operator[](0); } - - void pop_back() { - assert(size_>0); - --size_; - if (size_==SV_MAX) - ptr_to_small(); - } - - void compact() { - compact(size_); - } - - // size must be <= size_ - TODO: test - void compact(uint16_t size) { - assert(size<=size_); - if (size_>SV_MAX) { - size_=size; - if (size<=SV_MAX) - ptr_to_small(); - } else - size_=size; - } - - void resize(size_t s, int v = 0) { - if (s <= SV_MAX) { - if (size_ > SV_MAX) { - T *tmp=data_.ptr; - for (int i = 0; i < s; ++i) data_.vals[i] = tmp[i]; - delete[] tmp; - size_ = s; - return; - } - if (s <= size_) { - size_ = s; - return; - } else { - for (int i = size_; i < s; ++i) - data_.vals[i] = v; - size_ = s; - return; - } - } else { - if (size_ <= SV_MAX) - copy_vals_to_ptr(); - if (s > capacity_) - ensure_capacity(s); - if (s > size_) { - for (int i = size_; i < s; ++i) - data_.ptr[i] = v; - } - size_ = s; - } - } - - T& operator[](size_t i) { - if (size_ <= SV_MAX) return data_.vals[i]; - return data_.ptr[i]; - } - - const T& operator[](size_t i) const { - if (size_ <= SV_MAX) return data_.vals[i]; - return data_.ptr[i]; - } - - bool operator==(const Self& o) const { - if (size_ != o.size_) return false; - if (size_ <= SV_MAX) { - for (size_t i = 0; i < size_; ++i) - if (data_.vals[i] != o.data_.vals[i]) return false; - return true; - } else { - for (size_t i = 0; i < size_; ++i) - if (data_.ptr[i] != o.data_.ptr[i]) return false; - return true; - } - } - - friend bool operator!=(const Self& a, const Self& b) { - return !(a==b); - } - - private: - union StorageType { - T vals[SV_MAX]; - T* ptr; - }; - StorageType data_; - uint16_t size_; - uint16_t capacity_; // only defined when size_ > __SV_MAX_STATIC -}; - -typedef SmallVector SmallVectorInt; - -template -void memcpy(void *out,SmallVector const& v) { - std::memcpy(out,v.begin(),v.size()*sizeof(T)); -} - -#endif diff --git a/decoder/sparse_vector.h b/decoder/sparse_vector.h deleted file mode 100644 index 207489c5..00000000 --- a/decoder/sparse_vector.h +++ /dev/null @@ -1,512 +0,0 @@ -#ifndef _SPARSE_VECTOR_H_ -#define _SPARSE_VECTOR_H_ - -//#define SPARSE_VECTOR_HASH - -#ifdef SPARSE_VECTOR_HASH -#include "hash.h" -# define SPARSE_VECTOR_MAP HASH_MAP -# define SPARSE_VECTOR_MAP_RESERVED(h,empty,deleted) HASH_MAP_RESERVED(h,empty,deleted) -#else -# define SPARSE_VECTOR_MAP std::map -# define SPARSE_VECTOR_MAP_RESERVED(h,empty,deleted) -#endif -/* - use SparseVectorList (pair smallvector) for feat funcs / hypergraphs (you rarely need random access; just append a feature to the list) -*/ -/* hack: index 0 never gets printed because cdyer is creative and efficient. features which have no weight got feature dict id 0, see, and the models all clobered that value. nobody wants to see it. except that vlad is also creative and efficient and stored the oracle bleu there. */ -/* NOTE: zero vals may or may not be dropped from map (sparse, but not guaranteed to be so). - - I rely on !v the same as !((bool)v) the same as v==0 and v() same as v(0). - - one exception: - - a local: - T sum = 0; - is used instead of - T sum; - - because T may be a primitive type, and - - T sum(); - - is parsed as a function decl :( - - the alternative T sum=T() is also be reasonable. i've switched to that. -*/ - -// this is a modified version of code originally written -// by Phil Blunsom - -#include -#include -#include -#include -#include - -#include "fdict.h" -#include "small_vector.h" - -template -inline T & extend_vector(std::vector &v,int i) { - if (i>=v.size()) - v.resize(i+1); - return v[i]; -} - -template -class SparseVector { - void init_reserved() { - SPARSE_VECTOR_MAP_RESERVED(values_,-1,-2); - } -public: - T const& get_singleton() const { - assert(values_.size()==1); - return values_.begin()->second; - } - - typedef SparseVector Self; - typedef SPARSE_VECTOR_MAP MapType; - typedef typename MapType::const_iterator const_iterator; - SparseVector() { - init_reserved(); - } - explicit SparseVector(std::vector const& v) { - init_reserved(); - typename MapType::iterator p=values_.begin(); - const T z=0; - for (unsigned i=0;i *vp) const { - init_vector(*vp); - } - - void init_vector(std::vector &v) const { - v.clear(); - for (const_iterator i=values_.begin(),e=values_.end();i!=e;++i) - extend_vector(v,i->first)=i->second; - } - - void set_new_value(int index, T const& val) { - assert(values_.find(index)==values_.end()); - values_[index]=val; - } - - - // warning: exploits the fact that 0 values are always removed from map. change this if you change that. - bool nonzero(int index) const { - typename MapType::const_iterator found = values_.find(index); - return found==values_.end() || !found->second; - } - - - T get(int index) const { - typename MapType::const_iterator found = values_.find(index); - return found==values_.end()?T():found->second; - } - - T value(int i) const { return get(i); } - - // same as above but may add a 0 entry. TODO: check that people relying on no entry use get - T & operator[](int index){ - return values_[index]; - } - - inline void set_value(int index, const T &value) { - values_[index] = value; - } - - inline void maybe_add(int index, const T& value) { - if (value) add_value(index,value); - } - - T& add_value(int index, const T &value) { -#if 1 - return values_[index]+=value; -#else - // this is not really going to be any faster, and we already rely on default init = 0 init - std::pair art=values_.insert(std::make_pair(index,value)); - T &val=art.first->second; - if (!art.second) val += value; // already existed - return val; -#endif - } - - - void store(std::valarray* target) const { - (*target) *= 0; - for (typename MapType::const_iterator - it = values_.begin(); it != values_.end(); ++it) { - if (it->first >= target->size()) break; - (*target)[it->first] = it->second; - } - } - - int max_index() const { - if (empty()) return 0; - typename MapType::const_iterator found =values_.end(); - --found; - return found->first; - } - - // dot product with a unit vector of the same length - // as the sparse vector - T dot() const { - T sum = T(); - for (typename MapType::const_iterator - it = values_.begin(); it != values_.end(); ++it) - sum += it->second; - return sum; - } - - template - S cosine_sim(const SparseVector &vec) const { - return dot(vec)/(l2norm()*vec.l2norm()); - } - - // if values are binary, gives |A intersect B|/|A union B| - template - S tanimoto_coef(const SparseVector &vec) const { - S dp=dot(vec); - return dp/(l2norm_sq()+vec.l2norm_sq()-dp); - } - - template - S dot(const SparseVector &vec) const { - S sum = S(); - for (typename MapType::const_iterator - it = values_.begin(); it != values_.end(); ++it) - { - typename MapType::const_iterator - found = vec.values_.find(it->first); - if (found != vec.values_.end()) - sum += it->second * found->second; - } - return sum; - } - - template - S dot(const std::vector &vec) const { - S sum = S(); - for (typename MapType::const_iterator - it = values_.begin(); it != values_.end(); ++it) - { - if (it->first < static_cast(vec.size())) - sum += it->second * vec[it->first]; - } - return sum; - } - - template - S dot(const S *vec) const { - // this is not range checked! - S sum = S(); - for (typename MapType::const_iterator - it = values_.begin(); it != values_.end(); ++it) - sum += it->second * vec[it->first]; - std::cout << "dot(*vec) " << sum << std::endl; - return sum; - } - - T l1norm() const { - T sum = T(); - for (typename MapType::const_iterator - it = values_.begin(); it != values_.end(); ++it) - sum += fabs(it->second); - return sum; - } - - T l2norm_sq() const { - T sum = T(); - for (typename MapType::const_iterator - it = values_.begin(); it != values_.end(); ++it) - sum += it->second * it->second; - return sum; - } - - T l2norm() const { - return sqrt(l2norm_sq()); - } - - void erase(int key) { - values_.erase(key); -/* typename MapType::iterator found = values_.find(key); - if (found!=values_end()) - values_.erase(found);*/ - } - - template - void set_from(SparseVector const& other) { - for (typename MapType::const_iterator - it = other.values_.begin(); it != other.values_.end(); ++it) - { - values_[it->first]=it->second; - } - } - - SparseVector &operator+=(const SparseVector &other) { - for (typename MapType::const_iterator - it = other.values_.begin(); it != other.values_.end(); ++it) - { -// T v = - (values_[it->first] += it->second); -// if (!v) values_.erase(it->first); - } - return *this; - } - - SparseVector &operator-=(const SparseVector &other) { - for (typename MapType::const_iterator - it = other.values_.begin(); it != other.values_.end(); ++it) - { -// T v = - (values_[it->first] -= it->second); -// if (!v) values_.erase(it->first); - } - return *this; - } - - friend SparseVector operator -(SparseVector x,SparseVector const& y) { - x-=y; - return x; - } - friend SparseVector operator +(SparseVector x,SparseVector const& y) { - x+=y; - return x; - } - -private: - // DEPRECATED: becuase 0 values are dropped from the map, this doesn't even make sense if you have a fully populated (not really sparse re: what you'll ever use) vector - SparseVector &operator-=(T const& x) { - for (typename MapType::iterator - it = values_.begin(); it != values_.end(); ++it) - it->second -= x; - return *this; - } - - SparseVector &operator+=(T const& x) { - for (typename MapType::iterator - it = values_.begin(); it != values_.end(); ++it) - it->second += x; - return *this; - } -public: - SparseVector &operator/=(const T &x) { - for (typename MapType::iterator - it = values_.begin(); it != values_.end(); ++it) - it->second /= x; - return *this; - } - - SparseVector &operator*=(const T& x) { - for (typename MapType::iterator - it = values_.begin(); it != values_.end(); ++it) - it->second *= x; - return *this; - } - - SparseVector operator+(T const& x) const { - SparseVector result = *this; - return result += x; - } - - SparseVector operator-(T const& x) const { - SparseVector result = *this; - return result -= x; - } - - SparseVector operator/(T const& x) const { - SparseVector result = *this; - return result /= x; - } - - std::ostream &operator<<(std::ostream& out) const { - Write(true, &out); - return out; - } - - void Write(const bool with_semi, std::ostream* os) const { - bool first = true; - for (typename MapType::const_iterator - it = values_.begin(); it != values_.end(); ++it) { - // by definition feature id 0 is a dummy value - if (!it->first) continue; - if (with_semi) { - (*os) << (first ? "" : ";") - << FD::Convert(it->first) << '=' << it->second; - } else { - (*os) << (first ? "" : " ") - << FD::Convert(it->first) << '=' << it->second; - } - first = false; - } - } - - bool operator==(Self const & other) const { - return size()==other.size() && contains_keys_of(other) && other.contains_i(*this); - } - - bool contains(Self const &o) const { - return size()>o.size() && contains(o); - } - - bool at_equals(int i,T const& val) const { - const_iterator it=values_.find(i); - if (it==values_.end()) return !val; - return it->second==val; - } - - bool contains_i(Self const& o) const { - for (typename MapType::const_iterator i=o.begin(),e=o.end();i!=e;++i) - if (!at_equals(i->first,i->second)) - return false; - return true; - } - - bool contains_keys_of(Self const& o) const { - for (typename MapType::const_iterator i=o.begin(),e=o.end();i!=e;++i) - if (values_.find(i)==values_.end()) - return false; - return true; - } - -#ifndef SPARSE_VECTOR_HASH - bool operator<(const SparseVector &other) const { - typename MapType::const_iterator it = values_.begin(); - typename MapType::const_iterator other_it = other.values_.begin(); - - for (; it != values_.end() && other_it != other.values_.end(); ++it, ++other_it) - { - if (it->first < other_it->first) return true; - if (it->first > other_it->first) return false; - if (it->second < other_it->second) return true; - if (it->second > other_it->second) return false; - } - return values_.size() < other.values_.size(); - } -#endif - - int size() const { return values_.size(); } - - int num_active() const { return values_.size(); } - bool empty() const { return values_.empty(); } - - const_iterator begin() const { return values_.begin(); } - const_iterator end() const { return values_.end(); } - - void clear() { - values_.clear(); - } - - void swap(SparseVector& other) { - values_.swap(other.values_); - } - -private: - MapType values_; -}; - -//like a pair but can live in a union, because it lacks default+copy ctors, dtor. -template -struct feature_val { - int fid; - T val; -}; - -template -inline feature_val featval(int fid,T const &val) { - feature_val f; - f.fid=fid; - f.val=val; - return f; -} - - -// doesn't support fast indexing directly -template -class SparseVectorList { - typedef feature_val Pair; - typedef SmallVector List; - typedef typename List::const_iterator const_iterator; - SparseVectorList() { } - template - SparseVectorList(I i,I const& end) { - int c=0; - for (;i const& v) { - for (unsigned i=0;i *to) const { - for (int i=0;iset_value(p[i].fid,p[i].val); - } - void copy_to(SparseVector *to) const { - to->clear(); - overlay(to); - } - SparseVector sparse() const { - SparseVector r; - copy_to(r); - return r; - } -private: - List p; -}; - -template -SparseVector operator+(const SparseVector& a, const SparseVector& b) { - SparseVector result = a; - return result += b; -} - -template -SparseVector operator*(const SparseVector& a, const double& b) { - SparseVector result = a; - return result *= b; -} - -template -SparseVector operator*(const SparseVector& a, const T& b) { - SparseVector result = a; - return result *= b; -} - -template -SparseVector operator*(const double& a, const SparseVector& b) { - SparseVector result = b; - return result *= a; -} - -template -std::ostream &operator<<(std::ostream &out, const SparseVector &vec) -{ - return vec.operator<<(out); -} - -namespace B64 { - void Encode(double objective, const SparseVector& v, std::ostream* out); - // returns false if failed to decode - bool Decode(double* objective, SparseVector* v, const char* data, size_t size); -} - -#endif -- cgit v1.2.3