yade-dev team mailing list archive

[noreply@xxxxxxxxxxxxx]

------------------------------------------------------------
revno: 3878
committer: Anton Gladky <gladky.anton@xxxxxxxxx>
timestamp: Tue 2016-05-31 21:10:52 +0200
message:
  Replace vector by unordered_map data structure in Matchmaker.
  
  It allows to search for colliding coefficients much faster
  than using a simple vector which is getting extremely slow
  with the large number of coefficients.
modified:
  pkg/common/MatchMaker.cpp
  pkg/common/MatchMaker.hpp


--
lp:yade
https://code.launchpad.net/~yade-pkg/yade/git-trunk

Your team Yade developers is subscribed to branch lp:yade.
To unsubscribe from this branch go to https://code.launchpad.net/~yade-pkg/yade/git-trunk/+edit-subscription

=== modified file 'pkg/common/MatchMaker.cpp'
--- pkg/common/MatchMaker.cpp	2016-04-12 04:37:00 +0000
+++ pkg/common/MatchMaker.cpp	2016-05-31 19:10:52 +0000
@@ -5,12 +5,21 @@
 YADE_PLUGIN((MatchMaker));
 
 Real MatchMaker::operator()(int id1, int id2, Real val1, Real val2) const {
-	FOREACH(const Vector3r& m, matches){
-		if(((int)m[0]==id1 && (int)m[1]==id2) || ((int)m[0]==id2 && (int)m[1]==id1)) return m[2];
+	const int minId = std::min(id1, id2);
+	const int maxId = std::max(id2, id2);
+	
+	const auto foundMatchItem = matchSet.find (std::make_pair(minId, maxId));
+	
+	if ( foundMatchItem != matchSet.end() ) {
+		return foundMatchItem->second;
+	} else {
+		if(fbNeedsValues && (std::isnan(val1) || std::isnan(val2))) {
+			throw std::invalid_argument("MatchMaker: no match for ("+boost::lexical_cast<string>(id1)+
+			","+boost::lexical_cast<string>(id2)+"), and values required for algo computation '"+
+			algo+"' not specified.");
+		}
+		return computeFallback(val1,val2);
 	}
-	// no match
-	if(fbNeedsValues && (std::isnan(val1) || std::isnan(val2))) throw std::invalid_argument("MatchMaker: no match for ("+boost::lexical_cast<string>(id1)+","+boost::lexical_cast<string>(id2)+"), and values required for algo computation '"+algo+"' not specified.");
-	return computeFallback(val1,val2);
 }
 
 void MatchMaker::postLoad(MatchMaker&){
@@ -21,6 +30,14 @@
 	else if(algo=="max") { fbPtr=&MatchMaker::fbMax; fbNeedsValues=true;  }
 	else if(algo=="harmAvg") { fbPtr=&MatchMaker::fbHarmAvg; fbNeedsValues=true; }
 	else throw std::invalid_argument("MatchMaker:: algo '"+algo+"' not recognized (possible values: val, avg, min, max, harmAvg).");
+
+	// Fill matchSet with values for a fast coefficient search
+	for (const auto & m : matches) {
+		const int minId = std::min((int)m[0], (int)m[1]);
+		const int maxId = std::max((int)m[0], (int)m[1]);
+		const auto idPair = std::make_pair(minId, maxId);
+		matchSet.insert(std::make_pair(idPair, m[2]));
+	}
 }
 
 Real MatchMaker::computeFallback(Real v1, Real v2) const { return (this->*MatchMaker::fbPtr)(v1,v2); }

=== modified file 'pkg/common/MatchMaker.hpp'
--- pkg/common/MatchMaker.hpp	2014-10-15 06:44:01 +0000
+++ pkg/common/MatchMaker.hpp	2016-05-31 19:10:52 +0000
@@ -1,6 +1,7 @@
 // 2010 © Václav Šmilauer <eudoxos@xxxxxxxx>
 #pragma once
-#include<lib/serialization/Serializable.hpp>
+#include <lib/serialization/Serializable.hpp>
+#include <boost/unordered_map.hpp>
 
 namespace py = boost::python;
 
@@ -11,7 +12,6 @@
 
 */
 class MatchMaker: public Serializable {
-	#if 1
 		Real fbZero(Real v1, Real v2) const{ return 0.; }
 		Real fbAvg(Real v1, Real v2) const{ return (v1+v2)/2.; }
 		Real fbMin(Real v1, Real v2) const{ return min(v1,v2); }
@@ -22,7 +22,10 @@
 		// whether the current fbPtr function needs valid input values in order to give meaningful result.
 		// must be kept in sync with fbPtr, which is done in postLoad
 		bool fbNeedsValues;
-	#endif 
+		
+		// unordered set for a fast coefficient search
+		boost::unordered_map<std::pair<int, int>, Real> matchSet;
+		
 	public:
 		virtual ~MatchMaker() {};
 		MatchMaker(std::string _algo): algo(_algo){ postLoad(*this); }
@@ -34,7 +37,7 @@
 		// if no match is found and val1 or val2 are not given, throw exception
 		Real operator()(const int id1, const int id2, const Real val1=NaN, const Real val2=NaN) const;
 		YADE_CLASS_BASE_DOC_ATTRS_CTOR_PY(MatchMaker,Serializable,"Class matching pair of ids to return pre-defined (for a pair of ids defined in :yref:`matches<MatchMaker.matches>`) or derived value (computed using :yref:`algo<MatchMaker.algo>`) of a scalar parameter. It can be called (``id1``, ``id2``, ``val1=NaN``, ``val2=NaN``) in both python and c++. \n\n.. note:: There is a :ref:`converter <customconverters>` from python number defined for this class, which creates a new :yref:`MatchMaker` returning the value of that number; instead of giving the object instance therefore, you can only pass the number value and it will be converted automatically.",
-			((std::vector<Vector3r>,matches,,,"Array of ``(id1,id2,value)`` items; queries matching ``id1`` + ``id2`` or ``id2`` + ``id1`` will return ``value``"))
+			((std::vector<Vector3r>,matches,,Attr::readonly,"Array of ``(id1,id2,value)`` items; queries matching ``id1`` + ``id2`` or ``id2`` + ``id1`` will return ``value``"))
 			((std::string,algo,"avg",Attr::triggerPostLoad,"Alogorithm used to compute value when no match for ids is found. Possible values are\n\n* 'avg' (arithmetic average)\n* 'min' (minimum value)\n* 'max' (maximum value)\n* 'harmAvg' (harmonic average)\n\nThe following algo algorithms do *not* require meaningful input values in order to work:\n\n* 'val' (return value specified by :yref:`val<MatchMaker.val>`)\n* 'zero' (always return 0.)\n\n"))
 			((Real,val,NaN,,"Constant value returned if there is no match and :yref:`algo<MatchMaker::algo>` is ``val``"))
 			, fbPtr=&MatchMaker::fbAvg; fbNeedsValues=true; /* keep in sync with the algo value for algo */