From 34293060b5be57f6e2ea620ad4c3ff0f94e1d305 Mon Sep 17 00:00:00 2001 From: Michael Andreen Date: Mon, 29 Oct 2007 13:20:47 +0000 Subject: [PATCH] Small optimization in sort() safeActions() is guaranteed to only return actions that reduces the inversion distance by one, so we don't have to compute the inversion distance at each step. --- src/genesorter.cpp | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/src/genesorter.cpp b/src/genesorter.cpp index 81b9da5..3198543 100644 --- a/src/genesorter.cpp +++ b/src/genesorter.cpp @@ -41,7 +41,8 @@ struct ScoreCmp { GeneSorter::ActionList GeneSorter::sort(const GeneOrder& go, const Model& m){ ActionList al; GeneOrder temp(go); - while(inversionDistance(temp) > 0){ + size_t dist = inversionDistance(temp); + while(dist > 0){ //cout << "Distance: " << inversionDistance(temp) << " : "; //copy(temp.begin(), temp.end(), ostream_iterator(cout, " ")); //cout << endl; @@ -54,6 +55,7 @@ GeneSorter::ActionList GeneSorter::sort(const GeneOrder& go, const Model& m){ SortAction sa = pq.top().second; sa(temp); al.push_back(sa); + --dist; }else return ActionList(); //TODO: Need to handle hurdles. } -- 2.39.2