Hi! On Mon, 2009-05-25 at 16:35 +0200, Christian Schulte wrote: > Okay, then what one can do is use DFAs (or REGs) for specification, they are > not as fast but they work perfectly well with spares domains.
That's a great idea, but on this case I don't see a how can I specify the problem (or the allowable values for the tuples) using DFAs or REGs. Any way, I have tried the same tests using the Finite Domain Solver of GNU Prolog with its predicate fd_realtion/2 [1] that is very similar to Gecode extensional constraint, and the results were much better. Thank you, Pedro Salgueiro [1] http://www.gprolog.org/manual/html_node/gprolog062.html#toc274 > > Christian > > -- > Christian Schulte, www.ict.kth.se/~cschulte/ > > > -----Original Message----- > From: users-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf > Of Mikael Zayenz Lagerkvist > Sent: Monday, May 25, 2009 4:30 PM > To: Denys Duchier > Cc: us...@gecode.org > Subject: Re: [gecode-users] Symbolic Constraints - fd_relation contraint in > Gecode? > > Hi, > > On Wed, May 20, 2009 at 8:36 PM, Denys Duchier > <denys.duch...@univ-orleans.fr> wrote: > > I could be wrong about this, but I just had a quick glance at the > > implementation and its seems to allocate datastructures of a size > > proportial to the width of the domain. So if you have small values and > > very large values, the width is going to be very large. > > > > If I am right, then you might be better off encoding your N values into > > the interval [0,N-1] and then possibly using an element constraint to > > decode them where necessary. > > > > Then again, I could be completely off base :-/ > > Actually, you are completely right, and it also says so in the > documentation [1]: > Warning: > If the domains for the $x_i$ are not dense and have similar > bounds, lots of memory will be wasted (memory consumption > is in $ > O\left(|x|\cdot|\min_i(\underline{x_i})-\max_i(\overline{x_i})|\right)$ > for the basic algorithm (epk = EPK_MEMORY) and additionally > $ > O\left(|x|^2\cdot|\min_i(\underline{x_i})|\max_i(\overline{x_i})|\right)$ > for the incremental algorithm (epk = EPK_SPEED). > > The memory-consumption in the size of the domain is inevitable for > reasonably efficient extensional propagators. The translation into a > dense domain from a sparse domain needs to happen at one point or > another anyway for efficient data-structure management, and I choose > not to do it automagically. > > Cheers, > Mikael > > [1] > https://www.gecode.org/doc-latest/reference/group__TaskModelIntExt.html#gf88 > 5611633b7b2bfb4d9512071dee9a3 > _______________________________________________ Gecode users mailing list us...@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
