|
Boost : |
From: JoaquÃn M López Munoz (joaquin_at_[hidden])
Date: 2006-11-24 16:04:14
>
Hello Janek,
Janek Kozicki <janek_listy <at> wp.pl> writes:
> Since I can't stop thinking about that, I'll try to describe the most
> difficult data structure that I have here. Maybe you will have some
> suggestions. And maybe it will help me to sort the thing out.
>
> In my program I am calculating bodies collisions and other
> kind of interactions. This is a physical simualtion stuff.
>
> I have a container (an easier one) with bodies where each body has an
> integer ID number. And the bodies can interact together, there are
> various kinds of interaction. And I need to store those interactions
> in a container. The keys are:
>
> - interaction type: each polymorphic interaction type stored in this
> container is a different kind of interaction. Sometimes I need to
> interate over all interactions of selected type, thus it becomes
> one of the keys.
> This is an integer.
>
> - a set of interacting bodies: any number of bodies can interact. Two
> or more bodies, but very rarely as much as four.
> - Sometimes I need to iterate over all interactions which
> involve a selected body or,
> - check if an interaction of given type between bodies 1, 2 and 3
> already exists, then get it, or add it, if it didn't exist.
> This is a list of integer values (IDs of bodies).
[...]
> One solution (a bit of pseudocode) could be:
>
> multi_index_container<
> interaction*,
> indexed_by<
> ordered_non_unique<member<interaction*,int,&interaction::type> >
>
> ordered_unique
<member<interaction*,std::set<int>,&interaction::bodies> >
> // non_unique in fact. But uniqe with respect to &interaction::type.
> // That's why it's pseudocode
>
> >
> >;
>
> But how to make this and get a reasonable performance?
Well, your proposed structure has reasonable performance
and complies with all your requirements except the ability
to iterate on interactions involving a given body. In order
to get this extra feature, you might need to set up an
extra container like
std::[unordered_]multimap<int /* body ID */, interaction*>
which is kept in sync with the multi-index container: when
an interaction is inserted, the multimap must be fed
as many entries as bodies the given interaction involves.
I can't think of a more elegant solution than this, which
is a pity since one of the key goals of B.MI is to elminate
the need to manually maintain this kind of composite
structures :(
[...]
> Performance priorities (from most important, to least important):
> A)iterating over all elements with the same &interaction::type must
> be constant access time.
>
> B)finding if there is an interaction between (1,2,3) - great if it
> was constant time (N-dimensional matrix gives that), I guess that log(O)
> is the best we can have.
> C)deleting and adding an interaction, again I guess that constant
> time is not possible.
> D)iterating over all interactions involving a body with given ID
> is used less often so can be a bit slower.
If you use hashed indices instead of ordered ones and also
use an unordered_multimap for the additional data structure,
you can get the performance you aim for, constant time
for A), B), C) and D).
HTH,
JoaquÃn M López Muñoz
Telefónica, Investigación y Desarrollo
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk