Can I build a KDTree of pointers to objects?

[Paul Harris]

2008/4/29 Eric Fowler <eric.fowler at gmail.com>:

>
> On Mon, Apr 28, 2008 at 8:33 PM, Sylvain Bougerel <
> sylvain.bougerel.devel at gmail.com> wrote:
>
> > Sorry this comes a little late:
> >
> > On Fri, Apr 25, 2008 at 12:16 PM, Eric Fowler <eric.fowler at gmail.com>
> > wrote:
> > > I have a toy app that is storing a set<> of pointers to a PlanePoint
> > object,
> > > itself little more than a wrapper for {int x, y;}.
> > >
> > > Since I am storing pointers I want to store pointers in my KDTree too.
> > With
> > > that in mind, I wrote this:
> > >
> >
> > Now, in the KD tree, as Paul explained in this mail, we use an
> > accessor to get the data, we do not directly manipulate the element.
> > So you need to define the accessor just as Paul told you.
> >
> > May be, according to your example, it will look like smth like this:
> >
> > struct accessor {
> >   typedef int result_type;
> >   int operator () (const PlanePoint *e, int k) const { return
> > (k==0)?e->x, e->y; }
> > };
> >
>
> I had done something like this at some point and was still getting
> errors.But I have made progress and shall revisit it.
>
>
> >
> > Okay I haven't tried. Of course, as Paul says you shouldn't move your
> > PlanePoint around in memory. But if you're using pointers in your
> > set<> as well, I don't think there is a danger.
> >
>
>
> > Why just not using a pointer at all? Your object is just a few `int'?
> > You will gain in performance when you need to do computation (cause it
> > does not need to access the memory of the pointer) and you will also
> > gain in ease with your implementation. You might consume more memory,
> > but not necessarily, because you will not leak memory with copies of
> > your plane object.
>
>
> Hmm, that is an idea. I was thinking of something like this:
>
> class MyPoint
> {
> public: int x, y;
>
> char * data;
> int more_data;
> double still_more_data;
> bool by_now_you_get_the_idea;
> };
>
> ...and did not want to duplicate all that stuff in the kdtree, especially
> since I had reasons for storing the structs elsewhere (need to lookup on
> different criteria, effectively a different index).
>

if that is the extent of your data, then it would just use copies inside the
kdtree instead of pointers.

i use pointers when i need to find an item, and then refer back to where it
was originally in the vector... or if there was a *lot* of data in each
point.

check sizeof(MyPoint), it'll be about 18 bytes or so.  thats not much.  even
if you had a million items, thats only 18mb.  trivial relative to ram these
days.   start to worry when your tree is something like 100mb or you have to
be careful of lots of copies...  otherwise you are optimising prematurely.


>
> So I could just use the x,y, and a pointer to the MyPoint in a new struct
> that is made just for KDTree-ability, and store and search over them. This
> is a little redundant but the coding is simpler and memory-wise only a
> little more costly.
>

if you use the accessor, then you wont clutter your class up with operators
you'll never use without kdtree.


>
> But I think I will try to make the pointers work, mainly because that sort
> of thing is my style, and I am getting too old to change =-)
>
>

go for it


>
>
> >
> > Also there is one side effect that Paul did not mention: you cannot
> > change the coordinate of your PlanePoint once they are inside the
> > tree. It's easy to overlook this with pointers because it can be done.
> > But you would completely invalidate your tree. You would not get
> > memory corruption, but it will just return weird results when you send
> > a query.
>
> Yes, I intend to be cautious. I understand the procedure is: (1) remove
> point from KDTree; (2) change coordinates; (3) re-insert into KDTree; (4)
> optimiZe() the tree.
>
> >
like Sylvain says, you won't get a segfault or crash or memory corruption -
because the pointers are still valid.   but it'll throw kdtree's find off
the scent so it may skip entire bits of the tree when searching.

no need to remove and re-add... i think it'll be ok if you simply make the
change to the item, and then optimise.

or, i think it will be fine if you remove, and then reinsert without
optimisation (? check this, i assume the tree will be just as correct as
before, but a little deeper ?)




>
> >
> >
> > I recommend against the use of pointers. It does not mean that
> > libkdtree should not support it. But it's generally a bad idea.
> >
>
thats one opinion.  my opinion is use what is appropriate.  if you have a
huge amount of data with the locations buried in the data, then use
pointers.   if you do it without pointers and find that the performance is
adequate (in terms of memory usage and copy time), then don't use
pointers.   there is a greater chance that the compiler will be able to
optimise things when you use less pointers and function pointers.  and its
easier to comprehend once you get used to the idea.  and its more STL-like
(so you can improve your skills in that coding style).

use pointers, but be aware that you need to remember what the pointers are
pointing to, and where.  and you need to preserve the target block of
memory.   its one more thing to remember.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20080429/402182fd/attachment-0001.htm