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

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

#include <string.h>
#include <iostream>
#include <stdlib.h> int cntTotal = ;
int BOARDSIZE=;
bool markboard(bool* b, int row, int col){
for(int i =row;i<BOARDSIZE;++i){
*(b+i*BOARDSIZE+col) = true;
}
for (int i=row+, j=col- ; i<BOARDSIZE && j>=; ++i, --j)
*(b+i*BOARDSIZE+j)=true;
for(int i = row+, j=col+; 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 = ;i<BOARDSIZE; ++i){
if(*(board+idx*BOARDSIZE+i) )
continue;
if(idx == BOARDSIZE-){
cntTotal ++;
std::cout<<cntTotal<<"\r";
}
else{
memcpy(b, board, sizeof(bool)* BOARDSIZE*BOARDSIZE); markboard(b, idx, i);
IsQuerePos(b, idx+);
}
}
delete b;
} int main(int argc, char** argv){
if(argc ==)
BOARDSIZE = atoi(argv[]);
std::cout<< argc << std::endl;
bool *board = new bool[BOARDSIZE*BOARDSIZE];
bool *p = board;
for(int i = ; i<BOARDSIZE; i++){
for(int j=; j<BOARDSIZE;j++)
*p++ = false;
}
IsQuerePos(board, );
std::cout<<cntTotal<<std::endl;
delete board;
}

运行起来是没有任何问题的。然后就是想办法改成多线程的版本。对于多线程版本,最容易的方案就是从第一行开始,每个线程计算不同的列,也就是将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 = ;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 = ;
for(int i=;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, , i));
//qes[i]->PlaceQueueOnPosInternal(0, i, cnt);
} for (int i = ;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;
};

其中Thread是我封装的一个线程类,参照chrome的线程模型;CJob2对应了chrome的task,就是一个独立的任务,可以交给线程Thread来执行;为了线程之间的数据独立,定义了一个QueueEight的类来完成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*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工具,可以帮我们看看线程运行时的状态:

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

class QueueEight{
public:
QueueEight():m_board(NULL), m_board_size(){ } QueueEight(int size):m_board_size(size){
m_board = new bool*[m_board_size];
for (int i =;i<m_board_size;++i)
{
m_board[i] = new bool[m_board_size*m_board_size];
} for( int i =;i<m_board_size; ++i){
for(int j=; j<m_board_size; ++j){
m_board[][i*m_board_size + j] = false;
}
}
} ~QueueEight(){
for (int i =;i<m_board_size;++i)
{
delete[] m_board[i];
}
delete[] m_board;
} void PlaceQueueOnPos(int row, int col){
int cnt =;
{
PerformanceHelper ph("abc");
PlaceQueueOnPosInternal(row, col, cnt);
}
QueueEightDelegate::OnCalcComplete(cnt);
} int PlaceQueueOnPosInternal(int row, int col, int& cnt){
if(row == m_board_size-){
cnt ++;
}
else{
*(m_board[row]+row*m_board_size+col) = true; memcpy(m_board[row+], m_board[row], sizeof(bool)*m_board_size*m_board_size);
markboard(m_board[row+], row, col);
for (int i = ;i<m_board_size;++i)
{
if (QueueExist(m_board[row+], row+, i))
continue;
PlaceQueueOnPosInternal(row+, 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+, j=col- ; i<m_board_size && j>=; ++i, --j)
*(board+i*m_board_size+j)=true;
for(int i = row+, j=col+; 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;
};

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

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

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

mark以下.

多线程进行n皇后计算的更多相关文章

  1. 8皇后以及N皇后算法探究,回溯算法的JAVA实现,非递归,循环控制及其优化

    上两篇博客 8皇后以及N皇后算法探究,回溯算法的JAVA实现,递归方案 8皇后以及N皇后算法探究,回溯算法的JAVA实现,非递归,数据结构“栈”实现 研究了递归方法实现回溯,解决N皇后问题,下面我们来 ...

  2. 海量数据相似度计算之simhash短文本查找

    在前一篇文章 <海量数据相似度计算之simhash和海明距离> 介绍了simhash的原理,大家应该感觉到了算法的魅力.但是随着业务的增长 simhash的数据也会暴增,如果一天100w, ...

  3. WPF多线程UI更新——两种方法

    WPF多线程UI更新——两种方法 前言 在WPF中,在使用多线程在后台进行计算限制的异步操作的时候,如果在后台线程中对UI进行了修改,则会出现一个错误:(调用线程无法访问此对象,因为另一个线程拥有该对 ...

  4. 有一个很大的整数list,需要求这个list中所有整数的和,写一个可以充分利用多核CPU的代码,来计算结果(转)

    引用 前几天在网上看到一个淘宝的面试题:有一个很大的整数list,需要求这个list中所有整数的和,写一个可以充分利用多核CPU的代码,来计算结果.一:分析题目 从题中可以看到“很大的List”以及“ ...

  5. 多线程/多进程/异步IO

    SOCK_STREAM :TCPSOCK_Dgram :UDP family=AF_INET: 服务器之间的通信AF_INET6: 服务器之间的通信AF_UNIX: Unix不同进程间的通信 永远遵循 ...

  6. python 多进程和多线程

    在计算大量数据时,可以使用多进程 多线程机制来加速计算 多进程 import multiprocessing import os def run_proc(name): print('Child pr ...

  7. WPF多线程UI更新

    前言 在WPF中,在使用多线程在后台进行计算限制的异步操作的时候,如果在后台线程中对UI进行了修改,则会出现一个错误:(调用线程无法访问此对象,因为另一个线程拥有该对象.)这是很常见的一个错误,一不小 ...

  8. 并发编程~~~多线程~~~守护线程, 互斥锁, 死锁现象与递归锁, 信号量 (Semaphore), GIL全局解释器锁

    一 守护线程 from threading import Thread import time def foo(): print(123) time.sleep(1) print('end123') ...

  9. Python多进程和多线程是鸡肋嘛?【转】

    GIL是什么 Python的代码执行由 Python虚拟机(也叫解释器主循环,CPython版本)来控制,Python在设计之初就考虑到在解释器的主循环中,同时只有一个线程在运行.即每个CPU在任意时 ...

随机推荐

  1. 在 WCF 中使用高效的 BinaryFormatter 序列化

    本文将定义一个 WCF 终结点行为扩展,以在 WCF 中使用更高效的 BinaryFormatter 进行二进制序列化,并实现对是否使用传统二进制序列化功能的可配置. 介绍 实现步骤 使用方法 效果 ...

  2. 一起来做chrome扩展《本地存储localStorage》

    chrome中的本地存储其实也是用的HTML5中localStorage,唯一区别是chrome扩展有自己的localStorage,它属于这个扩展,而不属于一个域名.得用这一点可以很好的处理扩展自己 ...

  3. hibernate关联映射学习

  4. searchableselect不支持onchange的问题

    1.找到jquery.searchableSelect.js 2.找到selectItem函数 修改里面的方法,加入自定义你要回调的函数 selectItem: function(item){ //L ...

  5. fork函数

    在Unix/Linux中用fork函数创建一个新的进程.进程是由当前已有进程调用fork函数创建,分叉的进程叫子进程,创建者叫父进程.该函数的特点是调用一次,返回两次,一次是在父进程,一次是在子进程. ...

  6. MS CRM 2011的自定义和开发(11)——插件(plugin)开发(四)

    http://www.cnblogs.com/StoneGarden/archive/2012/02/08/2343294.html MS CRM 2011的自定义和开发(11)——插件(plugin ...

  7. C#开源资源大汇总

    C#开源资源大汇总     C#开源资源大汇总 一.AOP框架        Encase 是C#编写开发的为.NET平台提供的AOP框架.Encase 独特的提供了把方面(aspects)部署到运行 ...

  8. Redis的配置

    Redis是一个强大的Key-Value存储系统,在前面我们已遇到了两个问题: 1.redis server 启动后,独占进程,能不能修改为后台服务呢? 2.redis server 服务是单线程的, ...

  9. poj 3230 Travel(dp)

    Description One traveler travels among cities. He has to pay for this while he can get some incomes. ...

  10. SGU 101.Domino( 欧拉路径 )

    求欧拉路径...直接dfs即可,时间复杂度O(N) -------------------------------------------------------------------------- ...