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/ > /* > * Main authors: > * Martin Mann http://www.bioinf.uni-freiburg.de/~mmann/ > * > * Contributing authors: > * Sebastian Will http://www.bioinf.uni-freiburg.de/~will/ > * > * Copyright: > * Martin Mann, 2007 > * > * This file is part of the CPSP-tools package: > * http://www.bioinf.uni-freiburg.de/sw/cpsp/ > * > * See the file "LICENSE" for information on usage and > * redistribution of this file, and for a > * DISCLAIMER OF ALL WARRANTIES. > * > */ > > #ifndef GC_STLSETRANGEITERATOR_HH_ > #define GC_STLSETRANGEITERATOR_HH_ > > > #include <set> > #include <iostream> > > /** > * Provides a constant Gecode RangeIterator of a std::set<int> > that > * calculates the ranges on demand. > */ > class GC_StlSetRangeIterator > { > private: > const std::set<int>* data; > std::set<int>::const_iterator actElem; > > bool noFurtherRange; > > int nextMin, nextMax; > > //! searchs for the next range and sets the inner > members > void getNextRange(); > public: > GC_StlSetRangeIterator(); > GC_StlSetRangeIterator(const std::set<int>* data_); > virtual ~GC_StlSetRangeIterator(); > > void init(const std::set<int>* const data_) { > data = data_; > noFurtherRange = false; > if (data != NULL) > actElem = data->begin(); > getNextRange(); > } > > bool operator()(void) const { return !noFurtherRange; } > void operator++(void) { getNextRange(); } > > int min(void) const { return nextMin; } > int max(void) const { return nextMax; } > unsigned int width(void) { return nextMax-nextMin+1; } > > > }; > > > #endif /*GC_STLSETRANGEITERATOR_HH_*/ > /* > * Main authors: > * Martin Mann http://www.bioinf.uni-freiburg.de/~mmann/ > * > * Contributing authors: > * Sebastian Will http://www.bioinf.uni-freiburg.de/~will/ > * > * Copyright: > * Martin Mann, 2007 > * > * This file is part of the CPSP-tools package: > * http://www.bioinf.uni-freiburg.de/sw/cpsp/ > * > * See the file "LICENSE" for information on usage and > * redistribution of this file, and for a > * DISCLAIMER OF ALL WARRANTIES. > * > */ > > #include "cpsp/GC_StlSetRangeIterator.hh" > > > GC_StlSetRangeIterator::GC_StlSetRangeIterator() : > data(NULL), noFurtherRange(true) > { > getNextRange(); > } > > GC_StlSetRangeIterator::GC_StlSetRangeIterator(const std::set<int>* > data_) : > data(data_), noFurtherRange(false) > { > if (data != NULL) > actElem = data->begin(); > getNextRange(); > } > > GC_StlSetRangeIterator::~GC_StlSetRangeIterator() > { > } > > void > GC_StlSetRangeIterator::getNextRange() { > if (data==NULL || actElem == data->end()) { > noFurtherRange = true; > return; > } > // find next range > nextMin = *actElem; > nextMax = nextMin; > // build up new upper bound until end of set reached or > gap in > // sequence > while ( (++actElem != data->end()) && (*actElem == > (nextMax+1))) { > nextMax++; > } > } > _______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
