Skip to content

Instantly share code, notes, and snippets.

@SimLeek
Created April 15, 2018 01:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save SimLeek/808266d917af8d22e54dbe829eb5f876 to your computer and use it in GitHub Desktop.
Save SimLeek/808266d917af8d22e54dbe829eb5f876 to your computer and use it in GitHub Desktop.
Sparse Tensor implementation
template<typename _Tp, std::size_t _Nm>
class ConstructableArray{
public:
ConstructableArray(std::initializer_list<_Tp> list)
{
std::copy(list.begin(), list.end(), pointer);
}
ConstructableArray(const ConstructableArray& other)
{
std::copy(other.pointer, other.pointer+_Nm, pointer);
}
_Tp operator[](size_t i){
return pointer[i];
}
private:
_Tp pointer[_Nm];
};
template<typename _Tp, std::size_t _Nm>
std::ostream &operator<<(std::ostream &os, ConstructableArray<_Tp, _Nm> &m) {
os<<"["<<m[0];
for (int i=1;i<_Nm;++i){
os<<","<<m[i];
}
return os << "]";
}
template<typename _Tp, std::size_t _Nm>
std::string to_string(ConstructableArray<_Tp, _Nm> m){
std::stringstream ss;
ss<<m;
return ss.str();
}
template<typename _Tpi,typename _Tpr, std::size_t _Ndim>
class SparseTensor{
public:
SparseTensor(){}
SparseTensor(const _Tpr& default_value):default_value(default_value){}
_Tpr& operator[](ConstructableArray<_Tpi,_Ndim> loc){
//note: this can and should be improved to not used lists if time permits
//note: some modification necessary for higher precision floats
auto it=sparse_map.find(loc);
if(it==sparse_map.end()){
sparse_map[loc]=default_value;
}
return sparse_map[loc];
}
std::vector<_Tpr> get_array(ConstructableArray<_Tpi,_Ndim> max_loc){
_Tpi num=1;
for(std::size_t i=0; i<_Ndim;++i){
num*=max_loc[i];
}
std::vector<_Tpr> dense_array;
dense_array.resize(num, default_value);
for(auto it: sparse_map){
_Tpi pos = 0;
_Tpi multiplier = 1;
for(std::size_t i=0; i<_Ndim;++i){
pos += multiplier*(it->first[i]);
multiplier*=max_loc[i];
}
dense_array[pos] = it->second;
}
return dense_array;
}
_Tpr& operator[](std::initializer_list<_Tpi> list){
ConstructableArray<std::size_t,_Ndim> loc(list);
return operator[](loc);
}
std::vector<_Tpr> get_array(std::initializer_list<_Tpi> list){
ConstructableArray<std::size_t,_Ndim> loc(list);
return get_array(loc);
}
_Tpr default_value;
private:
std::unordered_map<ConstructableArray<_Tpi,_Ndim>, _Tpr&> sparse_map;
};
@SimLeek
Copy link
Author

SimLeek commented Apr 15, 2018

test:

TEST_CASE("test sparse array"){
    uint resolutions[10] = {800,600,
                            400,300,
                            200,150,
                            100,75,
                            50,37};

    SparseTensor<uint,uint, 2> test_tensor(3);
    test_tensor[{35,24}]=2;
    auto vec = test_tensor.get_array({800,600});//todo: need get array multisize

    REQUIRE(vec[35+600*24]==2);

    REQUIRE(vec[34+600*24]==3);
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment