From 6ff8072e8c5a6dc1301e884f5a648a0b63bdd48a Mon Sep 17 00:00:00 2001 From: Arnur Nigmetov Date: Tue, 3 Dec 2019 20:34:28 +0100 Subject: Rename directories for bottleneck and Wasserstein --- .../include/dnn/geometry/euclidean-dynamic.h | 270 +++++++++++++++++++++ wasserstein/include/dnn/geometry/euclidean-fixed.h | 196 +++++++++++++++ 2 files changed, 466 insertions(+) create mode 100644 wasserstein/include/dnn/geometry/euclidean-dynamic.h create mode 100644 wasserstein/include/dnn/geometry/euclidean-fixed.h (limited to 'wasserstein/include/dnn/geometry') diff --git a/wasserstein/include/dnn/geometry/euclidean-dynamic.h b/wasserstein/include/dnn/geometry/euclidean-dynamic.h new file mode 100644 index 0000000..b003906 --- /dev/null +++ b/wasserstein/include/dnn/geometry/euclidean-dynamic.h @@ -0,0 +1,270 @@ +#ifndef DNN_GEOMETRY_EUCLIDEAN_DYNAMIC_H +#define DNN_GEOMETRY_EUCLIDEAN_DYNAMIC_H + +#include +#include +#include +#include +#include +#include + +#include "hera_infinity.h" + +namespace hera +{ +namespace ws +{ +namespace dnn +{ + +template +class DynamicPointVector +{ + public: + using Real = Real_; + struct PointType + { + void* p; + + Real& operator[](const int i) + { + return (static_cast(p))[i]; + } + + const Real& operator[](const int i) const + { + return (static_cast(p))[i]; + } + + }; + struct iterator; + typedef iterator const_iterator; + + public: + DynamicPointVector(size_t point_capacity = 0): + point_capacity_(point_capacity) {} + + + PointType operator[](size_t i) const { return {(void*) &storage_[i*point_capacity_]}; } + inline void push_back(PointType p); + + inline iterator begin(); + inline iterator end(); + inline const_iterator begin() const; + inline const_iterator end() const; + + size_t size() const { return storage_.size() / point_capacity_; } + + void clear() { storage_.clear(); } + void swap(DynamicPointVector& other) { storage_.swap(other.storage_); std::swap(point_capacity_, other.point_capacity_); } + void reserve(size_t sz) { storage_.reserve(sz * point_capacity_); } + void resize(size_t sz) { storage_.resize(sz * point_capacity_); } + + private: + size_t point_capacity_; + std::vector storage_; + + private: + friend class boost::serialization::access; + + template + void serialize(Archive& ar, const unsigned int version) { ar & point_capacity_ & storage_; } +}; + +template +struct DynamicPointTraits +{ + typedef DynamicPointVector PointContainer; + typedef typename PointContainer::PointType PointType; + struct PointHandle + { + void* p; + bool operator==(const PointHandle& other) const { return p == other.p; } + bool operator!=(const PointHandle& other) const { return !(*this == other); } + bool operator<(const PointHandle& other) const { return p < other.p; } + bool operator>(const PointHandle& other) const { return p > other.p; } + }; + + typedef Real Coordinate; + typedef Real DistanceType; + + DynamicPointTraits(unsigned dim = 0): + dim_(dim) {} + + DistanceType distance(PointType p1, PointType p2) const + { + Real result = 0.0; + if (hera::is_infinity(internal_p)) { + // max norm + for (unsigned i = 0; i < dimension(); ++i) + result = std::max(result, fabs(coordinate(p1,i) - coordinate(p2,i))); + } else if (internal_p == Real(1.0)) { + // l1-norm + for (unsigned i = 0; i < dimension(); ++i) + result += fabs(coordinate(p1,i) - coordinate(p2,i)); + } else if (internal_p == Real(2.0)) { + result = sqrt(sq_distance(p1,p2)); + } else { + assert(internal_p > 1.0); + for (unsigned i = 0; i < dimension(); ++i) + result += std::pow(fabs(coordinate(p1,i) - coordinate(p2,i)), internal_p); + result = std::pow(result, Real(1.0) / internal_p); + } + return result; + } + DistanceType distance(PointHandle p1, PointHandle p2) const { return distance(PointType({p1.p}), PointType({p2.p})); } + DistanceType sq_distance(PointType p1, PointType p2) const { Real res = 0; for (unsigned i = 0; i < dimension(); ++i) { Real c1 = coordinate(p1,i), c2 = coordinate(p2,i); res += (c1 - c2)*(c1 - c2); } return res; } + DistanceType sq_distance(PointHandle p1, PointHandle p2) const { return sq_distance(PointType({p1.p}), PointType({p2.p})); } + unsigned dimension() const { return dim_; } + Real& coordinate(PointType p, unsigned i) const { return ((Real*) p.p)[i]; } + Real& coordinate(PointHandle h, unsigned i) const { return ((Real*) h.p)[i]; } + + // it's non-standard to return a reference, but we can rely on it for code that assumes this particular point type + size_t& id(PointType p) const { return *((size_t*) ((Real*) p.p + dimension())); } + size_t& id(PointHandle h) const { return *((size_t*) ((Real*) h.p + dimension())); } + PointHandle handle(PointType p) const { return {p.p}; } + PointType point(PointHandle h) const { return {h.p}; } + + void swap(PointType p1, PointType p2) const { std::swap_ranges((char*) p1.p, ((char*) p1.p) + capacity(), (char*) p2.p); } + bool cmp(PointType p1, PointType p2) const { return std::lexicographical_compare((Real*) p1.p, ((Real*) p1.p) + dimension(), (Real*) p2.p, ((Real*) p2.p) + dimension()); } + bool eq(PointType p1, PointType p2) const { return std::equal((Real*) p1.p, ((Real*) p1.p) + dimension(), (Real*) p2.p); } + + // non-standard, and possibly a weird name + size_t capacity() const { return sizeof(Real)*dimension() + sizeof(size_t); } + + PointContainer container(size_t n = 0) const { PointContainer c(capacity()); c.resize(n); return c; } + PointContainer container(size_t n, const PointType& p) const; + + typename PointContainer::iterator + iterator(PointContainer& c, PointHandle ph) const; + typename PointContainer::const_iterator + iterator(const PointContainer& c, PointHandle ph) const; + + Real internal_p; + + private: + unsigned dim_; + + private: + friend class boost::serialization::access; + + template + void serialize(Archive& ar, const unsigned int version) { ar & dim_; } +}; + +} // dnn + +template +struct dnn::DynamicPointVector::iterator: + public boost::iterator_facade +{ + typedef boost::iterator_facade Parent; + + + public: + typedef typename Parent::value_type value_type; + typedef typename Parent::difference_type difference_type; + typedef typename Parent::reference reference; + + iterator(size_t point_capacity = 0): + point_capacity_(point_capacity) {} + + iterator(void* p, size_t point_capacity): + p_(p), point_capacity_(point_capacity) {} + + private: + void increment() { p_ = ((char*) p_) + point_capacity_; } + void decrement() { p_ = ((char*) p_) - point_capacity_; } + void advance(difference_type n) { p_ = ((char*) p_) + n*point_capacity_; } + difference_type + distance_to(iterator other) const { return (((char*) other.p_) - ((char*) p_))/(int) point_capacity_; } + bool equal(const iterator& other) const { return p_ == other.p_; } + reference dereference() const { return {p_}; } + + friend class ::boost::iterator_core_access; + + private: + void* p_; + size_t point_capacity_; +}; + +template +void dnn::DynamicPointVector::push_back(PointType p) +{ + if (storage_.capacity() < storage_.size() + point_capacity_) + storage_.reserve(1.5*storage_.capacity()); + + storage_.resize(storage_.size() + point_capacity_); + + std::copy((char*) p.p, (char*) p.p + point_capacity_, storage_.end() - point_capacity_); +} + +template +typename dnn::DynamicPointVector::iterator dnn::DynamicPointVector::begin() { return iterator((void*) &*storage_.begin(), point_capacity_); } + +template +typename dnn::DynamicPointVector::iterator dnn::DynamicPointVector::end() { return iterator((void*) &*storage_.end(), point_capacity_); } + +template +typename dnn::DynamicPointVector::const_iterator dnn::DynamicPointVector::begin() const { return const_iterator((void*) &*storage_.begin(), point_capacity_); } + +template +typename dnn::DynamicPointVector::const_iterator dnn::DynamicPointVector::end() const { return const_iterator((void*) &*storage_.end(), point_capacity_); } + +template +typename dnn::DynamicPointTraits::PointContainer +dnn::DynamicPointTraits::container(size_t n, const PointType& p) const +{ + PointContainer c = container(n); + for (auto x : c) + std::copy((char*) p.p, (char*) p.p + capacity(), (char*) x.p); + return c; +} + +template +typename dnn::DynamicPointTraits::PointContainer::iterator +dnn::DynamicPointTraits::iterator(PointContainer& c, PointHandle ph) const +{ return typename PointContainer::iterator(ph.p, capacity()); } + +template +typename dnn::DynamicPointTraits::PointContainer::const_iterator +dnn::DynamicPointTraits::iterator(const PointContainer& c, PointHandle ph) const +{ return typename PointContainer::const_iterator(ph.p, capacity()); } + +} // ws +} // hera + +namespace std { + template<> + struct hash::PointHandle> + { + using PointHandle = typename hera::ws::dnn::DynamicPointTraits::PointHandle; + size_t operator()(const PointHandle& ph) const + { + return std::hash()(ph.p); + } + }; + + template<> + struct hash::PointHandle> + { + using PointHandle = typename hera::ws::dnn::DynamicPointTraits::PointHandle; + size_t operator()(const PointHandle& ph) const + { + return std::hash()(ph.p); + } + }; + + +} // std + + +#endif diff --git a/wasserstein/include/dnn/geometry/euclidean-fixed.h b/wasserstein/include/dnn/geometry/euclidean-fixed.h new file mode 100644 index 0000000..3e38baf --- /dev/null +++ b/wasserstein/include/dnn/geometry/euclidean-fixed.h @@ -0,0 +1,196 @@ +#ifndef HERA_WS_DNN_GEOMETRY_EUCLIDEAN_FIXED_H +#define HERA_WS_DNN_GEOMETRY_EUCLIDEAN_FIXED_H + +#include +#include +#include +#include +#include + +//#include +#include +#include +#include +#include + +#include "../parallel/tbb.h" // for dnn::vector<...> + +namespace hera +{ +namespace ws +{ +namespace dnn +{ + // TODO: wrap in another namespace (e.g., euclidean) + + template + struct Point: + boost::addable< Point, + boost::subtractable< Point, + boost::dividable2< Point, Real, + boost::multipliable2< Point, Real > > > >, + public boost::array + { + public: + typedef Real Coordinate; + typedef Real DistanceType; + + + public: + Point(size_t id = 0): id_(id) {} + template + Point(const Point& p, size_t id = 0): + id_(id) { *this = p; } + + static size_t dimension() { return D; } + + // Assign a point of different dimension + template + Point& operator=(const Point& p) { for (size_t i = 0; i < (D < DD ? D : DD); ++i) (*this)[i] = p[i]; if (DD < D) for (size_t i = DD; i < D; ++i) (*this)[i] = 0; return *this; } + + Point& operator+=(const Point& p) { for (size_t i = 0; i < D; ++i) (*this)[i] += p[i]; return *this; } + Point& operator-=(const Point& p) { for (size_t i = 0; i < D; ++i) (*this)[i] -= p[i]; return *this; } + Point& operator/=(Real r) { for (size_t i = 0; i < D; ++i) (*this)[i] /= r; return *this; } + Point& operator*=(Real r) { for (size_t i = 0; i < D; ++i) (*this)[i] *= r; return *this; } + + Real norm2() const { Real n = 0; for (size_t i = 0; i < D; ++i) n += (*this)[i] * (*this)[i]; return n; } + Real max_norm() const + { + Real res = std::fabs((*this)[0]); + for (size_t i = 1; i < D; ++i) + if (std::fabs((*this)[i]) > res) + res = std::fabs((*this)[i]); + return res; + } + + Real l1_norm() const + { + Real res = std::fabs((*this)[0]); + for (size_t i = 1; i < D; ++i) + res += std::fabs((*this)[i]); + return res; + } + + Real lp_norm(const Real p) const + { + assert( !std::isinf(p) ); + if ( p == 1.0 ) + return l1_norm(); + Real res = std::pow(std::fabs((*this)[0]), p); + for (size_t i = 1; i < D; ++i) + res += std::pow(std::fabs((*this)[i]), p); + return std::pow(res, 1.0 / p); + } + + // quick and dirty for now; make generic later + //DistanceType distance(const Point& other) const { return sqrt(sq_distance(other)); } + //DistanceType sq_distance(const Point& other) const { return (other - *this).norm2(); } + + DistanceType distance(const Point& other) const { return (other - *this).max_norm(); } + DistanceType p_distance(const Point& other, const double p) const { return (other - *this).lp_norm(p); } + + size_t id() const { return id_; } + size_t& id() { return id_; } + + private: + friend class boost::serialization::access; + + template + void serialize(Archive& ar, const unsigned int version) { ar & boost::serialization::base_object< boost::array >(*this) & id_; } + + private: + size_t id_; + }; + + template + std::ostream& + operator<<(std::ostream& out, const Point& p) + { out << p[0]; for (size_t i = 1; i < D; ++i) out << " " << p[i]; return out; } + + + template + struct PointTraits; // intentionally undefined; should be specialized for each type + + + template + struct PointTraits< Point > // specialization for dnn::Point + { + typedef Point PointType; + typedef const PointType* PointHandle; + typedef std::vector PointContainer; + + typedef typename PointType::Coordinate Coordinate; + typedef typename PointType::DistanceType DistanceType; + + + static DistanceType + distance(const PointType& p1, const PointType& p2) { if (hera::is_infinity(internal_p)) return p1.distance(p2); else return p1.p_distance(p2, internal_p); } + + static DistanceType + distance(PointHandle p1, PointHandle p2) { return distance(*p1,*p2); } + + static size_t dimension() { return D; } + static Real coordinate(const PointType& p, size_t i) { return p[i]; } + static Real& coordinate(PointType& p, size_t i) { return p[i]; } + static Real coordinate(PointHandle p, size_t i) { return coordinate(*p,i); } + + static size_t id(const PointType& p) { return p.id(); } + static size_t& id(PointType& p) { return p.id(); } + static size_t id(PointHandle p) { return id(*p); } + + static PointHandle + handle(const PointType& p) { return &p; } + static const PointType& + point(PointHandle ph) { return *ph; } + + void swap(PointType& p1, PointType& p2) const { return std::swap(p1, p2); } + + static PointContainer + container(size_t n = 0, const PointType& p = PointType()) { return PointContainer(n, p); } + static typename PointContainer::iterator + iterator(PointContainer& c, PointHandle ph) { return c.begin() + (ph - &c[0]); } + static typename PointContainer::const_iterator + iterator(const PointContainer& c, PointHandle ph) { return c.begin() + (ph - &c[0]); } + + // Internal_p determines which norm will be used in Wasserstein metric (not to + // be confused with wassersteinPower parameter: + // we raise \| p - q \|_{internal_p} to wassersteinPower. + static Real internal_p; + + private: + + friend class boost::serialization::access; + + template + void serialize(Archive& ar, const unsigned int version) {} + + }; + + template + Real PointTraits< Point >::internal_p = hera::get_infinity(); + + + template + void read_points(const std::string& filename, PointContainer& points) + { + typedef typename boost::range_value::type Point; + typedef typename PointTraits::Coordinate Coordinate; + + std::ifstream in(filename.c_str()); + std::string line; + while(std::getline(in, line)) + { + if (line[0] == '#') continue; // comment line in the file + std::stringstream linestream(line); + Coordinate x; + points.push_back(Point()); + size_t i = 0; + while (linestream >> x) + points.back()[i++] = x; + } + } +} // dnn +} // ws +} // hera + +#endif -- cgit v1.2.3