Basic implementation of threaded sorting

Assumes the caller calles join() to wait for all threads to end.

diff --git a/src/main.cpp b/src/main.cpp
index abd520f43a29f7a3ec9b4cb7cb8f893895f16cbc..85569e1c295dfa614245be5e6c759f534d1cd525 100644 (file)
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -3,6 +3,7 @@
 #include <queue>
 #include <iterator>
 #include <fstream>
+#include <cstdlib>
 
 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<int>(cout, " "));
-                       cout << endl;
+       if (threads){
+               ThreadGeneSorter so(model, threads);
+               so.start(go);
+               so.join();
+
+               ThreadGeneSorter::SolutionsQueue solutions = so.solutions();
+
+               while (solutions.size() > 0){
+                       pair<double,GeneSorter::ActionList> 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<int>(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 e0857803518b2d4aa5acaa72f0c7cfe89f41bf4f..267aeaa84bdc11cdec6dcadce0ecc114b4d10782 100644 (file)
--- 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<const ReverseAction*>(&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 a99f786988b88a9cb238fc77122fb6a14aa5d4f2..a1c5566acb16673368d5c3fc9260f9c68a055311 100644 (file)
--- 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 a45988c21dcc4a14f7717a9ef7b07d9757f81179..2276a2fdd271f05a04ae286831fb30ce9d0a20fc 100644 (file)
--- a/src/threadgenesorter.cpp
+++ b/src/threadgenesorter.cpp
@@ -21,6 +21,9 @@
 #include "threadgenesorter.h"
 #include "sortaction.h"
 
+#include "genealgorithms.h"
+
+#include <set>
 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<double,ActionList>(su._score,su._al));
+                       pthread_cond_broadcast(&_addedSolution);
+                       continue;;
+               }
+
+               ActionList act = safeActions(su._go);
+               if (act.size() > 0){
+                       set<SortAction> safe(act.begin(), act.end());
+                       for (set<SortAction>::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;
        }
 }