From 6b0585c4c6aa12aad13965d5f17be9a4a51653b5 Mon Sep 17 00:00:00 2001 From: Michael Andreen Date: Thu, 30 Oct 2008 11:43:29 +0100 Subject: [PATCH] Basic implementation of threaded sorting Assumes the caller calles join() to wait for all threads to end. --- src/main.cpp | 63 ++++++++++++++++++++++++++++------------ src/reverseaction.h | 8 +++++ src/sortaction.h | 14 ++++++++- src/threadgenesorter.cpp | 31 ++++++++++++++++++++ 4 files changed, 97 insertions(+), 19 deletions(-) diff --git a/src/main.cpp b/src/main.cpp index abd520f..85569e1 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -3,6 +3,7 @@ #include #include #include +#include using namespace std; @@ -11,6 +12,7 @@ using namespace std; #include "geneorder.h" #include "modelidentifier.h" #include "genesorter.h" +#include "threadgenesorter.h" #include "sortaction.h" #include "genealgorithms.h" #include "model.h" @@ -25,7 +27,8 @@ int main(int argc, char** argv){ //Parse command line arguments int opt; - while ((opt = getopt(argc, argv, "im:n:hp")) != -1) { + int threads = 0; + while ((opt = getopt(argc, argv, "im:n:t:hp")) != -1) { switch (opt) { case 'm': model = Model::modelFactory(optarg); @@ -34,6 +37,9 @@ int main(int argc, char** argv){ case 'n': ann = optarg; break; + case 't': + threads = atoi(optarg); + break; case 'i': onlyIdentify = true; break; @@ -97,25 +103,46 @@ int main(int argc, char** argv){ if (onlyIdentify){ return EXIT_SUCCESS; } - //Sort - GeneSorter so; - GeneSorter::ActionList al = so.sort(go,model); - - //Print the result - double score = 0; - - GeneOrder temp(go); - for (GeneSorter::ActionList::iterator sa = al.begin(); sa != al.end(); ++sa){ - cout << "Action: " << sa->toString() << " model score: " << model.score(*sa,temp) << endl; - (*sa)(temp); - score += model.score(*sa,temp); - - if (printPerm){ - copy(temp.begin(), temp.end(), ostream_iterator(cout, " ")); - cout << endl; + if (threads){ + ThreadGeneSorter so(model, threads); + so.start(go); + so.join(); + + ThreadGeneSorter::SolutionsQueue solutions = so.solutions(); + + while (solutions.size() > 0){ + pair s = solutions.top(); + solutions.pop(); + + cout << "Actions: "; + for (GeneSorter::ActionList::iterator sa = s.second.begin(); sa != s.second.end(); ++sa){ + cout << sa->toString() << " "; + + } + cout << endl << "Score: " << s.first << endl; + } + + }else{ + //Sort + GeneSorter so; + GeneSorter::ActionList al = so.sort(go,model); + + //Print the result + double score = 0; + + GeneOrder temp(go); + for (GeneSorter::ActionList::iterator sa = al.begin(); sa != al.end(); ++sa){ + cout << "Action: " << sa->toString() << " model score: " << model.score(*sa,temp) << endl; + (*sa)(temp); + score += model.score(*sa,temp); + + if (printPerm){ + copy(temp.begin(), temp.end(), ostream_iterator(cout, " ")); + cout << endl; + } } + cout << "Avg score: " << score / al.size() << endl; } - cout << "Avg score: " << score / al.size() << endl; return EXIT_SUCCESS; } diff --git a/src/reverseaction.h b/src/reverseaction.h index e085780..267aeaa 100644 --- a/src/reverseaction.h +++ b/src/reverseaction.h @@ -63,6 +63,14 @@ class ReverseAction : public SortActionImpl{ return false; } + virtual bool operator<(const SortActionImpl& sa) const{ + if (const ReverseAction* psa = dynamic_cast(&sa)){ + if (_i < psa->_i || (_i == psa->_i && _j < psa->_j)) + return true; + } + return false; + } + /** * Gives a string representation of the action, for output */ diff --git a/src/sortaction.h b/src/sortaction.h index a99f786..a1c5566 100644 --- a/src/sortaction.h +++ b/src/sortaction.h @@ -44,7 +44,12 @@ class SortActionImpl{ * Compares sort actions. */ virtual bool operator==(const SortActionImpl& sa) const = 0; - + + /** + * Compares sort actions. + */ + virtual bool operator<(const SortActionImpl& sa) const = 0; + /** * Gives a string representation of the action, for output */ @@ -92,6 +97,13 @@ class SortAction{ return (*_action) == (*sa._action); } + /** + * Compares sort actions. + */ + bool operator<(const SortAction& sa) const{ + return (*_action) < (*sa._action); + } + /** * Compares sort actions. */ diff --git a/src/threadgenesorter.cpp b/src/threadgenesorter.cpp index a45988c..2276a2f 100644 --- a/src/threadgenesorter.cpp +++ b/src/threadgenesorter.cpp @@ -21,6 +21,9 @@ #include "threadgenesorter.h" #include "sortaction.h" +#include "genealgorithms.h" + +#include using namespace std; /** @@ -131,6 +134,7 @@ void ThreadGeneSorter::sorter(const GeneOrder& go){ } void ThreadGeneSorter::worker(){ + try{ while(!_done){ Mutex m(&_queuelock); @@ -146,6 +150,33 @@ void ThreadGeneSorter::worker(){ SortUnit su = _queue.top(); _queue.pop(); m.unlock(); + + size_t dist = inversionDistance(su._go); + if (dist == 0){ + Mutex m(&_solutionslock); + _solutions.push(pair(su._score,su._al)); + pthread_cond_broadcast(&_addedSolution); + continue;; + } + + ActionList act = safeActions(su._go); + if (act.size() > 0){ + set safe(act.begin(), act.end()); + for (set::iterator sa = safe.begin(); sa != safe.end(); ++sa){ + GeneOrder go(su._go); + ActionList al(su._al); + al.push_back(*sa); + (*sa)(go); + double score = su._score + _model.score(*sa,su._go); + Mutex m(&_queuelock); + _queue.push(SortUnit(score,go,al)); + } + pthread_cond_broadcast(&_addedTask); + } //TODO: Hurdles.. + + } + }catch(const bad_alloc& e){ + _done = true; } } -- 2.39.2