过桥问题

Posted by & filed under Uncategorized.

过桥问题: 问题描述:4个人在晚上过一座小桥,过桥时必须要用到手电筒,只有一枚手电筒,每次最多只可以有两人通过, 4个人的过桥速度分别为1分钟、2分钟、5分钟、10分钟,试问最少需要多长时间4人才可以全部通过小桥?   Morewindows的方法(以下参考blog: http://blog.csdn.net/MoreWindows/article/details/7481851) Morewindows君通过观察发现,要么是最快者将最慢的2个送过桥,要么是最快的2个将最慢的2个送过桥。即将过桥的人按其过桥的时间从小到大排列,设为A,B,…… Y,Z。其中A和B是最快的二个,Y和Z是最慢的二个。那么就有二种方案: 方案一 最快者将最慢的2个送过桥 第一步:A和Z过桥,花费Z分钟。 第二步:A回来,花费A分钟。 第三步:A和Y过桥,花费Y分钟。 第四步:A回来,花费A分钟。 这四步后总人数就减小2个,花费时间为A Read more […]

小白鼠问题

Posted by & filed under Uncategorized.

小白鼠问题 问题描述:有 1000 个一模一样的瓶子,其中有 999 瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。问,在一星期时间内,如何用最少的白鼠试验出有毒的那瓶?   错误解法: 1.只要一只白鼠,一瓶瓶喝过去,喝到哪瓶死了,哪瓶有毒。 注意到问题为一星期内最少老鼠,上述方法大概要500个星期。 2.二分法思想。还是犯了上面的问题,只限在一星期内,二分法收敛要logN的时间,也就是logN星期。   正确解法: 根据信息论的知识,1000瓶药水1瓶有毒,那么有1000种不同的情况;每个小老鼠有1死,0活,两种情况。如果有10只小老鼠,我们就能表示2^10=1024种情况,应该能表示1000种不同的药水情况。 于是我们用二进制编码的方法解决上面问题。 为了方便说明,下面举N=6的情况,不妨设4号瓶有毒。 依据上面的理论,我们应该可以用2^3=8,也就是3只小白鼠来表示6种情况,具体如下: 小白鼠:         Read more […]

区间最值与线段树

Posted by & filed under Uncategorized.

  区间最值问题: 有如下无序序列,求任意子区间段的最大值。 接下来,我们要用分治的思想来快速地解决上面的问题。在解决问题之前,先介绍一些分治的概念。   二分查找   二分查找是分治思想的典型运用 我们有如下序列: A1,A2,A3……An. 要查找其中等于b的元素。一种方法就是一个个对比,看看是不是相等,时间复杂度为N。还有就是二分查找。 如上图,通过不断地与中间元素对比,缩小搜索区间,最后得到A4==b.时间复杂度为logN.   二叉搜索树   在二分查找中,我们要求队列是有序地。那么如果队列无序又要如何?我们可以仿造二分查找的方式,构造一个二叉搜索树,如下: 二叉搜索树左节点比根小,右节点比根大。上图红色箭头代表搜索A4的过程。   线段树 线段树也是一种二叉搜索树,我们回到区间最值的问题,有如下无序序列 现在我们要在上面的序列中,搜索任意指定区间的最大值。   我们先来解决总的最大值的问题 一个基本的方法就是一个个比较,取出最大值,时间复杂度为N。 我们借用二分搜索的分治思想。可以把序列划分为1-5节点的最大值和6-8的最大值,再取这两个值的较大值。递归地,我们再把1-5继续划分至只剩一个元素。这样的时间复杂度为logN Read more […]

01背包问题

Posted by & filed under Uncategorized.

01背包问题。 问题描述:现有背包大小为W,有物品1,2,3.。。。N,大小分别为w1,w2,w3….wN,价值分别为p1,p2,p3….pN,求在背包容量下,能装的最大物品价值。   首先我们用最笨的方法,穷举法,N个物品的放入组合一共用2^N种,枚举出每种的价值,取其中大小和小于W的最大值,即为所求,如下:   设背包大小W为3,物品1:w1=1,p1=2;物品2:w2=2,p2=3;物品3:w3=3,p3=6; 那么我们的2^3=8种放入的方法分别为: 0 1 2 3 1+2 1+3 2+3 1+2+3 上诉8个组合方法中,1+3,2+3,1+2+3总大小大于背包大小,舍去,于是我们剩余5种方法: 0       权值为:0 1                          2 2                          Read more […]

两个list查找相同元素

Posted by & filed under Uncategorized.

问题是两个list,包含了上万的字符串元素,要快速查找重复元素。 相应的我们可以用map的方法,插入,遍历查找。 这里提出另外两个可行的方法,供参考;然后就这类问题进行一些扩展探讨。 (1)两个可行方法。 一个是基于哈希表+链表的查找,一个是26叉树。 A..哈希表+链表。 前面的blog提到了哈希表,就是用一个key值作为地址值,直接寻址。寻找速度为O(1). 具体到两个字符串的list问题,我们需要为每个字符串映射到一个整数,然后依次建立一个哈希表H[N]。比如“aabbc”这个字符串的key是102,对应的位置就为H[102]。这样的话,我们初始化H为0,遍历list_1,计算key,在H中对应的位置设为1。再遍历list_2,查看对应的H位置是0或1,0着没有重复,1就重复。 上面的问题一个关键的步骤就是如何建立一个映射“aabbc”到102。这方面前人有现成的研究成果,如下: 这个函数把每个字符串映射到一个0-500的整数key。   这样,我们有了“aabbc”对应的“102”,建立长度为500的哈希表。但是500个哈希数组,肯定会有地址冲突问题,一种普遍的解决方法就是哈希表+链表,如下: 也就是在哈希表后,如果地址冲突,就接上相同地址元素的链表。 到这里,哈希表+链表的方法就大功告成了。具体步骤总结如下: a.用映射函数计算list_1中各个字符串的key。 b.建立大小为500的哈希表H,初始化为0. c.遍历list_1,在H中的相应位置H[key]置1,如果有地址冲突,则起一个链表节点,接到后面。 d.用映射函数计算list_2的key,并在H中寻找是否重复。 然后,我们对这个算法进行分析: 这个算法的主要消耗在key值得计算,其他步骤时间复杂度都是O(1). B.接着说第二种方法,26叉树。 之所以想到26叉树,是由于每个字符串字母都是a-z(暂时忽略大小写),那么根据其特性,我们建立一个26叉树,一个母节点都有a-z26个子节点。 如下图所示: 上面是字符串“aabbc”的路径。每个字符串节点里存储其是否出现的信息。 那么我们的具体步骤可以归纳如下: a.根据list_1建立26叉树,建立方法为从空树开始,没有节点则建立,在尾节点里加上个数信息。 b.根据上面建立的26叉树,把list_2中的字符串逐个遍历这个树,得到是否重复信息。 性能分析: 这个算法其实想模仿map中的红黑2叉树,建立26叉树则是根据具体问题的特点改进,时间复杂度又原来的log2N减少到log26N。算是对map方法查找的一个改进。而且还省略了其比较的过程。不过如果长生了退化的26叉树,也有可能导致结果不理想。 (2)关于大数据的查找问题扩展探讨。 上面针对两个list查找相同元素问题,提出了两个方法。这里的list是以万为单位的,故可以再内存中进行如上的哪些算法。下面把问题扩展到上亿的数据,结果会怎样呢? 假设一个字符串20byte之内,那么两亿个字符串就是4*10^10byte~=40GB,远大于一般的内存。 我们首先想到的是把两个list分块,分别放入内存用上述方法计算。那么第一个问题是怎么分块? 一般的内存为2GB,那么一个list20GB要分为二十块。那么我们直接按顺序分块,分别作上面的计算,要计算20*20=400次。当然,这里假设一个list本身的字符串都是非重复的。 不过上面假设一亿个字符串都是非重复,貌似很难成立,那么便又引出一个问题,list中本就有重复元素。 ,那么分块方法首先要变,我们要把相同元素放到一个块。这里又要用到哈希表,把一亿个元素按照哈希表分块,保证重复元素被分到了一个大块中,接着再进行上述的计算便可以了。哈希表分块如下: 总结:上述只是查找相同元素的一个方法,还有许多诸如大数据前K大数等问题,大数据操作中常常用到哈希表和分块计算的方法。 Read more […]

线程堆栈

Posted by & filed under Uncategorized.

线程堆栈大小http://blog.csdn.net/nokianasty/article/details/7600321 C++内存分布http://blog.csdn.net/morewindows/article/details/6851681 线程堆栈分布http://bbs.csdn.net/topics/390391357 在看了这三篇的讨论后,对于线程堆栈,内存分布等有了一点了解,以上引出几篇文章,再做一些自己的总结: 首先,引出这方面问题是因为多线程编程中,过多的线程导致存储不足的情况,猜测占用了许多空闲的内存,于是探究一些解决方法。 1).线程分为内核态与用户态。 首先是内核,指的是操作系统中最基础的一些部分,提供一些分装的结构,方法,对外部限制访问权限。即对于用户是一个只知道接口,不知道内部的结构。 内核态线程,即对内核可见线程,有比较小的数据堆栈,易于调度,调度依赖于操作系统,一个线程阻塞,操作系统依据自己的策略调度其他可用线程,实现线程的并发。 用户态线程,对于内核不可加,一个线程阻塞时,如果用户不手动调度,整个进程都会阻塞。 由于在项目中用CreateThread创建的线程已经是内核态的线程,故这里没有改进。   2).存储变量分为五个区,堆,栈,自由区,全局/静态区,常量区 摘自以上某篇文章的示意图如下: 其中new Read more […]

初识多线程编程

Posted by & filed under Uncategorized.

刚刚开始接触多线程编程,遇到一些难题,走了许多弯路,在此做一个简短的小结。 1.为什么要引入多线程,个人总结以下两点 a.线程共享进程的地址空间,提高了物理空间的重复利用率 b.时域复用CPU的运算时间,提高计算时间的利用率 2.多线程的高效率也带来了许多复杂的线程同步,互斥等问题。 a.互斥,操作共享资源时的互不干扰 b.同步,运行按照一定的顺序进行 c.异步,参考消费者生产者模型 解决这些问题是,接触到了如下几种解决方式: a.关键段CS 开始在理解关键段的时候有一些错误认识,比如认为关键段是原操作,后来参考关键段的硬件操作细节,得知不是如此,而可以理解为线程的代码段所有权,即所标示代码段其他线程暂时不能贡献。解决互斥问题。 关键段CRITICAL_SECTION一共就四个函数,使用很是方便。下面是这四个函数的原型和使用说明。 函数功能:初始化 函数原型: void InitializeCriticalSection(LPCRITICAL_SECTIONlpCriticalSection); 函数说明:定义关键段变量后必须先初始化。 函数功能:销毁 函数原型: void DeleteCriticalSection(LPCRITICAL_SECTIONlpCriticalSection); 函数说明:用完之后记得销毁。 函数功能:进入关键区域 函数原型: void EnterCriticalSection(LPCRITICAL_SECTIONlpCriticalSection); 函数说明:系统保证各线程互斥的进入关键区域。 函数功能:离开关关键区域 函数原型: void LeaveCriticalSection(LPCRITICAL_SECTIONlpCriticalSection); b.事件EVENT 触发和等待一个事件,用于处理同步问题 事件Event实际上是个内核对象,它的使用非常方便。下面列出一些常用的函数。 第一个 CreateEvent 函数功能:创建事件 函数原型: HANDLECreateEvent(  LPSECURITY_ATTRIBUTESlpEventAttributes,  BOOLbManualReset,  BOOLbInitialState,  LPCTSTRlpName ); 函数说明: 第一个参数表示安全控制,一般直接传入NULL。 第二个参数确定事件是手动置位还是自动置位,传入TRUE表示手动置位,传入FALSE表示自动置位。如果为自动置位,则对该事件调用WaitForSingleObject()后会自动调用ResetEvent()使事件变成未触发状态。打个小小比方,手动置位事件相当于教室门,教室门一旦打开(被触发),所以有人都可以进入直到老师去关上教室门(事件变成未触发)。自动置位事件就相当于医院里拍X光的房间门,门打开后只能进入一个人,这个人进去后会将门关上,其它人不能进入除非门重新被打开(事件重新被触发)。 第三个参数表示事件的初始状态,传入TRUR表示已触发。 第四个参数表示事件的名称,传入NULL表示匿名事件。 第二个 OpenEvent 函数功能:根据名称获得一个事件句柄。 函数原型: HANDLEOpenEvent(  DWORDdwDesiredAccess,  BOOLbInheritHandle,  LPCTSTRlpName     //名称 ); 函数说明: 第一个参数表示访问权限,对事件一般传入EVENT_ALL_ACCESS。详细解释可以查看MSDN文档。 第二个参数表示事件句柄继承性,一般传入TRUE即可。 第三个参数表示名称,不同进程中的各线程可以通过名称来确保它们访问同一个事件。 第三个SetEvent 函数功能:触发事件 函数原型:BOOLSetEvent(HANDLEhEvent); 函数说明:每次触发后,必有一个或多个处于等待状态下的线程变成可调度状态。 第四个ResetEvent 函数功能:将事件设为末触发 函数原型:BOOLResetEvent(HANDLEhEvent); 最后一个事件的清理与销毁 由于事件是内核对象,因此使用CloseHandle()就可以完成清理与销毁了。 c.互斥量MUTEX 全局唯一表示,解决互斥问题 互斥量也是一个内核对象,它用来确保一个线程独占一个资源的访问。互斥量与关键段的行为非常相似,并且互斥量可以用于不同进程中的线程互斥访问资源。使用互斥量Mutex主要将用到四个函数。下面是这些函数的原型和使用说明。 第一个 CreateMutex 函数功能:创建互斥量(注意与事件Event的创建函数对比) 函数原型: HANDLECreateMutex(   LPSECURITY_ATTRIBUTESlpMutexAttributes,   BOOLbInitialOwner,   LPCTSTRlpName ); 函数说明: 第一个参数表示安全控制,一般直接传入NULL。 第二个参数用来确定互斥量的初始拥有者。如果传入TRUE表示互斥量对象内部会记录创建它的线程的线程ID号并将递归计数设置为1,由于该线程ID非零,所以互斥量处于未触发状态。如果传入FALSE,那么互斥量对象内部的线程ID号将设置为NULL,递归计数设置为0,这意味互斥量不为任何线程占用,处于触发状态。 第三个参数用来设置互斥量的名称,在多个进程中的线程就是通过名称来确保它们访问的是同一个互斥量。 函数访问值: 成功返回一个表示互斥量的句柄,失败返回NULL。 第二个打开互斥量 函数原型: HANDLEOpenMutex(  DWORDdwDesiredAccess,  BOOLbInheritHandle,  LPCTSTRlpName     //名称 ); 函数说明: 第一个参数表示访问权限,对互斥量一般传入MUTEX_ALL_ACCESS。详细解释可以查看MSDN文档。 第二个参数表示互斥量句柄继承性,一般传入TRUE即可。 第三个参数表示名称。某一个进程中的线程创建互斥量后,其它进程中的线程就可以通过这个函数来找到这个互斥量。 函数访问值: 成功返回一个表示互斥量的句柄,失败返回NULL。 第三个触发互斥量 函数原型: BOOLReleaseMutex (HANDLEhMutex) 函数说明: 访问互斥资源前应该要调用等待函数,结束访问时就要调用ReleaseMutex()来表示自己已经结束访问,其它线程可以开始访问了。 最后一个清理互斥量 由于互斥量是内核对象,因此使用CloseHandle()就可以(这一点所有内核对象都一样)。 d.信号量 解决异步问题 信号量Semaphore常用有三个函数,使用很方便。下面是这几个函数的原型和使用说明。 第一个 CreateSemaphore 函数功能:创建信号量 函数原型: HANDLE CreateSemaphore(   LPSECURITY_ATTRIBUTES lpSemaphoreAttributes,   LONG lInitialCount,   LONG lMaximumCount,   LPCTSTR lpName ); 函数说明: 第一个参数表示安全控制,一般直接传入NULL。 第二个参数表示初始资源数量。 第三个参数表示最大并发数量。 第四个参数表示信号量的名称,传入NULL表示匿名信号量。 第二个 OpenSemaphore 函数功能:打开信号量 函数原型: HANDLE OpenSemaphore(   DWORD dwDesiredAccess,   BOOL bInheritHandle,   LPCTSTR lpName ); 函数说明: 第一个参数表示访问权限,对一般传入SEMAPHORE_ALL_ACCESS。详细解释可以查看MSDN文档。 第二个参数表示信号量句柄继承性,一般传入TRUE即可。 第三个参数表示名称,不同进程中的各线程可以通过名称来确保它们访问同一个信号量。 第三个 ReleaseSemaphore 函数功能:递增信号量的当前资源计数 函数原型: BOOL ReleaseSemaphore(   HANDLE hSemaphore,   LONG lReleaseCount,   LPLONG lpPreviousCount ); 函数说明: 第一个参数是信号量的句柄。 第二个参数表示增加个数,必须大于0且不超过最大资源数量。 第三个参数可以用来传出先前的资源计数,设为NULL表示不需要传出。 在对信号量调用等待函数时,等待函数会检查信号量的当前资源计数,如果大于0(即信号量处于触发状态),减1后返回让调用线程继续执行。一个线程可以多次调用等待函数来减小信号量。 最后一个 Read more […]

关于map

Posted by & filed under Uncategorized.

map的定义:Map提供一对一<key,value>的数据处理能力,在我们处理一对一数据的时候,在编程上提供快速通道。 实现关键:快速查找的问题,即根据所给的key,在内存中找到其对应的value. 在具体讨论前引入查找速度的评价指标:渐进时间复杂度,表示为O(); 由于程序的具体执行时间难以准确估计,引入渐进时间复杂度这个概念,如下面的程序: for(int i=0;i<N;i++) { a++;b++; }c++; 程序主要部分一共执行了2*N+1次,取其幂,得起渐进时间复杂度为O(N); 同理,以下程序 for(int i=0;i<N;i++) for(int j=0;j<N;j++) a++; 主要部分执行了N*N次,渐进时间复杂度就为O(N^2); 渐进时间复杂度的大小比较为: O(1)<O(logN)<O(N)<O(N*logN)<O(N^2)<O(N^3); 接着我们来讨论快速查找的几个算法: 1)我们首先用数组来存储map,接着讨论如何在数组的前提下进行查找: 1。数组为无序的,我们最直观的方法便是一个个查看过去,确认是否是我们要找的东西,不是则查看下一个,是则结束查找。 渐进时间复杂度为O(N); 2。数组为有序的,可以有二分查找,斐波那契查找等,其基本的思想是相同的,我们以二分查找为例,每次对比数组的中位数,查找数大于中位数,则在后一半数组中继续,否则在前一半查找,直到数组大小为1时,判断是否为所要找的元素。 渐进时间复杂度可以估算为O(logN);<O(N); 不过这里假设的前提是数组有序,而最快的排序快速排序法的时间复杂度为O(N*logN)〉O(N);所以如果在一个无序的数组里先排序,再二分的话,速度还不如直接查找。 2。hash表,也叫散列表 hash数组即以一个hash函数,为每个value计算一个唯一的地址值,查找只要通过计算hash函数,就能直接找到所在地址。 一个简单的hash数组如下: <key,value><3,value1><6,value2><9,value3><12,value4> 观察到每个key都是3的倍数,而且没有重复,我们定义一个hash函数f int Read more […]