From: Michael Andreen <harv@ruin.nu>
Date: Mon, 29 Oct 2007 13:20:47 +0000 (+0000)
Subject: Small optimization in sort()
X-Git-Tag: v0.1~9
X-Git-Url: https://ruin.nu/git/?p=germs.git;a=commitdiff_plain;h=34293060b5be57f6e2ea620ad4c3ff0f94e1d305;hp=ebdd033ac96ff67b70a80146d076f07ad68f5dad

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.
---

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<int>(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.
 	}