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.
Christian -- Christian Schulte, www.ict.kth.se/~cschulte/ -----Original Message----- From: [email protected] [mailto:[email protected]] On Behalf Of Mikael Zayenz Lagerkvist Sent: Monday, May 25, 2009 4:30 PM To: Denys Duchier Cc: [email protected] Subject: Re: [gecode-users] Symbolic Constraints - fd_relation contraint in Gecode? Hi, On Wed, May 20, 2009 at 8:36 PM, Denys Duchier <[email protected]> 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 -- Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/ _______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users _______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
