[gecode-users] Iterating/filtering IntView in Gecode 3.x

[Martin Mann]

Hi Peter,

I guess you iterate over the variables in increasing order already! 
Thus, you filled your std::vector ordered!

Since the vector::push_back operation is on average much faster than the 
set::insert operation (that cares about the sorting), you might get even 
better runtimes by going back to your vector and an adaption of the 
range iterator code..

But just a suggestion. And don't forget to have a look at the new Gecode 
manual draft! Christian and Co might have an even better solution at hand!

so long,

Martin


Peter Vanhee schrieb:
> Thanks Martin, 
> 
> this is very helpful.
> 
> I modified my code to use std::set as well with your range iterator, and I have a huge speed increase.
> Note that I used narrow_r instead of inter_r.
> 
> Thanks!
> Peter
> 
> On 19 Mar 2010, at 15:58, Martin Mann wrote:
> 
>> Hi Peter,
>>
>> I solved that problem for Gecode 1.3.0 (still running for 3.*) by a dedicated implementation of a Gecode RangeIterator for a std::set (source attached). The source code can be easily adapted for your purpose either by sorting the std::vector after filling or by ensuring that you fill it with values of increasing order.
>>
>> Dont know if there is a "native" Gecode support in 3.*, havent checked since I wrote it. :)
>>
>> the application is than quite simple:
>>
>> ////////////////////////////////////////////////////
>>  std::set<int> data; // fill data
>>  GC_StlSetRangeIterator dataIt(&data);
>>  x.inter_r(*home, dataIt);
>> ////////////////////////////////////////////////////
>>
>> Hope it helps,
>>
>> Martin
>>
>>
>>
>> Peter Vanhee schrieb:
>>> Hey all,
>>> I have more or less the same problem as mentioned here: http://thread.gmane.org/gmane.comp.lib.gecode.user/919,
>>> however the solution seems to be outdated for gecode 3.x: e.g. GECODE_AUTOARRAY is not existing anymore etc.
>>> Within the binary propagator, and when one variable is assigned (x0), I need to filter values in the other variable (x1). What I do right  now is:
>>> // loop over all values of x1 and push to remove if necessary
>>> vector<int> remove;
>>> for (IntVarValues i(*x1); i(); ++i) {
>>> 	if (!predicate(home, x0->val(), i.val())) remove.push_back(i.val());
>>> }
>>> // remove values from domain
>>> for(vector<int>::iterator i=remove.begin(); i!=remove.end(); ++i) {
>>> 	GECODE_ME_CHECK(x1->nq(_home, r));
>>> }
>>> This is not at all efficient:  90% of the time is spent in Int::IntVarImp::nq_full, and 38% in Int::IntVarImp::RangeList::min().
>>> How can I change this? I have variables with big domains (into the millions of values) that have few continuous ranges.
>>> Thanks,
>>> Peter


-- 
Martin Mann, Dipl. Bioinf.
Bioinformatics - Inst. of Computer Science
Albert-Ludwigs-University Freiburg
Tel: ++49-761-203-8259
Fax: ++49-761-203-7462
http://www.bioinf.uni-freiburg.de/~mmann/