Thank you very much Guido! just what I needed :) . 2010/8/2 Guido Tack <[email protected]>
> Gustavo Gutierrez wrote: > > Probably what I am going to ask is not useful or is just to much > particular to my case that does not worth have it, however, I wouldn't > hesitate to ask :). > > > > While writing a propagator I realized that keeping some state in it will > lower the complexity. This propagator is on a finite set variable and what I > does is to track "the new elements in the glb" and propagate according with > its semantics. At the beginning to I was using an std::set to keep the "old > values" and using it to compute the new elements: > > > > new elements = current glb \ old values > > > > The propagator was performing well but the memory consumption and the > time to compute the intersection was quite high. After realizing that I > start using an IntSet instead of a std::set to keep the data. The advantage > is that the IntSet stores ranges and then is *hopefully* less memory hungry. > There is also something nice, you can use all the iterators with them (range > iterators). The only problem is that they are intended to be used only to > represent variable domains in initializations or when posting constraints > and this is reflected in the fact that they lack of "modification > operations" in the API. > > > > In my case I have to copy construct all the time and this is of course > time consuming but far better than my previous implementation. Now my > question, sounds it very crazy or stupid to use the IntSet in this way?, if > it does not, then it would be nice to provide an specialization (via > inheritance, for instance) that allows this kind of use. What do you think? > > Yes, that is very crazy :-) However, there's a different data structure > you can use in exactly the way you describe. It's actually two data > structures, LUBndSet and GLBndSet. The difference is in the available > operations: LUBndSet has intersectI and excludeI operations (i.e., it can > shrink), and GLBndSet has an includeI operation (i.e., it can grow). These > sets are used internally for implementing set variables. In your case, you'd > use a GLBndSet (and includeI the current lower bound after each > propagation). There's an iterator called BndSetRanges that you can use on > these sets. > You should have a look at the IntersectionN propagator, it uses a LUBndSet > to remember the intersection of all assigned variables it has seen so far > (it will show you how to initialize and copy these sets). > > Cheers, > Guido > > -- > Guido Tack, http://people.cs.kuleuven.be/~guido.tack/ > > > > > _______________________________________________ > Gecode users mailing list > [email protected] > https://www.gecode.org/mailman/listinfo/gecode-users > -- Gustavo Gutierrez
_______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
