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

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