Ulrich Scholz wrote: > Dear Marco and all, > > some simple tests show that the performance of the fd_sets library is > related to domain size: > > Consider the three clauses below. All require a non-empty set to have an > empty intersection with itself, thus they all should fail. > > t1 does not fail but yields delayed goals. So to detect the inconsistency, > we have to search for a solution. > > t2 does this search and fails as expected. > > t3 is the same clause as t2, with the difference of using a largely extended > domain. Unfortunately, the inconsistency is found much slower that for > clause t2. Sorry for not joining the discussion earlier. As you noticed, the solution time is dependent of the domain sizes. This is because in {fd,ic}_sets the domains are represented with a flag for each element that indicates whether the element is included the set, excluded from the set, or unknown. At the beginning of the computation, membership for every element is unknown, and at the end every element is decided. So (at least in the success case), every element membership flag must be set in the course of the computation, therefore the time is proportional to the domain sizes. It would be quite a nice project to change the representation such that ranges of elements can be included/excluded in constant time! -- JoachimReceived on Thu Oct 16 2008 - 05:48:14 CEST
This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET