在排序数组中寻找特定数字 —— 人脑 vs 计算机 round 1我们通过一个具体的例子来说明人脑和计算机的思维方式不同假设我们想要从一个已经排好序的数组中找出一个特定的数字。已知排序好的数组是1 2 3 5 7 13 34 67 90 127 308我们希望找到是否13这个数在数组内。人脑是如何去完成任务的呢人脑处理这样的问题几乎是“作弊”的我们可以一目十行我们在眼镜一扫视的情况下就发现了13所以如果我问自己我是如何找到13的我只能说我“看见”了。而计算机是如何来完成这个任务呢最简单也是最笨的算法就是从数组开始一个一个的读入数组我相信每个学习过编程基础的同学都可以写出类似下面的代码。boolean isNumInArray(int num, int[] array) { for (int i 0; i array.length; i) { if (array[i] num) { return true; } } return false; }计算机需要从数组的第一个元素开始一个一个的去查当前的数组的元素和13相比看看是不是相等。为了找出13这个数计算机要做6次循环操作而人几乎是瞬间就看到了答案。为何计算机解决问题的方式这么“笨”呢我们先得从计算机的工作原理说起。CPU的工作方式CPU作为计算机的最核心的部件也是算法的主要运载体。CPU并不会像人一样思考它只懂得一些基本的指令。每一个CPU都有其指令集指令集是存储在CPU内部对CPU运算进行指导和优化的硬程序。通俗一点说指令集就是CPU的所有思维方式。比如常见的指令集中都会有ADD指令这个指令可以将两个寄存器中的值相加并将存储到另一个寄存器中与此相对应的也会有SUB指令用于将两个寄存器值相减。如果你去查阅各种CPU指令集的手册会发现基本上都会包含基本的加减乘除指令以及向内存中存、取数据的指令。而常见的CPU指令集最多也就是几百条指令。也就是说CPU只会这几百个命令。而人脑相对于CPU有强大的记忆和联想能力比如你看到11就想到2看到红灯就会想到停下来看到门就知道去开门把手这些都是你不假思索可以立刻反映出来的东西。所以CPU会的东西指令比人少多了那CPU岂不是很笨没错CPU就是很笨但是CPU的优点也是人脑所无法比拟的虽然CPU只会干简单的事情几百种指令但是它可以在固定的时间指令执行时间内保证正确的运算出正确的结果。而人脑不可能保证在固定的时间内一定产生“同样”的思维结果。现代化的CPU工艺可以在一秒钟内执行百万次以上的指令而人脑的思维速度则比不上我们一个“念头”最短也需要零点零几秒的反应时间。综上所述CPU是一个既笨又快的家伙。计算机存储计算机的常见存储有寄存器、高速缓存、内存、硬盘等。寄存器就相当于人脑中立刻可以想起来的东西CPU所做的一切运算都是针对于在寄存器中的数据进行的。寄存器存储了计算机当前要做什么计算指令寄存器要计算的数据数据寄存器计算到哪一步了段寄存器等信息。无论是最早的有寄存器的CPU还是最新最强的的CPU它们的寄存器数量最多也只有几十个特殊情况有几百个也就是说CPU同一时刻能够立刻使用过的信息也就是这几十个数字。内存则是计算机的主力存储设施它可以存储运行中的程序的信息内存相当于图书馆的书架CPU需要用某一段内存中的数据是需要通过LOAD指令同时附上一个书架编号内存地址然后内存控制器可以将对应的地址的数据通过总线传输给CPUCPU则将载入的结果放入寄存器中使用。内存存取的速度远小于寄存器但是访问分布在内存各个区间的数据的速度基本是相等的。由于大部分时候CPU需要读取连续的一段内存来进行运算因此通常CPU会有高速缓存将最近使用过的内存整块缓存起来而使得CPU不必每执行一步就需要去读一次内存。高速缓存的速度介于寄存器和内存之间但远高于内存。高速缓存的大小一般在几兆到十几兆之间。硬盘属于外部存储老式的机械硬盘中会有一个可转的磁头在读取磁盘文件的时候需要将磁头转到对应的位置磁盘的速度远低于内存并且如果磁盘的磁头如果停留在某个位置时随机磁盘上不同位置的信息会受到磁头运动的物理速度限制而出现速度不均等的情况。新式的固态硬盘采用了和内存相似的存储介质在随机访问的性能上提升很大。所以计算机有一颗只能记得一点点事情的小脑袋寄存器但是能够拥有相对较大的快速记忆缓存拥有远超过人类的知识储备内存并且还随身携带了巨大的移动图书馆硬盘所以从存储上来看计算机像是一个有先天缺陷的雨人Rain Man。所以我们来分析一下round 1中为何计算机到底做了怎样的操作首先我们看我们函数的定义boolean isNumInArray(int num, int[] array)在调用函数的底层实现中参数是被分配到两个寄存器中。isNumInArray这个函数在被调用时第一个参数num的值13会被载入到寄存器r1 的第二个参数array传入CPU的时候就只是array在内存中的地址信息被存储在另一个寄存器r2。而在第四行array[i] num时CPU需要做三件事才可以完成这工作通过ADD指令根据array的地址r2和ir4的数字计算需要读取的内存地址通过LOAD指令将内存地址对应的数载入到寄存器r3通过CMP指令比较numr1和r3的值结果存储在结果存储器中而根据操作3的结果如果结果不相等则CPU需要将循环计数器i加上1存入寄存器r4再次进行上面的计算。所不同的是第二到第N次的步骤二会比第一次要快很多因为整个数组的内容已经被高速缓存所捕获。所以我们可以看出为何计算机在解决这个问题上显得如此愚笨计算机的输入收到限制。计算机一次只能读入单个值有高速缓存的帮助这并不太糟糕且在寄存器中放有限的几个值而人类可以通过视觉等一次性读入多个值存储在脑海中。计算机的指令有限制只能支持基本的运算指令。而人脑可以有丰富的指令比如直接通过一堆刚刚看到的数字中视觉模式匹配出13这个数字。在排序数组中寻找特定数字 —— 人脑 vs 计算机 round 2计算机在上一轮和人脑的PK中败下阵来然而这并不是很公平因为数组的数量只有短短的几个而计算机可以存储的上限远不止于如此。于是我们开始第二次的比拼。 这次我们将输入扩大1 2 3 5 7 13 34 67 90 127 308 502 ... 2341245 ... 100万个查找的数变成了2341245。这次人脑和计算机的表现又如何呢对于一个普通人我们假设这100万个数字是打印在一本字典里的那么他如何找出100万个有序数组中的某个数字呢这时人类引以自豪的“一目十行”的能力已经微乎其微当数字的位数增大时且不说一眼比较一个数字是否和目标数字相同已经困难即使真的有一目十行的本事在100万这样的数字面前也是微乎其微。于是乎我们老老实实的去从头到尾比较数字一页一页的翻开去看当前的页中有没有数字没有的话就去翻下一页。这个思路是不是很熟悉没错这就是计算机的思维和我们上一节中所描述的计算机编码几乎是一样的除了人可以一眼多看几个数据外。然而人类在比较大数是否相等的速度以及翻字典的速度可远远比不上计算机去读完这100万个数的速度同样是“笨鸟”计算机每秒百万次的运算能力几乎可以在瞬间就完成这样的任务。也就是说在大规模输入的情况下人脑的思维方式“退化”成和计算机近似但是被计算机压倒性的性能优势给击败。在排序数组中寻找特定数字 —— 人脑 vs 计算机 round 3在第二轮中人脑败给了计算机但这样的比拼无疑于两只笨鸟比谁更快。有没有聪明一些的方法呢没错我们学过二分查找Binary Search的算法可以派上用场了。步骤一有这么有一本打印了100万个数字的字典摆在我们的面前我们不知道要找的数字会在哪里那么我们先折半打开字典不用那么精确也没关系看当前页的第一个数字和最后一个数字我们要找的数字是否在这个范围内如果在那么我们可以继续在当前页找这个数字。步骤二如果当前页的第一个数字还是比我们要找的数字大那么我们可以将字典的后半部分撕了因为我们要找的数字不可能在后半部分了继续上面的步骤。步骤三如果当前页的最后一个数字比我们要找的数字小那么我们可以将字典的前半部分撕了理由同上继续步骤一。这样我们会讲这本字典越撕越薄最坏的情况下我们会撕到最后一页这一页要么有这个数字要么没有这个数字但是我们保证按照上面的步骤进行我们不会错过任何可能含有这个数字一页。这个逻辑和计算机算法中的二分查找原理是一样的我们来看看实际的算法代码是如何实现的boolean isNumInArray(int num, int[] array, int start, int end) { if(num arr[start] || key arr[end] || start end){ return false; } int middle (start end) / 2; //找到对折点 if(array[middle] num) { return isNumInArray(arr, key, start, middle - 1); //撕掉后一半 } else if(array[middle] num){ return isNumInArray(arr, key, middle 1, end); //撕掉前一半 }else { return middle; } }我们可以看出和人类的思维方式比计算机不会翻“一页”它只会翻看一个数字但是其他的思维方式是一模一样的。利用这样的算法人类虽然从结果上还是比计算机要慢但是双方都找到了最适合的方法达到自我效率的最大提升。在排序数组中寻找特定数字 —— 更多的思考那么我们回过头来看为什么我要假设这100万数字打印在字典上呢因为字典和计算机内存的模型很像。计算机可以通过内存地址来直接访问内存这一点和通过字典的页码来翻到某一页这一点是近似的。在计算机编码中我们可以知道数组的长度而通过折半的方法找到中间的数字典有厚度我们可以通过厚度减半来找到中间的页码这一点也是相似的。试想一样如果100万的数字不是打印在字典而是印在一条公路上我们是否还可以用上一节的算法来人肉二分查找答案是不可以因为跑到公路的一半会消耗你很多的体力如果采用二分法查找比起round 1中的最笨办法只会让你耗费更多的体力。因为公路这一存储的概念对应的便不是内存的模型而是磁带Tape的模型那么对于这样的模型我相信不论是人或者是计算机 都需要调整算法来达到最高的效率。总结