多线程进行n皇后计算

在浏览zhihu的时候, 看到了这个问题:Linux c++服务器端这条线怎么走? http://www.zhihu.com/question/22608820 , 其中排第一的答案说的很不错。针对他结尾处给出的问题,一直想自己做一下,最近工作不忙,也写了以下,还是发现了一些自己存在的问题,总结一下吧。

一个简单的8皇后问题可以比较容易的实现

多线程进行n皇后计算
#include <string.h>
#include <iostream>
#include <stdlib.h>

int cntTotal = 0;
int BOARDSIZE=11;
bool markboard(bool* b, int row, int col){
    for(int i =row;i<BOARDSIZE;++i){
        *(b+i*BOARDSIZE+col) = true;
    }
    for (int i=row+1, j=col-1 ; i<BOARDSIZE && j>=0; ++i, --j)
        *(b+i*BOARDSIZE+j)=true;
    for(int i = row+1, j=col+1; i<BOARDSIZE && j<BOARDSIZE; ++i, ++j)
        *(b+i*BOARDSIZE+j)=true;

    return true;
}
bool IsQuerePos(bool* board, int idx){

    bool *b = new bool[BOARDSIZE*BOARDSIZE];
    for(int i = 0;i<BOARDSIZE; ++i){
        if(*(board+idx*BOARDSIZE+i) )
            continue;
        if(idx == BOARDSIZE-1){
            cntTotal ++;
            std::cout<<cntTotal<<"\r";
        }
        else{
            memcpy(b, board, sizeof(bool)* BOARDSIZE*BOARDSIZE);
        
            markboard(b, idx, i);
              IsQuerePos(b, idx+1);
        }
    }
    delete b;
}

int main(int argc, char** argv){
    if(argc ==2)
        BOARDSIZE = atoi(argv[1]);
    std::cout<< argc << std::endl;
    bool *board = new bool[BOARDSIZE*BOARDSIZE];
    bool *p = board;
    for(int i = 0; i<BOARDSIZE; i++){
        for(int j=0; j<BOARDSIZE;j++)
            *p++ = false;
    }
    IsQuerePos(board, 0);    
    std::cout<<cntTotal<<std::endl;
    delete board;
}
多线程进行n皇后计算

运行起来是没有任何问题的。然后就是想办法改成多线程的版本。对于多线程版本,最容易的方案就是从第一行开始,每个线程计算不同的列,也就是将n皇后问题,分成n个子任务,这样每个子任务互不影响,可以进行并行计算。这样子的算法是我们人为的来进行子任务的分解,简单,线程之间不需要同步,易于实现。更复杂的算法是由算法智能调度各线程的负载,我没学过并行计算,复杂的就不研究了,实现简单的就行了。

核心代码如下:

多线程进行n皇后计算
class ThreadMgr{
public:
  ThreadMgr(int boardSize, int threadCount): m_board_size(boardSize), m_thread_count(threadCount){    
  }

  void Start(){
    m_threads = new Thread*[m_thread_count];
    for (int i = 0;i<m_thread_count; ++i)
    {
      m_threads[i] = new Thread();
      m_threads[i]->Start();
    }
    {
     // PerformanceHelper ph("internal-");
      QueueEight** qes = new QueueEight*[m_board_size];
      int cnt = 0;
      for(int i=0;i<m_board_size; ++i){
        qes[i] = new QueueEight(m_board_size);
        m_threads[i%m_thread_count]->PostJob(new CJob2<QueueEight, int, int>(qes[i], &QueueEight::PlaceQueueOnPos, 0, i));
        //qes[i]->PlaceQueueOnPosInternal(0, i, cnt);
      }    

      for (int i = 0;i<m_thread_count; ++i)
      {      
        m_threads[i]->Finish();
      }
    }
    
    std::cout<< QueueEightDelegate::getCnt() <<std::endl;

  }

private:
  int m_thread_count;
  Thread** m_threads;
  int m_board_size;
};
多线程进行n皇后计算

其中Thread是我封装的一个线程类,参照chrome的线程模型;CJob2对应了chrome的task,就是一个独立的任务,可以交给线程Thread来执行;为了线程之间的数据独立,定义了一个QueueEight的类来完成n皇后的计算,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class QueueEight{
public:
    QueueEight():m_board(NULL), m_board_size(8){ }
 
    QueueEight(int size):m_board_size(size){
        m_board = new bool[m_board_size*m_board_size];
        for( int i =0;i<m_board_size; ++i){
            for(int j=0; j<m_board_size; ++j){
                m_board[i*m_board_size + j] = false;
            }
        }
    }
 
    QueueEight(const QueueEight* qe){
        m_board_size = qe->m_board_size;
        m_board = new bool[m_board_size*m_board_size];
        memcpy(m_board, qe->m_board, sizeof(bool)* m_board_size*m_board_size);
    }
 
  ~QueueEight(){
    delete[] m_board;
  }
 
    void PlaceQueueOnPos(int row, int col){
      int cnt =0;
      {    
        //PerformanceHelper ph("abc");
        PlaceQueueOnPosInternal(row, col, cnt);
      }
      QueueEightDelegate::OnCalcComplete(cnt);
    }
 
    int PlaceQueueOnPosInternal(int row, int col, int& cnt){
      if(row == m_board_size-1){
        cnt ++;
      }
      else{
        *(m_board+row*m_board_size+col) = true;             
        QueueEight qe(this);               
        qe.markboard(row, col);
        for (int i = 0;i<m_board_size;++i)
        {         
          if (qe.QueueExist(row+1, i))
            continue;
          qe.PlaceQueueOnPosInternal(row+1, i, cnt);
        }
        *(m_board+row*m_board_size+col) = false;             
      }
      return cnt;
    }
 
    bool inline QueueExist(int row, int col){
      return *(m_board + row*m_board_size + col);
    }
 
private:
    bool markboard( int row, int col){
        for(int i =row;i<m_board_size;++i){
            *(m_board+i*m_board_size+col) = true;
        }
        for (int i=row+1, j=col-1 ; i<m_board_size && j>=0; ++i, --j)
            *(m_board+i*m_board_size+j)=true;
        for(int i = row+1, j=col+1; i<m_board_size && j<m_board_size; ++i, ++j)
            *(m_board+i*m_board_size+j)=true;
        return true;
    }
 
private:
    bool* m_board;
    int m_board_size;
};

这个类实现n 皇后的递归回朔算法,为了回朔方便,计算下一层的时候,重新new 一个QueueEight 对象,撤销时直接delete就行了。一看没有问题吧,然后计算结果也是正确的,但是运行时发现了一个问题,我用1个线程和4个线程来运行时,总时间上并没有什么差别,我的机器是i7 的8核,所以4个线程不会有大问题,那么问题哪儿呢? 

查了一些资料感觉找不出问题,所以借助于工具吧。vs2010带的performance profile工具,可以帮我们看看线程运行时的状态:多线程进行n皇后计算

通过这个,就可以收集线程运行的一些性能信息,通过分析发现,在new 新的 QueueEight对象时,会触发到默认堆的锁,而多线程同时new时,冲突会加剧,导致delay。突然想起以前接触tcmalloc时,核心思想就是线程分配 小对象时,从线程的私有内存分配,避免不同的线程共享堆而导致的加锁现象。问题找到了后,开始优化,将QueueEight的算法改一下。一开始就申请n个board区域,分别存储不同的行位置时queue的位置,方便回朔。这样在递归时就不需要分配内存了。实现代码如下:

多线程进行n皇后计算
class QueueEight{
public:
    QueueEight():m_board(NULL), m_board_size(8){ }

    QueueEight(int size):m_board_size(size){
        m_board = new bool*[m_board_size];
        for (int i =0;i<m_board_size;++i)
        {
            m_board[i] = new bool[m_board_size*m_board_size];
        }        
        
        for( int i =0;i<m_board_size; ++i){
            for(int j=0; j<m_board_size; ++j){
                m_board[0][i*m_board_size + j] = false;
            }
        }
    }

  ~QueueEight(){
      for (int i =0;i<m_board_size;++i)
      {
          delete[] m_board[i];
      }        
    delete[] m_board;
  }

    void PlaceQueueOnPos(int row, int col){
      int cnt =0;
      {     
        PerformanceHelper ph("abc");
        PlaceQueueOnPosInternal(row, col, cnt);
      }
      QueueEightDelegate::OnCalcComplete(cnt);
    }

    int PlaceQueueOnPosInternal(int row, int col, int& cnt){
      if(row == m_board_size-1){
        cnt ++;
      }
      else{
        *(m_board[row]+row*m_board_size+col) = true;              
        
        memcpy(m_board[row+1], m_board[row], sizeof(bool)*m_board_size*m_board_size);
        markboard(m_board[row+1], row, col);
        for (int i = 0;i<m_board_size;++i)
        {          
          if (QueueExist(m_board[row+1], row+1, i))
            continue;
          PlaceQueueOnPosInternal(row+1, i, cnt);
        }
        *(m_board[row]+row*m_board_size+col) = false;              
      }
      return cnt;
    }

    bool inline QueueExist(bool* board, int row, int col){
      return *(board + row*m_board_size + col);
    }

    
private:
    bool markboard(bool*board,  int row, int col){
        for(int i =row;i<m_board_size;++i){
            *(board+i*m_board_size+col) = true;
        }
        for (int i=row+1, j=col-1 ; i<m_board_size && j>=0; ++i, --j)
            *(board+i*m_board_size+j)=true;
        for(int i = row+1, j=col+1; i<m_board_size && j<m_board_size; ++i, ++j)
            *(board+i*m_board_size+j)=true;
        return true;
    }

private:
    bool** m_board;
    int m_board_size;
};
多线程进行n皇后计算

运行后,发现能够缩短总的运行时间。 15 皇后 4线程 运行3s, 15皇后 1线程 运行10s

其实我门还可以在进行优化,以位图来存储,而不用bool存储,也可以进行调度算法的设计和优化,但是线程之间如果同步的需求增多时,那么性能也会下降,这个我不太懂,可能要学习后才能搞搞。

通过这个问题,学习了一下多线程的性能分析,学会了用vs2010怎么分析程序的性能;对多线程的同步有了更深的理解;对多线程处理时数据的隔离也有了了解,所以

mark以下.

多线程进行n皇后计算,布布扣,bubuko.com

多线程进行n皇后计算

上一篇:记录一下c++的一点指针所得


下一篇:Java函数式编程(九)MapReduce