Subj : Re: Compiler and an interpreter To : comp.programming From : Jon Harrop Date : Sun Aug 07 2005 03:17 am Gerry Quinn wrote: > In article <42f4f604$0$91541$ed2e19e4@ptn-nntp-reader04.plus.net>, > usenet@jdh30.plus.com says... >> Gerry Quinn wrote: > >> The set of "n"th-nearest neighbours is defined as: >> >> nth(i, 0) = {i} >> nth(i, 1) = neighbours(i) >> nth(i, n) = union(j in nth(i,n-1), nth(i, 1)) - nth(i, n-1) - nth(i, n-2) >> >> where neighbours(i) gives the set of neighbours of "i". > > I don't understand the last line, so I may have solved a different > problem! It is, at least, a similar problem. I calculate a layer of > neighbours expanding outward from a single point - in a simple cubic > lattice they would be a series of octahedral layers of increasing size. > > In other words, I am saying: > nth( i, n ) = all neighbours of nth( i, n-1 ), that don't appear in > nth( i, n-1 ) or nth( i, n-2 ) Exactly. > The following compiles, It doesn't compile here (see below) but this serves as a fine example of debugging C++. I've been working on it for 30mins and I'm damned if I can see what's wrong... :-( > but I haven't tested it so it could be bugged. > I haven't used sets before but they seem straightforward. I use > vectors where possible and don't use complicated nested templates. I > think it's fairly comprehensible what I'm doing. At least it's > comprehensible to me whereas your code isn't, but perhaps that > situation is symmetric! Curiously, FindNthNeighbours is clear to me (and imperative equivalent of my code) but I don't understand what FindNeighbours is doing. > I did hardcode 3D, for efficiency and because it's faster to type - it > would be easy to use a vector. That makes a significant difference to performance but I'd like to measure your code anyway - it is interestingly different. > I'd be surprised if it was particularly slow. However, it just occurs > to me that one could modify the FindNeighbours() function to check the > m_Prev and m_Current layers before inserting a neighbour into the > m_Next. This would obviate the need for set_difference() functions > because no invalid neighbour would ever be inserted. I don't know if > it's a win or not. The STL set_union and set_difference functions are slow. I'm not sure if that would be much faster though. > I've a feeling your nested templates are the cause of slowness > problems. No, it is the use of set_union and set_difference. If you code them yourself and reuse temporary scratch space then the C++ is ~5x faster than the OCaml. However, that is quite a bit of work and the result is significantly longer and more obfuscated than the OCaml (which is little more than the mathematical expression). > set_difference( work.begin(), work.end(), > m_Current.begin(), m_Current.end(), work2.begin() ); Starting with this line, I get the errors: $ g++ nth.cpp -o nth /usr/include/c++/3.3/bits/stl_algo.h: In function `_OutputIter std::set_difference(_InputIter1, _InputIter1, _InputIter2, _InputIter2, _OutputIter) [with _InputIter1 = std::_Rb_tree_iterator, _InputIter2 = std::_Rb_tree_iterator, _OutputIter = std::_Rb_tree_iterator]': nth.cpp:122: instantiated from here /usr/include/c++/3.3/bits/stl_algo.h:3807: error: passing `const Neighbour' as `this' argument of `Neighbour& Neighbour::operator=(const Neighbour&)' discards qualifiers /usr/include/c++/3.3/bits/stl_algobase.h: In function `_OutputIter std::__copy(_InputIter, _InputIter, _OutputIter, std::input_iterator_tag) [with _InputIter = std::_Rb_tree_iterator, _OutputIter = std::_Rb_tree_iterator]': /usr/include/c++/3.3/bits/stl_algobase.h:260: instantiated from `_OutputIter std::__copy_aux2(_InputIter, _InputIter, _OutputIter, __false_type) [with _InputIter = std::_Rb_tree_iterator, _OutputIter = std::_Rb_tree_iterator]' /usr/include/c++/3.3/bits/stl_algobase.h:303: instantiated from `_OutputIter std::__copy_ni2(_InputIter, _InputIter, _OutputIter, __false_type) [with _InputIter = std::_Rb_tree_iterator, _OutputIter = std::_Rb_tree_iterator]' /usr/include/c++/3.3/bits/stl_algobase.h:323: instantiated from `_OutputIter std::__copy_ni1(_InputIter, _InputIter, _OutputIter, __false_type) [with _InputIter = std::_Rb_tree_iterator, _OutputIter = std::_Rb_tree_iterator]' /usr/include/c++/3.3/bits/stl_algobase.h:349: instantiated from `_OutputIter std::copy(_InputIter, _InputIter, _OutputIter) [with _InputIter = std::_Rb_tree_iterator, _OutputIter = std::_Rb_tree_iterator]' /usr/include/c++/3.3/bits/stl_algo.h:3817: instantiated from `_OutputIter std::set_difference(_InputIter1, _InputIter1, _InputIter2, _InputIter2, _OutputIter) [with _InputIter1 = std::_Rb_tree_iterator, _InputIter2 = std::_Rb_tree_iterator, _OutputIter = std::_Rb_tree_iterator]' nth.cpp:122: instantiated from here /usr/include/c++/3.3/bits/stl_algobase.h:228: error: passing `const Neighbour' as `this' argument of `Neighbour& Neighbour::operator=(const Neighbour&)' discards qualifiers Any ideas? -- Dr Jon D Harrop, Flying Frog Consultancy http://www.ffconsultancy.com .