can not compile nearest neighbors in d dimensions
I can not create a point in d(in the code M is dimensions) dimensions. The error is this: error: the value of ‘M’ is not usable in a constant expression note: ‘int M’ is not const error: template argument 2 is invalid and the line is this: int M; .. typedef bg::model::point<float, M, bg::cs::cartesian> point; Then, I am trying to create an Rtree (I have already the data in a 2D array), like this: // create the rtree using default constructor bgi::rtree< point, bgi::quadratic<16> > rtree; point tmp; for ( unsigned i = 0 ; i < N ; ++i ) { // insert new value for(int j = 0 ; j < M ; ++j) { bg::set<M>(tmp, a[i][j]); } rtree.insert(tmp); } and I think the error is in insert(). I am attaching a file with the minimal code and one with the errors I receive (I receive another one too). I am struggling to achieve that all day long. :/
On 16 April 2014 00:41, Georgios Samaras <georgesamarasdit@gmail.com> wrote:
I can not create a point in d(in the code M is dimensions) dimensions. The error is this: error: the value of ‘M’ is not usable in a constant expression note: ‘int M’ is not const error: template argument 2 is invalid
and the line is this: int M; .. typedef bg::model::point<float, M, bg::cs::cartesian> point;
The compiler is right, as in this context of template instantiation, M must denote a constant expression and M must not be evaluated at run-time. This error has nothing to do with a problem in Boost.Geometry, but it indicates problem in your program, misuse of the class template(s). Best regards, -- Mateusz Łoskot, http://mateusz.loskot.net
The compiler is right, as in this context of template instantiation, M must denote a constant expression and M must not be evaluated at run-time.
The compiler is "always" right. How Boost.Geometry allows me to achieve my purpose (i.e. creating a M-dimension point)? I tried to work around it, but I failed and can not find any workable solutions in Google. Moreover, I didn't find anything about that in the docs. Thanks, George PS - I was warned about top-posting (is my message ok now?)
On 16 April 2014 11:28, Georgios Samaras <georgesamarasdit@gmail.com> wrote:
The compiler is right, as in this context of template instantiation, M must denote a constant expression and M must not be evaluated at run-time.
The compiler is "always" right. How Boost.Geometry allows me to achieve my purpose (i.e. creating a M-dimension point)? I tried to work around it, but I failed and can not find any workable solutions in Google. Moreover, I didn't find anything about that in the docs.
First, you need to understand requirements on non-type template parameters in C++ (dimension is an integer, not a type), that it must be a constant expression known at compile-time, *not* run-time! Second, look at docs for geometry model, namely point http://www.boost.org/doc/libs/1_55_0/libs/geometry/doc/html/geometry/referen... The example presents how to instantiate point template to generate types for 2D and 3D points: bg::model::point<double, 2, bg::cs::cartesian> point1; bg::model::point<double, 3, bg::cs::cartesian> point2 where 2 and 3 denote your M value. Long story short: int const M = 3; typedef bg::model::point<float, M, bg::cs::cartesian> point; Best regards, -- Mateusz Łoskot, http://mateusz.loskot.net
Long story short: int const M = 3;
I have checked the link already. Yes, I had tried that it worked, but, as I said the dimensions are going to be read from a file given by the user (that is run time I guess). That means that Boost can not let the user apply a desired dimension? If that is the case, how am I supposed to initialize the point? I have read the data in a 2D array and I do typedef bg::model::point<float, constM, bg::cs::cartesian> point; for(int j = 0 ; j < M ; ++j) { bg::set<j>(tmp, a[i][j]); // this will fail for the same reason you mentioned before, but it can not be const now //int const conj = j; //bg::set<(int const)j>(tmp, a[i][j]); } Sorry for asking again, but I can't make it work.
On 16 April 2014 12:02, Georgios Samaras <georgesamarasdit@gmail.com> wrote:
Long story short: int const M = 3;
I have checked the link already. Yes, I had tried that it worked, but, as I said the dimensions are going to be read from a file given by the user (that is run time I guess). That means that Boost can not let the user apply a desired dimension?
You need to use multiple models and dispatch between them in runtime. -- Mateusz Łoskot, http://mateusz.loskot.net
On 16 April 2014 12:30, Mateusz Łoskot <mateusz@loskot.net> wrote:
On 16 April 2014 12:02, Georgios Samaras <georgesamarasdit@gmail.com> wrote:
Long story short: int const M = 3;
I have checked the link already. Yes, I had tried that it worked, but, as I said the dimensions are going to be read from a file given by the user (that is run time I guess). That means that Boost can not let the user apply a desired dimension?
You need to use multiple models and dispatch between them in runtime.
You may find this overview helpful "BG uses a generic programming paradigm, just as the entire Boost library does. BG is mostly composed of function templates and class templates, so it’s not OK to use the dynamic polymorphism paradigm here, we instead have to statically dispatch geometry objects of each type to the right version of each BG spatial function call." http://mysqlserverteam.com/making-use-of-boost-geometry-in-mysql-gis/ IOW, you need to think of these two as separate types: bg::model::point<double, 2, bg::cs::cartesian> point1; bg::model::point<double, 3, bg::cs::cartesian> point2; like one is std::vector<float> and one is std::vector<int>. Best regards, -- Mateusz Łoskot, http://mateusz.loskot.net
On Wed, Apr 16, 2014 at 12:02:39PM +0200, Georgios Samaras wrote:
Long story short: int const M = 3;
I have checked the link already. Yes, I had tried that it worked, but, as I said the dimensions are going to be read from a file given by the user (that is run time I guess). That means that Boost can not let the user apply a desired dimension?
It's not really about Boost. It's about understanding the fundamentals of templates. They are instantiated at compile-time, and instantiations with distinct parameters are distinct types. If you want to make a runtime choice based on a runtime count, you need to either have instantiations of the template for each and use a wrapper that applies sufficient type erasure/hiding, or you would have to have a type that has runtime-parametricism in dimensions. If your question is: "does this library have a type with runtime-configurable dimensionality" and "can I use that type with the algorithms", you should probably ask _that_ question instead. -- Lars Viklund | zao@acc.umu.se
On 16 April 2014 12:37, Lars Viklund <zao@acc.umu.se> wrote:
If your question is: "does this library have a type with runtime-configurable dimensionality" and "can I use that type with the algorithms", you should probably ask _that_ question instead.
Indeed, and to rephrase the question that way, one needs to understand "It's not really about Boost. It's about understanding the fundamentals of templates." Thanks Lars for clarifying it better. Best regards, -- Mateusz Łoskot, http://mateusz.loskot.net
Thanks for the replies, now it is clearer. However, the minimum dimension I have in my datasets is 100 and I want to run NN with dimension 10000. So, how I am going to initialize a point? template <int CompileTimeDimension> void fill(point& tmp) { for(int j = CompileTimeDimension - 1 ; j >= 0 ; --j) { bg::set<CompileTimeDimension-->(tmp, 5); } } Even I can see that the above code won't even compile. Writting manually bg::set<0>(tmp, 5), ..., bg::set<10000>(tmp, 5) does not really sound a good idea. So what should I do? Maybe boost nearest's neighbors are meant to be used in higher dimensions?
Hi, Never use tree methods in high dimensional spaces unless you have n >> 2^dim data points. Use instead some fast matrix library and brute-force the nearest neighbours. Cheers, Oswin On 16.04.2014 14:32, Georgios Samaras wrote:
Thanks for the replies, now it is clearer. However, the minimum dimension I have in my datasets is 100 and I want to run NN with dimension 10000.
So, how I am going to initialize a point?
template <int CompileTimeDimension> void fill(point& tmp) { for(int j = CompileTimeDimension - 1 ; j >= 0 ; --j) { bg::set<CompileTimeDimension-->(tmp, 5); } }
Even I can see that the above code won't even compile. Writting manually bg::set<0>(tmp, 5), ..., bg::set<10000>(tmp, 5) does not really sound a good idea. So what should I do?
Maybe boost nearest's neighbors are meant to be used in higher dimensions?
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On 16 April 2014 15:00, Georgios Samaras <georgesamarasdit@gmail.com> wrote:
Never use tree methods in high dimensional spaces
Good observations, but I am intrigued on the topic. This is way I want to see what Boost library is able to do there. But, I am afraid I can not even use it.
Think of a tuple: std::tuple<int, int, int, int, [repeat 9996 times]> and now imagine how to iterate over the elements. Idiomatic way to achieve it is to use compile-time recursion. Best regards, -- Mateusz Łoskot, http://mateusz.loskot.net
The code has the error: "expected unqualified-id before ‘return’", but I do not see any missing bracket or relevant. How is this going to be fixed? No, there is not a problem in the NN now, the problem is in the creation of the points that will be stored in the tree. I made that question in a second phase. :)
The code has the error: "expected unqualified-id before ‘return’", but I do not see any missing bracket or relevant. How is this going to be fixed?
I was referring to the code Mateusz posted. The other code with the recursion (reminds a lot of Prolog ;p) has the error variable or field ‘fill’ declared void When I am trying to enclose it in a class I phase many errors.
On 16 April 2014 15:35, Georgios Samaras <georgesamarasdit@gmail.com> wrote:
The code has the error: "expected unqualified-id before ‘return’", but I do not see any missing bracket or relevant. How is this going to be fixed?
The code compiles for me in VS 2012 as well as GCC 4.8 (if I lower N of dimensions). See yourself http://coliru.stacked-crooked.com/a/04a8437af2842f3c Best regards, -- Mateusz Łoskot, http://mateusz.loskot.net
Yes, you are right. I messed up something with the file. I recreated it and it run. I will try to perform NN and report back. Thanks and sorry for my latency.
@Adam, it seems that I can reduce heavily the dimensions I want to test, just to take the big picture. So, I am going to try to write code to run NN.
I decided to choose dimensions 100 and 10000. With the second one, what mentioned above for compilation depth was happened. Thanks everybody for the help. This is enough for me. :)
Georgios Samaras wrote:
I decided to choose dimensions 100 and 10000. With the second one, what mentioned above for compilation depth was happened. Thanks everybody for the help. This is enough for me. :)
To be clear. If you used the recursive template technique, you've choosen all dimensions between 100 and 10000 must be compiled. If you wanted to use only those two dimensions you should rather just check the simple condition: if ( dim == 100 ) // do something for dimension 100 else if ( dim == 10000 ) // something for dimension 10k This way the compilation shouldn't fail. Regards, Adam
I am talking about the 2 dimensions. #include <boost/geometry.hpp> #include <boost/geometry/geometries/point.hpp> #include <boost/geometry/index/rtree.hpp> namespace bg = boost::geometry; namespace bgi = boost::geometry::index; template <int CompileTimeDimension> void do_something() { typedef bg::model::point<float, CompileTimeDimension, bg::cs::cartesian> point; bgi::rtree<point, bgi::linear<8> > rt; } int main() { int M; M = 100; if ( M == 100 ) do_something<100>(); else if ( M == 10000 ) do_something<10000>(); else std::cerr << "invalid dimension!"; return 0; } and here is the first lines of the errors In file included from ../boost/geometry/strategies/cartesian/centroid_weighted_length.hpp:23:0, from ../boost/geometry/strategies/strategies.hpp:33, from ../boost/geometry/geometry.hpp:35, from ../boost/geometry.hpp:17, from bla.cpp:66: ../boost/geometry/geometries/point.hpp: In static member function ‘static CoordinateType boost::geometry::traits::access<boost::geometry::model::point$ .. I am attaching the errors.
On 16 April 2014 16:45, Georgios Samaras <georgesamarasdit@gmail.com> wrote:
and here is the first lines of the errors In file included from ../boost/geometry/strategies/cartesian/centroid_weighted_length.hpp:23:0, from ../boost/geometry/strategies/strategies.hpp:33, from ../boost/geometry/geometry.hpp:35, from ../boost/geometry.hpp:17, from bla.cpp:66: ../boost/geometry/geometries/point.hpp: In static member function ‘static CoordinateType boost::geometry::traits::access<boost::geometry::model::point$ ..
This is irrelevant, it includes no error.
I am attaching the errors.
You should rather try to read the error messages yourself and see what the compiler is trying to tell you. Hint: error: template instantiation depth exceeds maximum of 1024 (use -ftemplate-depth= to increase the maximum) Best regards, -- Mateusz Łoskot, http://mateusz.loskot.net
Damn, I pasted only the 1st line, sorry. The max of 1024 means that I can not allocate a point in 10000 dimensions, right?
Georgios Samaras wrote:
Damn, I pasted only the 1st line, sorry.
The max of 1024 means that I can not allocate a point in 10000 dimensions, right?
This error is more related to the compiler than to Boost. Next time please search the Web first -> e.g. http://stackoverflow.com/questions/12277732/template-metaprogramming-recursi.... The compiler is telling you everything: 1. error: template instantiation depth exceeds maximum of 1024 2. (use -ftemplate-depth= to increase the maximum) Regards, Adam
I did performed google search, but I didn't find the link you provided. Sorry. So, now I receive: error: template instantiation depth exceeds maximum of 10001 (use -ftemplate-depth=.. Practically, that means that because of my compiler I can not use the boost library NN, right? On Wed, Apr 16, 2014 at 6:05 PM, Adam Wulkiewicz <adam.wulkiewicz@gmail.com>wrote:
Georgios Samaras wrote:
Damn, I pasted only the 1st line, sorry.
The max of 1024 means that I can not allocate a point in 10000 dimensions, right?
This error is more related to the compiler than to Boost. Next time please search the Web first -> e.g. http://stackoverflow.com/ questions/12277732/template-metaprogramming-recursion-up-limits.
The compiler is telling you everything:
1. error: template instantiation depth exceeds maximum of 1024 2. (use -ftemplate-depth= to increase the maximum)
Regards, Adam
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Georgios Samaras wrote:
I did performed google search, but I didn't find the link you provided. Sorry.
So, now I receive: error: template instantiation depth exceeds maximum of 10001 (use -ftemplate-depth=..
Practically, that means that because of my compiler I can not use the boost library NN, right?
10001 may be not enough...
I increased and it compile. However, I am -again- not able to continue, because now it says point not declared.. #include <boost/geometry.hpp> #include <boost/geometry/geometries/point.hpp> #include <boost/geometry/index/rtree.hpp> namespace bg = boost::geometry; namespace bgi = boost::geometry::index; template <int CompileTimeDimension> void do_something() { typedef bg::model::point<float, CompileTimeDimension, bg::cs::cartesian> point; bgi::rtree<point, bgi::linear<8> > rt; } template <std::size_t D, std::size_t N> struct fill { template <typename Point> static void apply(Point& p, typename bg::coordinate_type<Point>::type const& v) { bg::set<D>(p, v); fill<D + 1, N>::apply(p, v); } }; template <std::size_t N> struct fill<N, N> { template <typename Point> static void apply(Point&, typename bg::coordinate_type<Point>::type const&) {} }; int main() { int M; M = 100; if ( M == 100 ) do_something<100>(); else if ( M == 10000 ) do_something<10000>(); else std::cerr << "invalid dimension!"; point p; if ( M == 100 ) fill<0, 100>::apply(p, 5); else if ( M == 10000 ) fill<0, 10000>::apply(p, 5); else std::cerr << "invalid dimension!"; return 0; }
Georgios Samaras wrote:
I increased and it compile. However, I am -again- not able to continue, because now it says point not declared..
If you're talking about the point identifier used in the main() function then yes, the compiler is right. The point type is declared inside do_something() and is visible only inside this function. I understand that template metaprogramming may be confusing but typedefs and functions are elements of C language. I advice you to learn more about C++ before proceeding. C++ Primer Plus by Stephen Prata is a nice book but I'm sure you can find more in the Web. This mailing list doesn't cover general C++, only Boost-related questions should be posted here. Regards, Adam
#include <boost/geometry.hpp> #include <boost/geometry/geometries/point.hpp> #include <boost/geometry/index/rtree.hpp>
namespace bg = boost::geometry; namespace bgi = boost::geometry::index;
template <int CompileTimeDimension> void do_something() { typedef bg::model::point<float, CompileTimeDimension, bg::cs::cartesian> point; bgi::rtree<point, bgi::linear<8> > rt; }
template <std::size_t D, std::size_t N> struct fill { template <typename Point> static void apply(Point& p, typename bg::coordinate_type<Point>::type const& v) { bg::set<D>(p, v); fill<D + 1, N>::apply(p, v); } }; template <std::size_t N> struct fill<N, N> { template <typename Point> static void apply(Point&, typename bg::coordinate_type<Point>::type const&) {} };
int main() { int M; M = 100; if ( M == 100 ) do_something<100>(); else if ( M == 10000 ) do_something<10000>(); else std::cerr << "invalid dimension!"; point p; if ( M == 100 ) fill<0, 100>::apply(p, 5); else if ( M == 10000 ) fill<0, 10000>::apply(p, 5); else std::cerr << "invalid dimension!"; return 0; }
On 16 April 2014 18:24, Georgios Samaras <georgesamarasdit@gmail.com> wrote:
I did performed google search, but I didn't find the link you provided. Sorry.
So, now I receive: error: template instantiation depth exceeds maximum of 10001 (use -ftemplate-depth=..
Practically, that means that because of my compiler I can not use the boost library NN, right?
10001 may be not enough, Also, the Boost Discussion Policy says: do not top post http://www.boost.org/community/policy.html#quoting Best regards, -- Mateusz Łoskot, http://mateusz.loskot.net
Thanks for the replies, now it is clearer. However, the minimum dimension I have in my datasets is 100 and I want to run NN with dimension 10000. So, how I am going to initialize a point? template <int CompileTimeDimension> void fill(point& tmp) { for(int j = CompileTimeDimension - 1 ; j >= 0 ; --j) { bg::set<CompileTimeDimension-->(tmp, 5); } }
Maybe something like this (untested, you might have to put these inside a class and make CTD a template parameter of the class, etc.): template <int CTD> void fill(point& tmp) { bg::set<CTD>(tmp, 5); fill<CTD - 1>(tmp, 5); } template <> void fill<0>(point& tmp) { bg::set<0>(tmp, 5); } Ilja
On 16 April 2014 14:32, Georgios Samaras <georgesamarasdit@gmail.com> wrote:
Thanks for the replies, now it is clearer. However, the minimum dimension I have in my datasets is 100 and I want to run NN with dimension 10000.
So, how I am going to initialize a point?
template <int CompileTimeDimension> void fill(point& tmp) { for(int j = CompileTimeDimension - 1 ; j >= 0 ; --j) { bg::set<CompileTimeDimension-->(tmp, 5); } }
Even I can see that the above code won't even compile. Writting manually bg::set<0>(tmp, 5), ..., bg::set<10000>(tmp, 5) does not really sound a good idea. So what should I do?
Once again, dimension is a compile-time property. #include <boost/geometry/geometries/point.hpp> #include <boost/geometry/algorithms/assign.hpp> namespace bg = boost::geometry; template <std::size_t D, std::size_t N> struct fill { template <typename Point> static void apply(Point& p, typename bg::coordinate_type<Point>::type const& v) { bg::set<D>(p, v); fill<D + 1, N>::apply(p, v); } }; template <std::size_t N> struct fill<N, N> { template <typename Point> static void apply(Point&, typename bg::coordinate_type<Point>::type const&) {} }; int main() { bg::model::point<double, 1000, bg::cs::cartesian> p1; fill<0, 1000>::apply(p1, 5); return 0; } But, you will likely hit compiler limits asking for 10K dimensions.
Maybe boost nearest's neighbors are meant to be used in higher dimensions?
Your problem has *nothing* to do with the NN algorithm as it is implemented in Boost.Geometry. Best regards, -- Mateusz Łoskot, http://mateusz.loskot.net
Georgios Samaras wrote:
Thanks for the replies, now it is clearer. However, the minimum dimension I have in my datasets is 100 and I want to run NN with dimension 10000.
So, how I am going to initialize a point?
template <int CompileTimeDimension> void fill(point& tmp) { for(int j = CompileTimeDimension - 1 ; j >= 0 ; --j) { bg::set<CompileTimeDimension-->(tmp, 5); } }
Even I can see that the above code won't even compile. Writting manually bg::set<0>(tmp, 5), ..., bg::set<10000>(tmp, 5) does not really sound a good idea. So what should I do?
Maybe boost nearest's neighbors are meant to be used in higher dimensions?
I'm curious about the result! I didn't test Boost.Geometry for such big dimensions. One point will take 40kB, right? 1M of points would require 40 GB of memory. I'm wondering how big will be the difference in performance of e.g. simple searching in std::vector in O(N) vs rtree kNN. How many points do you want to store in the rtree? If the number is too small you may not see the difference. In order to handle arbitrary dimensions (more or less) you might replace the for-loop with the compile-time recursive template (see the code below). Assuming the compiler would be able to compile it (it will take some time). E.g. VS2010 stops on CompileTimeDimension=3030 with the "error C1001: An internal error has occurred in the compiler" and a note: "compiler is out of heap space". It probably would be possible to somehow increase it with some compler parameter but I wouldn't recommend it. So if you're sure that you're unable to specify some dimensions for which your program should work or at least make the possible range of dimensions shorter, e.g. you know that there can only be {100, 1000, 10000} or at least [100, 200, 300, ... 10000], then Boost.Geometry is probably not suitable for you needs. Or maybe someone else has some other idea? #include<boost/geometry.hpp> #include <boost/geometry/geometries/point.hpp> #include <boost/geometry/index/rtree.hpp> namespace bg = boost::geometry; namespace bgi = boost::geometry::index; template <int CompileTimeDimension> void do_something() { typedef bg::model::point<float, CompileTimeDimension, bg::cs::cartesian> point; bgi::rtree<point, bgi::linear<8> > rt; } template <int CompileTimeDimension, int Max> struct do_something_for_dimension { static void apply(int run_time_dimension) { if ( run_time_dimension == CompileTimeDimension ) do_something<CompileTimeDimension>(); else do_something_for_dimension<CompileTimeDimension + 1, Max>::apply(run_time_dimension); } }; // specialization to break the compile-time recursion template <int Max> struct do_something_for_dimension<Max, Max> { static void apply(int) { throw std::runtime_error("run-time dimension not found!"); } }; int main() { int run_time_dimension = 1000; if ( run_time_dimension < 100 || run_time_dimension >= 10001 ) std::cerr << "invalid dimension!"; else do_something_for_dimension<100, 10001>::apply(run_time_dimension); } Regards, Adam
Hi Georgios, Georgios Samaras wrote:
Long story short: int const M = 3;
I have checked the link already. Yes, I had tried that it worked, but, as I said the dimensions are going to be read from a file given by the user (that is run time I guess). That means that Boost can not let the user apply a desired dimension?
If that is the case, how am I supposed to initialize the point? I have read the data in a 2D array and I do
typedef bg::model::point<float, constM, bg::cs::cartesian> point; for(int j = 0 ; j < M ; ++j) { bg::set<j>(tmp, a[i][j]); // this will fail for the same reason you mentioned before, but it can not be const now //int const conj = j; //bg::set<(int const)j>(tmp, a[i][j]); }
Sorry for asking again, but I can't make it work.
First, you should learn and understand the difference between run-time function parameters and compile-time template parameters. There is a lot of resources in the Web you can use. In short, everything between <...> must be known at compile-time. In the above code you try to use run-time variables (j) as template parameters. To propose a solution we should know more about your application. The user can define the dimension but may it be any number or are there some bounds, i.e. min and max dimension? Suppose the user may specify dimension 2 or 3, then you could use something like this: template <int CompileTimeDimension> void do_something() { typedef bg::model::point<float, CompileTimeDimension, bg::cs::cartesian> point; // ... } // ... if ( run_time_dimension == 2 ) do_something<2>(); else if ( run_time_dimension == 3 ) do_something<3>(); else std::cerr << "invalid dimension!"; Regards, Adam
participants (6)
-
Adam Wulkiewicz -
Georgios Samaras -
Ilja Honkonen -
Lars Viklund -
Mateusz Łoskot -
oswin krause