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/
_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
