forked from GHScan/TechNotes
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path3.html
45 lines (44 loc) · 113 KB
/
3.html
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
<head>
<meta http-equiv=Content-Type content="text/html; charset=utf-8">
</head>
<div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="ennote">
1. nc。netcat，这个工具可以用作tcp/udp客户端/服务器，因此它比更telnet更适合作为调试工具，毕竟telnet其实是个telnet协议的客户端
<div><br>
</div><div>1. CSAPP lab: proxy lab</div><div><br>
</div><div>1. 注意用pthread_attr_setstacksize来减少线程的内存占用</div><div><br>
</div><div>1. C++ project: readerwriterlock，由于writer、writer、readers三者互斥，但是reader、reader之间可以并发，所以如果用mutex，总时间是writers+readers，那改用readerwriterlock，总时间是writers+readers/reader_count。readerwriterlock的特点:</div><div><ul><li>lockread/unlockread之间的临界区: 此时绝不会有writer在访问资源，但是可能有多个reader在访问资源。故，读绝对安全，哪怕是复杂结构如std::map的读操作，但是写绝对危险(因为多个reader在访问)，要提防mutable的结构的读操作</li><li>lockwriter/unlockwrite之间的临界区: 除了此writer之外，没有任何其他的reader/writer在访问资源，同mutex语义一样</li></ul></div><div>1. unix网络编程中提到的5种并发IO模型:</div><div><ul><li>blocking IO</li><li>non-blocking IO，指不阻塞，但反复轮询尝试recvfrom(UDP例子)</li><li>IO multiplexing，比如select/poll，特点是一次处理多个文件</li><li>signal drived IO，注册signal，然后在可以内核准备好IO后(要读的数据已经到内核缓冲并且超过了TCP buf的水位，或者写缓冲有空间)，通过signal handler通知用户，然后在handler内部去进行recvfrom</li><li>异步IO，指调用异步IO函数，然后内核缓冲中数据就绪并进一步拷贝到用户buf后通知用户</li></ul><div>1. unix网络编程中提到的继承并发服务器模型:</div></div><div><ul><li>多进程</li><li style="list-style: none; display: inline"><ul><li>进程池: 一开始fork多个进程，每个都accept。这里的accept视OS支持情况，可能需要加跨进程的锁</li><li>进程池: fork多个进程，父进程accept，然后将conn描述符交给子进程(怎么实现的?)</li></ul></li><li>IO multiplexing</li><li>多线程</li><li style="list-style: none; display: inline"><ul><li>线程池: 每个线程带锁的accept</li><li>线程池: 主线程accept，其他处理connfd</li></ul></li></ul><div>1. select, poll都可以用于实现高精度的sleep</div></div><div><br>
</div><div>2. unix网络编程, TCP</div><div><ul><li>状态迁移: 书的35页，很精彩</li><li style="list-style: none; display: inline"><ul><li>建立连接: (1)SYN i (2) ACK (i+1), SYN j (3) ACK (j+1)。可见ACK的号是接收方下一个应该受到的号</li><li>断开连接: (1)FIN i (2) ACK (i+1), FIN j (3) ACK (j+1)</li></ul></li><li>面向连接的，双工的，可靠的</li><li>面向连接: 对传输层以上来说，最小read/write单元是字节；而UDP是报文包</li><li>双工的: 可单独shutdown某端；默认情况下，close立即返回，如果发送缓冲还有数据，则发送完毕后才发送FIN，使用SO_LINGER选项调用setsockopt可修改这行为</li><li>可靠的: (UDP都没有，需要在应用层模拟)</li><li style="list-style: none; display: inline"><ul><li>接收:</li><li style="list-style: none; display: inline"><ul><li>SYN的时候会沟通双方接收缓冲大小。通信过程中，双方会一直沟通接收缓冲剩余大小，如果应用层一直不read，那么接收缓冲可能为0，于是对端不再发送数据，这叫流量控制(flow control)</li><li>接收到的包会按序号重组顺序，避免网络乱序</li><li>去掉序号重复的包</li><li>SO_RCVBUF选项配置</li></ul></li><li>发送:</li><li style="list-style: none; display: inline"><ul><li>发送缓冲按照接收端的MSS(maximum segment size, SYN的时候协商这个值，很多时候等于MTU)来组织，只有当最左端的包收到了ACK，才向右移动窗口；如果左端包超时，则重发；如果多次超时，则失败。接收端可用接收缓冲变小可能导致发送端的窗口收缩</li><li>SO_SNDBUF选项配置</li></ul></li></ul></li></ul><div>2. unix网络编程:</div></div><div><ul><li>相比read、write这样的通用IO函数，recv、send提供了额外的控制选项，比如MSG_DONTWAIT(本次操作nonblocking), MSG_WAITALL(本次读操作读取所有数据后才返回)</li><li>blocking vs nonblocking:</li><li style="list-style: none; display: inline"><ul><li>read: 当缓冲区非空，读取(最多读空缓冲，可能小于要求大小)；当缓冲区为空，blocking的socket会阻塞等待，而nonblocking的socket直接返回EWOULDBLOCK(linux下叫EAGAIN)</li><li>write: 当缓冲区非满，写(最多写满缓冲，可能小于要求大小)；当缓冲已满，blocking的socket会阻塞等缓冲有空间，而nonblokcing的socket返回EWOULDBLOCK</li><li>connect: blocking的socket等待三次握手完成；nonblocking返回EINTERPROGRESS，之后可以用select来等待socket可读写。</li></ul></li><li>netscape等浏览器加载网页的时候就用了非阻塞connect: 阻塞connect的抓取主页，读取到主页的html后，边解析内容边以IO multiplexing的方式并发nonblocking connect的抓取解析出来的其他URL</li></ul><div>2. 关于read/write的思考</div></div><div><ul><li>阻塞分三个级别:</li><li style="list-style: none; display: inline"><ul><li>全阻塞: 可以可靠的传输n字节，除非遇到EOF。典型: 文件IO</li><li>半阻塞: 传输字节>0但<n，当内核缓冲为空或者满的时候，需要阻塞，其他时候立即返回。典型: socket</li><li>非阻塞: 以O_NONBLOCK调用fcnl操作过的文件句柄，read/write遇到空缓冲、满缓冲时，返回EWOULDBLOCK</li></ul></li><li>几种常见设备:</li><li style="list-style: none; display: inline"><ul><li>文件: read/write全阻塞，方便；阻塞时间长达10ms，如果nonblocking化的话，这10ms可以干其他事；另外可以考虑批量提交IO操作的异步IO，提高"磁盘->内核buf->应用buf"流水线的利用率。最后，磁盘IO应该按块读写，比如bufferedIO，ANSI C的标准库即是如此</li><li>socket:</li><li style="list-style: none; display: inline"><ul><li>read, write是半阻塞的，不保证n字节的传输，使用难度和非阻塞一样，不如直接上O_NONBLOCK标志</li><li>就一般程序来说，readline、writen这种需求几乎是刚需，因此需要在nonblocking的read/write上包装一层readn/writen，为了实现readline可能还需要引入bufferedIO</li><li>对于纯网络程序来说，如果允许彻底以event drive的方式来组织程序，那么select/poll/epoll + nonblocking IO可以最大化吞吐，当然编码复杂</li></ul></li></ul></li><li>总结:</li><li style="list-style: none; display: inline"><ul><li>文件:</li><li style="list-style: none; display: inline"><ul><li>一般直接read, write，方便的话利用bufferedIO</li><li>特殊情况需要异步IO，使DMA的时候主线程能干其他事；进一步，批量提交请求能最大化流水线利用率</li></ul></li><li>服务器。吞吐越大，越复杂，从复杂度和性能的平衡上，分3个级别供取舍(主要在1、3之间取舍):</li><li style="list-style: none; display: inline"><ol><li>blocking fd。用select/poll检测多个fd的可读状态，如果为真，则read(用于forwarding server)，或者半阻塞的readn/readline(读取协议头)，再阻塞的writen。显然这里readn/readline,writen都是半阻塞，性能不够高，但编码简单。简单提升性能的话，fork/pthread_create即可</li><li>blocking fd。用select/poll/LT epoll检测多个fd的读写状态，用户自己维护读缓冲，自己维护写缓冲，编码复杂，性能不错。</li><li>nonblocking fd。用ET epoll检测多个fd的读写状态，对每个fd，连续读写直到EWOULDBLOCK，自己维护读写缓冲，编码复杂，性能最好。</li></ol></li><li>客户端:</li><li style="list-style: none; display: inline"><ul><li>一般程序，connect；需要的时候fork/pthread_create后并发connect</li><li>高IO要求的时候，使用non blocking的connect + select/poll</li></ul></li></ul></li></ul><div>2. select, poll, epoll</div></div><div><ul><li>select:</li><li style="list-style: none; display: inline"><ul><li>每次wait都将fd_set在用户态和内核态之间拷贝</li><li>需要轮询(poll)，并且轮询的复杂度是O(最大fd)</li><li>最大监听fd个数有限(linux是1024，修改需要重编译内核)。随着监听的fd增多性能明显下降</li></ul></li><li>poll:</li><li style="list-style: none; display: inline"><ul><li>每次wait都将fd_set在用户态和内核态之间拷贝</li><li>需要轮询，轮询的复杂度是O(监听的fd个数)</li><li>监听数无上限，只收性能限制。随着监听的fd增多性能明显下降</li></ul></li><li>epoll:</li><li style="list-style: none; display: inline"><ul><li>原理: 托管fd会导致epoll将自己放到该fd的DMA完成的callback队列中，该callback会创建event加入epoll_wait的数组中，而epoll_wait的实现是while(1)并检查event数组非空，如果为空的话sleep(0)</li><li>level-trigger模式:</li><li style="list-style: none; display: inline"><ul><li>只在epoll_ctl的时候拷贝fd/events结构到内核</li><li>少许轮询，轮询复杂度是O(可写/可读的fd个数)</li><li>监听数无上限(可多达10k+)，性能不因监听数增加明显下降</li></ul></li><li>edge-trigger模式:</li><li style="list-style: none; display: inline"><ul><li>只在epoll_ctl的时候拷贝fd/events结构到内核</li><li>极少轮询，复杂度是O(本次poll中可读/可写的fd个数)</li><li>监听数无上限(可多达10k+)，性能不因监听数增加明显下降</li></ul></li></ul></li><li>总结，epoll性能最佳，但使用稍麻烦，适合专用服务器；而select/poll使用方便，甚至可以用在文件fd上，适合任何程序，而poll相比select有fd个数不限的优势</li></ul><div>2. sync系列函数</div></div><div><ul><li>sync: 将整个OS的filesystem cache刷回disk</li><li>fsync: 刷单个文件，包括fstat中的元数据修改</li><li>fdatasync: 刷文件的数据修改，比如write</li><li>fflush: 刷ANSI C自己管理的应用层buf</li></ul><div>2. 了解了下libevent，基本上就是select/poll/epoll/kqueue的跨平台封装，加上是c语言，使用上仍然不方便</div></div><div><br>
</div><div>3. 编程珠玑，第一章</div><div><ul><li>问题: 文件中有1千万个电话号码需要排序输出</li><li style="list-style: none; display: inline"><ul><li>首先重新定义问题: 有大小不超过n的数需要排序；每个数只出现1次；数没有额外关联数据。运行时间最多几分钟，10秒以下的话无需进一步优化(<b>这是设置优化期望!!</b>)</li><li>可行的三种方案:</li><li style="list-style: none; display: inline"><ol><li>多趟算法->以step为增量，遍历m趟，每次将[i*step, (i+1)*step)读入内存，排序，并输出。缺点是多趟遍历，优点是，内存可以任意小，只是趟数增加</li><li>位向量。10M的不重复整数，用1.25M的位向量足矣。该方案是针对3个条件特化后的排序办法，如果3个条件分别有变数:
<ul><li>1. 如果数值离散->1M可以表示256K个区间，每个区间16k个数，先遍历一次，几下每个区间的个数，然后遍历第2次，根据区间中数的多寡，来选择不同的表示法，多的用位图，少的直接记录数本身</li><li>2.1 每个数出现最多N次->改为char/short/int向量，甚至log(N)的位向量</li><li>2.2 每个数可以出现任意次->法1，改为index向量(长为n的index的数组)，index指向额外数组，那个数组保存实际出现次数；当然，此法也可以说是指针向量。法2，在位向量的基础上，额外给一个hash表，只有出现多次的数才会在hash表中也有计数</li><li>3. 数关联了附加信息->改为index向量，index向量指向的额外数组中，元素保存了附加信息(以及出现次数)</li></ul></li><li>归并->1M可以表示256K个数，将源文件分配到40个小文件，写过去的同时排序；然后对40个小文件两两归并，直到剩1个</li></ol></li></ul></li><li>涉及的原理:</li><li style="list-style: none; display: inline"><ul><li>正确的问题。先分析问题抓住特殊域，再针对性给方案。在程序员修炼之道中强调，这叫dig the requirements</li><li>位图表示。要求域小、不重、无额外数据。如果重复或者有额外数据，可以用一个包含重复次数和额外数据的指针来表示，也就成了指针数组，作为优化，用索引比指针占空间更小</li><li>多趟算法。针对结果域进行细分，多次读取输入</li><li>时间-空间可以双赢。一般是舍空间换时间，但很多时候，省空间的方案时间也小，比如这里的位图</li><li>简单设计。设计已达完美的标准不是不能增加东西，而是不能减少东西</li></ul></li><li>把课后题做了下</li></ul><div>3. c/c++中需要注意的一个问题: malloc(sizeof(A) + sizeof(B))这种东西不要出现。应该struct C{A; B}; malloc(sizeof(C))，因为内存对齐的考虑</div></div><div><br>
</div><div>3. mergeSort的两种实现: (具体代码见我的ProgrammingPearls/1/mergeSort.cpp，两者性能相同)</div><div><ul><li>mergeSort由inplaceMergeSort和mergeSortTo交叉调用实现:</li><li style="list-style: none; display: inline"><ul><li>mergeSort == inplaceMergeSort</li><li>inplaceMergeSort:</li><li style="list-style: none; display: inline"><ul><li>mergeSortTo(src_seg1, dest_seg1)</li><li>mergeSortTo(src_seg2, dest_seg2)</li><li>merge(dest_seg1, dest_seg2, src)</li></ul></li><li>mergeSort2:</li><li style="list-style: none; display: inline"><ul><li>inplaceMergeSort(src_seg1, dest_seg1) (参数2只是辅助缓冲)</li><li>inplaceMergeSort(src_seg2, dest_seg2)</li><li>merge(src_seg1, src_seg2, dest)</li></ul></li></ul></li><li>mergeSort由递归调用mergeSortTo实现:</li><li style="list-style: none; display: inline"><ul><li>mergeSort == inplaceMergeSort</li><li>inplaceMergeSort:(同上)</li><li style="list-style: none; display: inline"><ul><li>mergeSortTo(src_seg1, dest_seg1)</li><li>mergeSortTo(src_seg2, dest_seg2)</li><li>merge(dest_seg1, dest_seg2, src)</li></ul></li><li>mergeSortTo:</li><li style="list-style: none; display: inline"><ul><li>mergeSortTo(src_seg1, dest_seg2)</li><li>mergeSortTo(src_seg2, src_seg1)</li><li>merge(src_seg1, dest_seg2, dest)</li></ul></li></ul></li></ul><div>3. HH漫画网的爬虫</div></div><div><br>
</div><div>4. 不用在posix多线程程序中使用fork: </div><div><ul><li>fork后的子进程里只有fork的那个线程，其他线程凭空蒸发</li><li>posix的mutex等因为性能原因通常被实现在用户态，所以fork后会拷贝一份。问题是，fork后子进程可能会出现一个没有owner的锁(因为owner不是fork线程，蒸发了)，这时子进程的唯一线程可能会因为该锁而死锁</li></ul><div>4. wait每次消耗一个子进程的状态变化。如果有子进程则等待变化，没有子进程则直接返回错误</div></div><div><br>
</div><div>4. 以static initializer初始化的静态同步对象不需要pthread_xxx_destroy</div><div><br>
</div><div>4. pthread_mutex比我用semaphore实现的mutex快很多(可能用了spin lock的原因?); pthread_rwlock比我用semaphore实现的readerwriterlock快一点</div><div><br>
</div><div>4. HH漫画网的爬虫增加书列表选择</div><div><br>
</div><div>4. C++ project: Non-Intrusive AutoReleasePool</div><div><br>
</div><div>4. C++ project: guard ptr, 其每个call site都受到lock/unlock保护</div><div><br>
</div><div>4. C++的宏TO_STRING和CONN: </div><div><ul><li>直接用#或者##的话，都是直接将传入的参数字符串化或者连接，如: #NUM -> "NUM", var_##NUM->var_NUM</li><li>而如果将#和##放到深一层的_TO_STRING和_CONN，那么调用_CONN的实参会先展开，等到进行#和##的时候，已经是展开值了，如: TO_STRING(NUM)->1, CONN(var_, NUM)->var_1</li></ul><div>4. 关于pthread_cond</div></div><div><ul><li>unix下pthread_cond只有一种正确的用法(用陈硕的说法)</li><li style="list-style: none; display: inline"><ul><li>signal端:</li><li style="list-style: none; display: inline"><ul><li>用mutex保护条件的布尔表达式</li><li>一般修改表达式为真后signal/broadcast</li></ul></li><li>wait端:</li><li style="list-style: none; display: inline"><ul><li>用mutex保护表达式判断</li><li>确保wait的时候mutex锁上</li><li>用while循环反复判断和wait</li></ul></li></ul></li><li>一般而言: broadcast用于通知状态变化；signal通知资源可用</li><li>用pthread_cond实现通用的waiter: (参见我的代码C++/ReaderWriterLock/PosixWaiter)</li><li style="list-style: none; display: inline"><ul><li>用mutex保护条件判断和修改，否则信号可能丢失(因为race)</li><li>用bool表达式存储条件，否则信号可能丢失(将edge-trigger变成了level-trigger)</li><li>用while循环反复判断条件并wait (避免spurious wakeup，即由于cond的实现问题导致的没有signal/broadcast却发生wait醒来的事情)</li></ul></li></ul><div>4. 重新实现readerwriterlock，提高writer的优先权: (参见我的代码 C++/ReaderWriterLock/ReaderWriterLock2，report.txt里面的结果表示效果明显)</div></div><div><ul><li>参见<操作系统:精髓与设计原理>的164页算法，经典。注意166页上还有一个靠消息来实现readerwriterlock的算法，它添加了一个controller线程，这个最好画出状态迁移图来理解，很简单，3个状态</li><li>针对读多写少的特点，一步步实现、优化读写锁: (优化的几点逐个在源码中去掉，是能观察到性能下降的)</li><li style="list-style: none; display: inline"><ol><li>读写都用mutex: 读不能共享，浪费了</li><li>区分读写=>将readers看做一个整体，当这个整体占有资源的时候，writer阻塞，但reader可以并发。实现: ++readerCount==1的时候lockRes，--readerCount==0的时候unlockRes。缺点: 由于readerCount>0的时候，新reader进入无需锁，所以如果reader连续进入，writer永远拿不到锁</li><li>优化，一旦有writer，后续reader进入受阻=>writer在lockRes之前，先lock(hasWriter)，unlockRes之后，要unlock(hasWriter)；而reader在lockRes之前，必须lock(hasWriter); unlock(hasWriter)。因此，一旦writer的lock(hasWriter)成功，可以放心的阻塞在lockRes上等之前的reader离开，因为后续进入的reader都阻塞在了lock(hasWriter)上。这里的问题是，假如reader非常多，操作频繁、绵绵不绝，writer进行lock(hasWriter)的时候可能有一队列的reader也阻塞在lock(hasWriter)上，mutex的唤醒是随机的，可能导致writer很难拿到锁，比如1000个reader、5个writer到来，每个writer都很艰难的才能lock(hasWriter)成功</li><li>优化，让参与lock(hasWriter)的reader只有一个=>在reader对hasWriter的lock+unlock的前后，再包装一层lock(singleReader), unlock(singleReader)，这样，当很多reader到来时，只有1个在lock(hasWriter)上和writer竞争锁，其他的reader都阻塞在lock(singleReader)上。现在还剩下一个问题，第1个writer修改资源的同时，后续writer到来，他们相对reader没优势</li><li>优化，让后续writer能直接穿过lock(hasWriter)进而阻塞在lockRes上: ++writerCount==1的时候才lock(hasWriter)，而--writerCount==0的时候才unlock(hasWriter)，这样，只要一个writer能lock(hasWriter)成功，后续writer都能连续进入，将reader都阻塞在后面，这种情况下，就是1个writer成功的lockRes，n个writer阻塞在lockRes上，1个reader阻塞在lock(hasWriter)上，n个reader阻塞在lock(singleReader)上</li></ol></li></ul><div>4. gnu工具addr2line可以把指定elf中的地址值转化成文件+行。比如"addr2line 0x123 -e ./main"</div></div><div><br>
</div><div>4. C++ project: CmdRunAndRetrive。利用pipe来实现，相当于python中的subprocess.check_output</div><div><br>
</div><div>5. C++ project: TCPSocket, 部分。因为涉及的system call太多，进行了封装(深切的感受到，如果不是纯算法库，需要和其他api打交道的话，抽象是必须的，否则代码会写成屎)：</div><div><ul><li>Utils: 其他模块的基石。包括小工具CONN,TO_STRING,ARRAY_SIZE,DISABLE_COPY,ON_EXIT_SCOPE等；以及明确异常体系, 基类Exception，用于支持能捕获环境的ENSURE；两个派生类RuntimeException和LogicError，分别表示运行时异常和逻辑错误，其中逻辑错误会进行stack traceback，如果捕获到逻辑错误，必须exit，运行时错误允许容错；特化了一种特殊的RuntimeException，即访问strerror的PosixException，靠它，对所有的systemcall进行了错误码到异常的转换</li><li>Threading: 封装semaphore、mutex、rwlock、condvar、thread等；另外还有waiter, concurrentQueue</li><li>IO: 封装了基于fd的blocking/nonblocking的read/write</li><li>Socket: HostAddress类处理了ip、域名以及端口的字节顺序等问题；TCPSocket类只是socket fd的一个浅包装，不管理生命期，只负责封装api和错误码到异常的转换</li><li>Poller: 封装了linux下三种reactor的api: select, poll, epoll</li></ul><div>6. 用find查找多个类型的文件，必须启用find的正则模式: find . -regextype posix-extended -regex '.+\.(h|cpp)'</div></div><div><br>
</div><div>6. 对多个文件进行批量替换:</div><div><ul><li>用vi:</li><li style="list-style: none; display: inline"><ul><li>先确保编辑多个文件: "vi *"， 或者在vi中"args *"</li><li>再"argdo %s/ENSURE/ASSERT/g | update"</li></ul></li><li>用sed:</li><li style="list-style: none; display: inline"><ul><li>find . -type f | xargs sed -i 's/ENSURE/ASSERT/g'</li></ul></li></ul><div>6. git用HEAD^表示父亲, HEAD^^表示父亲的父亲；等价的方式是HEAD~1, HEAD~2；后者方面追溯任意版本</div></div><div><br>
</div><div>6. getopt的使用: </div><div><ul><li>man getopt</li><li>单字符表示无参数的选项: "v"</li><li>字符+:表示一个参数: "n:"</li><li>字符+::表示一个可选参数: "c::"</li><li>在于parse循环中，optarg表示参数字符串; getopt返回值'?'表示无效选项，':'表示缺少参数，这些一般都用switch的default来处理，在里面打印help</li><li>parse结束后，argv[optind]表示选项之外的参数</li></ul><div>6. C++ project: TCPSocket, 部分。今天完成了Concurrent client，能够利用select/poll/epoll并发的去connect多个不同的tcp服务器，发起请求和接收响应。对之前的模块进行了大规模的重构，以及修复bug</div></div><div><br>
</div><div>7. C++ project: TCPSocket, 部分。完成BlockingServer，即只用poller来监听accept/read事件，一旦事件发生，就block的读取整个包，并block的发送response</div><div><br>
</div><div>7. 关于io multiplexing server的想法，三种级别:</div><div><ul><li>blocking server: 只用select来监听listen socket的connect请求和client socket的request请求，一旦select返回，就accept或者receive整个request然后马上write response。缺陷是read request和write response都是阻塞的，效率低下。想象作为服务器，一堆以各个端口为目标的tcp数据带来，你的服务器却阻塞了整个线程在等某个特点端口的包；另外，也容易被攻击，比如，只发一部分request头；或者总是不receive response，结果由于tcp的flow control，服务器的写缓冲满，write总不返回</li><li>reactor server: 即通过onRead和onWrite来通知socket可读或者可写，需要用户代码自己管理缓冲。性能最高，是select/poll/epoll的原生模型。当然，用起来很不方便。例子，libevent</li><li>proactor server: 在reactor的基础上，由库来管理缓冲，要求用户在read/write的同时提供readCompleteHandler/writeCompleteHanlder。当然由于库管理缓冲内部多了些拷贝，所以在性能上的可定制性差些(这是unix的情况，windows下的iocp就是原生的proactor)，但用户使用方便。例子，asio。实现proactor的两种方案:</li><li style="list-style: none; display: inline"><ul><li>level trigger的poller + blocking/nonblocking的socket: 其中select/poll/epoll都是level trigger的。如果使用nonblocking的socket，由于每次都将缓冲消耗尽，所以poller的wait次数更少，性能更佳</li><li>edge trigger的poller + nonblocking的socket: 这里的poller只能是ET模式的epoll。这是unix下实现io multiplexing的最佳方案</li></ul></li></ul><div>8. C++ project: TCPSocket, 部分。EventDrivedReadBuffer/EventDrivedWriteBuffer，ProactorService，以及在此基础上写成的ProactorServer</div></div><div><br>
</div><div>8. C++ project: TCPSocket, 部分。Proactor client</div><div><br>
</div><div>8. 最近TCP客户端编程的一个结论: 本机下载，即使是最简单的阻塞IO，只要开启多进程/多线程，轻松把我的下行带宽占满(4MB)。因此，如果是下载东西，直接python开多线程够了</div><div><br>
</div><div>9. 在使用select/poll/epoll等reactor模式的api时，POLLRDHUP(EPOLLRDHUP类似)应该和POLLIN一起，用作输入检测；而POLLHUP作为错误事件</div><div><br>
</div><div>9. 对nonblocking的socket进行accept的时候，也应该是循环；类似的，read/write也是循环；而connect的话，因为只会有一次，所以不循环也无妨</div><div><br>
</div><div>9. 关于level-trigger/edge-trigger的poller搭配blocking/nonblocking fd的时候:</div><div><ul><li>LT的poller搭配blocking fd: 没问题，read没有读完或者accept没有处理完，poller下次还会通知</li><li>LT的poller搭配nonblocking fd: 没问题，read会读到底，accept也会接收所有的连接，poller有能力再通知但是不必</li><li>ET的poller搭配blocking fd: <b>有问题</b>！read或者accept没有处理完，poller不会再通知了。导致数据已经到了本地，fd却不知道应该读，connectioin已经到了本地，lsiten socket却不知道去再accept</li><li>ET的poller搭配nonblocking fd: 没问题，虽然poller只会通知一次，但是fd会一次性的read到底或者accept到底(即直到遇到EAGAIN错误)</li></ul><div>9. C++ project: TCPSocket, 部分。WebProxy</div></div><div><br>
</div><div>10. 《C语言程序设计》</div><div><ul><li>C语言不受限于OS和机器，适合用来编写编译器和操作系统，因此被称为“系统编程语言”</li><li>多年来C语言的定义就是《The C Programming language》第1版，直到1983年ANSI开始拟定、1988年完成的ANSI C标准</li><li>同其他任何语言一样，C语言不完美，比如某些运算符的优先级是不正确的</li><li>《TCPL》附录中有YACC支持的Grammar</li><li>C语言中，注释不允许嵌套</li><li>:?表达式类型是固定的，编译器会尝试对?做隐式类型转换以统一类型</li><li>由深层for循环跳出、错误处理，都是使用goto的合理场合</li><li>无论register变量实际上是否被放置在寄存器中，它都是不能被取地址的。（是否有可能因此而杜绝了pointer aliasing带来的性能劣化?）</li><li>最简单的qsort实现中，在partition之前加上一轮swap(begin, mid)，可能有效优化性能和避免输入有序时的退化</li><li>getchar、putchar通常被实现为宏，因为性能原因。但实际上标准不允许实现存在类似i++引起的副作用错误，所以getchar的宏实现很可能是错误的</li><li>string literal中的"\c\d"等不支持的转义符，其中的"\"会被直接去掉</li><li>sizeof是编译器运算符，用来计算对象/类型长度</li><li>typedef出现的位置和static、extern一样(<b>实际上，在grammar中，typedef和auto/register/static/extern一样，都被叫做storage-class specifier</b>)，而它作用的identify出现的位置，和普通的变量声明出现的位置一样。因此，其grammar仅仅是"typedef var_declartion";</li><li>使用bit field的时候，用unsigned</li><li>printf的格式控制组成是:(1)% (2)数字，表示最小宽度 (3). (4)数字，表示小数位 (5)字符，输出方式</li><li>在Unix下，fopen中的"b"是无意义的</li><li>Unix中，目录也是文件，在某些实现中，它的内容就是"filename+inode_idx"</li><li>一种malloc、free实现: freelist总是按地址排序的，因此，free的时候判断是否需要合并，只需要看freelist前后节点的地址是否连续</li><li>在scanf中，可用%*d这样的格式来消耗指定类型的输入，比如scanf("%*d %*d %d", &i)表示读取第3个整数</li><li>ungetc一个字符串的时候，注意逆序放回</li><li>::creat用于创建文件</li><li>ANSI C支持remove删除文件或目录，在unix上，实现为unlink或者rmdir</li><li>需要一个struct按照特定类型对齐，可以在内部union特定结构</li><li>预处理器</li><li style="list-style: none; display: inline"><ul><li><b>宏调用的实际参数是逗号分割的记号序列，用引号或嵌套的括号(parentheses)括起来的逗号不能用于分割实际参数</b>。因此，对于ON_EXIT_SCOPE中用到的多个捕获的lambda，如"[a, b, c](){}"，把整个lambda用()包起来，这里的"a,b,c"就不会被当做宏的实参了</li><li><b>除非遇到#或者##，否则宏调用的实参会被检查和展开</b>。这解释了为什么CONN和TO_STRING的实现会多调用一层。</li><li><b>当某个标识符在某个扩展中被替换后，后续扫描再遇到此标识符不会执行替换</b>，而是保持不变</li><li>#error description</li><li>#line 100 "a.cpp"，可以用来提示预处理器当前的文件名和行号。对于动态代码生成器有用。预处理过后的c文件中充斥了这种命令，因为#include会破坏行计数</li></ul></li></ul><div>10. 程序设计实践(The practice of programming)，第一章，风格</div></div><div><ul><li>一个变量的作用域越大，它的名字所携带的信息就应该越多</li><li>人们常常鼓励程序员使用长变量名，而不管用在什么地方。这种认识是错误的，清晰性经常是随着简洁而来的</li><li>对于类而言，由于类型本身标明了上下文，因此方法不应该再出现类名，比如队列的方法不应该叫popQueue</li><li>函数应该采用动词，后面可以跟着名词</li><li>对于bool返回值的函数，函数名应该清楚的返回真值的情况，比如isoctal就比checkoctal好</li><li>当你工作在不是自己的程序上时，请保留原有的编码风格，即使你特别喜欢自己的风格。程序的一致性比你本人的习惯更重要，因为这将使你之后的其他人生活更容易些</li><li>每种programming language有它自己的惯用法，即那些经验丰富的程序员写代码片段的习惯方式，学习一个PL的过程中，一个中心问题就是逐渐熟悉它的习惯用法</li><li>用for (p = head; p != NULL; p = p->next)来迭代链表</li><li>用for (;;)来写无限循环</li><li>过于拉长的代码会摊到更多的页和显示屏中去，进一步妨碍人阅读</li><li>else如果为空，请至少给错误信息</li><li>嵌套的if其实可以写成非嵌套的if else，比如"if (fault1) {} else if (fault2) {} else if (fault3) {} else { the right logic!!! }"。这里的准则是: 判断对应的逻辑应该紧接，而不是离得很远</li><li>老的C程序员有一种倾向，把短而执行频繁的计算写成宏，而不是函数。比如isdigit, getchar。在新的机器和编译器面前，宏的缺点已经超过了那丁点的性能好处。如果宏的实参是函数调用的话，那么宏体中的多次表达式引用还可能带来性能问题</li><li>除了0和1之外的magic number，都应该有个自己的名字</li><li>不考虑宏的情况下，C语言中能用作常数的只剩下enum了(C++中可以用const变量)</li><li>赞成不同形式的常数用法，比如'\n', nullptr, 0</li><li>用语言去计算大小，而不是显示写出来。比如sizeof</li><li>sizeof的使用可以避免为临时数组的长度引入新名字</li><li>注释是帮助阅读的手段。如果注释只说明了代码本身已经讲明的事情，甚至与代码矛盾，或者过于精心排版，那么就是在帮倒忙</li><li>不要注释差的代码，重写它。如果注释的长度超过了代码本身，那么代码应该改了</li><li>修改代码时确保注释仍然有效</li><li>如果真的需要很多话来注释特殊情况，那么代码应该重写</li><li>学生常被告知应该注释所有内容，职业程序员也常本要求注释所有内容。但是，一旦盲目遵循这些规则的结果是丢掉了注释的真谛。注释是工具，是为了帮助读者理解程序中不容易通过代码直接看到的部分</li><li>应该尽可能的把代码写得容易理解，代码越容易理解，需要的注释就越少。好的代码注释远少于差的代码</li><li>好的风格应该成为习惯，如果你在开始写代码的时候就关心风格问题，你将逐渐养成好的编程习惯，而在习惯的自动帮助下，你的潜意识会帮你照料好很多细节问题，甚至你在工作压力之下写的代码也是好的</li></ul></div><div>10. 杂项</div><div><ul><li>考虑递归算法: 其实就是将数据节点放在了调用栈的各栈帧上，以数据的角度来思考最后组合的顺序，那么，递归算法的编码顺序也就清楚了。(比如递归版的itoa什么的)</li><li>c99中规定了在<stdint.h>里面应该typedef一组intN_t和uintN_t的整形。例如int32_t, uint32_t。因此，在需要指定位宽的时候(比如序列化)，用这些类型</li><li>即使是非常小的程序(内存分配模式及其简单)，也不要期待realloc不移动指针，其具体行为依赖于分配器的实现。据实测，在linux的默认分配器上，从1字节开始，每次realloc翻倍的内存，超过128K过后，地址就每次都变了...</li><li>linus那种利用二级指针的链表remove_if技巧</li><li>lower_bound, upper_bound的实现，按照loop invarant来写。对于lower_bound，val > *begin && val <= *last，最终return last; 对于upper_bound, val >= *begin && val < *last，最终return last</li><li>非常容易写正确的shell sort，出自《TCPL》</li></ul></div><div>11. 编程珠玑，第2章，啊哈，算法</div><div><ul><li>二分查找的应用</li><li style="list-style: none; display: inline"><ul><li>查找一个范围的一个数</li><li>查找源码中的错误行</li><li>变化->比起两分支，可以使用多分支</li></ul></li><li>rotate ab->ba</li><li style="list-style: none; display: inline"><ul><li>法1: a^b^->(a^b^)^==ba。即对ab分别逆序，再对整个序列逆序。</li><li>法2: a(b1b2)->b2b1a->(递归处理b2b1)。同stl中的rotate</li><li>法3: n[0]<-a[i]<-a[2*i%len(n)]<-... 这样循环移动一个元素，当回到idx 0时，如果还有元素没处理，继续n[1]<-n[i+1]<-...。书里称为戏法，即每隔n个元素左移，只需要O(1)的额外空间</li></ul></li><li>注意字符集连续且有限的序列排序，比如sort(string), sort(n1~nn)，可以用计数法，在O(n)的时间搞定，即桶排序。书中的变位词的分类依据，既可以是sorted(str)，也可以是桶排序的中间统计信息</li><li>优秀程序员都是先坐下来想方法而不是直接开始编程。但何时开始编码，这取决于解决问题和反思答案所获得的经验</li><li>pi秒就是1纳世纪</li></ul><div>11. 程序设计实践，第2章，算法与数据结构</div></div><div><ul><li>只有熟悉了领域的工具与技术才能对特殊问题提供正确解答</li><li>即使是复杂如编译器和浏览器，其主要数据结构也无非是数组、表、树和散列表。如果需要更精巧的东西，那多半也是这些基本元素的组合。对大部分程序员而言，需要知道有哪些合适、可用的算法与数据结构，并知道如何在做出选择</li><li>快排之所以快：一旦知道某个元素比基准值小，那么它再也不必与那些大元素比较</li><li>如果quicksort中的partition得不到均匀的划分，其性能就会退化；因此，快排的性能是nlog(n)~n^2</li><li>对于cmp这种函数(即返回值为-1,0,1)，直接return a - b是不合适的，因为可能溢出</li><li>ANSI C有bsearch，但是其价值比不上qsort: qsort的实现，为了尽可能的高效和避免特殊输入的退化，做了很多定制，其代码可能达到数页纸的篇幅，但是bsearch的实现很简单，只需数行，如果用库函数的，需要提供比较器的指针，其性能开销可能入不敷出</li><li>矩阵乘法是O(n^3)的复杂度</li><li>尾递归可以直接转换成循环，最差、但简单的改写法是goto到函数开头</li><li>java早期版本的hash(string)，对长string采用了隔几个字符采样的方法，一度出现性能bug，因为类似url(以<a href="http://开头" target="_blank">http://开头</a>)、文件名(.exe, .txt等后缀)等特殊输入，它可能对不同的输入采样到同样的结果</li></ul><div>11. 杂项</div></div><div><ul><li>time a | b | c，这样，time命令会对管道中每个环节分别计时</li><li>std::queue默认是用std::deque实现的; std::stack默认也是std::deque实现的。参考了vs2008和g++的stl</li><li>用for (Node *p = mHead; p != nullptr; p = p->next)遍历数组，再加上linus的二级指针技巧，神技！</li><li>pre condition+post condition+loop invariant: <b>写算法的神器！</b>加上for循环、begin/end的简洁迭代方式，很容易一次就把lower_bound/upper_bound/nth_element/各种sort算法写正确。总之，通过invariant来验证算法的正确性很重要！这个应该熟练掌握!</li><li>所谓"对于已排序的输入，怎样插入能让二叉树尽量平衡"，这里讨论的二叉树是普通的BST，而不是AVL/RBTree，因此，简单的递归插入mid值即可</li></ul><div>12. 编程珠玑，第3章，数据决定程序结构(Data structures programs)</div></div><div><ul><li>当程序员在无计可施时，从代码中解脱出来，退回起点并集中精力研究数据，常常能有奇效。数据的表示形式是程序的根本</li><li>冗长相似的代码常常可以使用数组来更好的表述</li><li>在动手编码之前，优秀的程序员会彻底的理解输入、输出和中间数据结构，并围绕这些结构构建程序</li></ul><div>21. 程序设计实践，第3章，设计与实现</div></div><div><ul><li>Fred brooks，《人月神话》: 看了你的流程图仍然一头雾水；而看了你的表后，流程图反而显得太明显</li><li>数据结构是程序构造过程中的中心环节，一旦数据结构设计好，算法就是瓜熟落地，而编码也很容易</li><li>程序的设计可以用语言来装饰，但通常不会为语言所左右</li><li>马尔科夫链</li><li style="list-style: none; display: inline"><ul><li>前缀太短，生成的结果将趋于无意义；前缀太长，则趋向于拷贝源串；对英文文本而言，一般前后缀采用2:1的形式</li></ul></li><li>大部分程序采用的不过是很少几种不同的算法和数据结构</li></ul><div>21. 程序设计实践，第4章，接口</div><div><ul><li>《修墙》：砌墙之前，必须设法弄清，什么应该在墙内，什么应该在墙外，以及，最需要防御的又是什么</li><li>设计，就是在一组冲突的需求和制约之间找到平衡。设计接口的时候需要做出大量的决策，而其中大部分常常都是无意识中做出的，如果不遵循某些原则，生产出来的可能是随意的接口，它将妨碍甚至破坏我们的日常程序设计工作</li><li>设计的考虑</li><li style="list-style: none; display: inline"><ul><li>界面：应该提供哪些服务和访问？应该提供一种统一而方便的服务，功能丰富而又不泛滥</li><li>信息隐藏：哪些应该私有，哪些应该共有？应该便于访问，而又隐藏实现细节，这样，修改才不会影响到使用者</li><li>资源管理：内存及其他资源的分配、释放和拷贝应该由谁负责？</li><li>错误处理：谁检查错误？谁报告？如何报告？发现错误后，应该做哪些恢复性操作？</li></ul></li><li>接口应该尽量不依赖于外部组件，尽量自给自足；如果实在无法办到，那也应该把对外部组件的依赖做得非常明显</li><li>API一致性:</li><li style="list-style: none; display: inline"><ul><li>C语言库的strxxx一致性非常好：数据总是从右往左。memxxx也一样</li><li>C的IO库的一致性比较差，有些API把FILE*参数放在最左，有些放在最右</li><li>unix的命令行参数一致性不好，同样的选项字符在不同的命令中解释可能不同</li><li>*如果总是由shell来解释，则将得到一致的结果；但如果由具体程序来解释，则行为可能不一致</li><li>FILE*的实现是暴露了的，但好的程序员不会依赖它</li></ul></li><li>今天设计得好的接口在明天可能会有缺陷，但足够好的设计能将这个明天推迟得更晚</li><li>错误应该在尽可能低的层次上检测，在某个更高的层次上处理；对错误的处理方式，应该由调用方决定</li><li>将已经释放的指针置为空，能够更容易发现对无效指针的错误使用</li><li>防御性编程，是指坏的输入不会破坏程序本身</li><li>图形界面的“正确”，强烈依赖于个人期望；而通常用户界面这一部分，其代码可能比实际工作的算法代码更多，可见程序的交互、输入容错之复杂</li><li>接口易用的保证：简单性、清晰性、规范性、统一性、熟悉性、严谨性</li></ul></div><div><br>
</div><div>21. 程序设计实践，第5章，排错</div><div><ul><li>程序的复杂性与各部件间可相互作用的途径数有关</li><li>人们提出了许多技术以减少部件间的交互：</li><li style="list-style: none; display: inline"><ul><li>信息隐藏</li><li>抽象和接口</li><li>语言特性</li></ul></li><li>好的程序员知道排错需要花费的时间和写程序一样多，所以他们努力从已有的错误中学习；任何错误都能教导你防止类似错误再次发生，以及发生后怎样尽快识别</li><li>排错非常困难，可能花费很长、甚至无法预期的时间，因此，早期预防胜过事后补救；对减少错误有帮助的技术包括：</li><li style="list-style: none; display: inline"><ul><li>好的设计</li><li>好的风格</li><li>边界条件测试</li><li>断言和合理性检测</li><li>防御性编程</li><li>静态分析工具</li><li>程序设计语言</li><li style="list-style: none; display: inline"><ul><li>下标检查</li><li>指针的算数运算、强制转换约束；甚至去掉指针</li><li>垃圾收集</li><li>内置的字符串类型</li><li>类型检查(如C++中的iostream相对于printf)</li><li>部分语言特性也有错误引导的作用</li><li style="list-style: none; display: inline"><ul><li>goto</li><li>全局变量</li><li>不限制的指针操作</li><li>隐式类型转换</li></ul></li></ul></li></ul></li><li>锻炼排错能力的原因：</li><li style="list-style: none; display: inline"><ul><li>一些非主流语言没有debug功能或者很弱</li><li>debug功能是依赖于具体系统的，因此，在另一个系统中工作时，可能无法使用熟悉的排错系统（如gdb和vc）</li><li>部分程序很难debug，如多进程、多线程、操作系统、分布式系统</li></ul></li><li>作者倾向于只使用debug系统中的栈打印和变量打印功能，其他时候靠思考，辅以关键位置添加打印语句和一致性检查函数</li><li>好线索，简单错误的情况</li><li style="list-style: none; display: inline"><ul><li>检查输出中的错误情况，推测产生原因；根据栈轨迹，推测在什么情况下、在哪里发生的</li><li>寻找错误模式，如</li><li style="list-style: none; display: inline"><ul><li>scanf("%d", i)</li><li>printf("%d", f)</li><li>变量忘记初始化</li></ul></li><li>检查最近改动</li><li>修正一个错误后，搜索是否其他地方有同样的问题</li><li>现在排除，而不是以后</li><li>取得栈轨迹</li><li>打印错误上下文</li><li>键入前读一读，抵抗急于键入的诱惑</li><li>运行前读一读</li><li>休息一下，放松大脑</li><li>把代码解释给别人</li><li style="list-style: none; display: inline"><ul><li>某计算中心咨询台放了个绒毛玩具熊，出现奇怪错误的学生被要求先给玩具熊解释，然后再找人咨询</li></ul></li></ul></li><li>无线索，难办错误</li><li style="list-style: none; display: inline"><ul><li>让错误可重现</li><li style="list-style: none; display: inline"><ul><li>花时间构造输入和参数，让错误能可靠重现：作总结，包装关键步骤，一键重现问题</li><li>如果无法稳定重现，弄清楚为什么不行。即使无法每次重现，如果你能减少重现需要的时间，也能更快解决问题</li><li>设置随机种子</li></ul></li><li>打开程序自身的debug输出</li><li>分而治之</li><li style="list-style: none; display: inline"><ul><li>逐步减少输入，构造报错的最小输入，发现体现错误特征的关键输入</li><li>每个测试都应该有明确目的，用于肯定或否定一个可能出错假设</li><li>在战争和政治中也经常用分而治之的办法...</li></ul></li><li>二分查找</li><li style="list-style: none; display: inline"><ul><li>丢弃一般输入，看是否还有错；递归...</li></ul></li><li>研究错误输出的统计特性</li><li>添加打印语句，使搜索局部化</li><li style="list-style: none; display: inline"><ul><li>用这种插入的打印语句验证你对程序的理解。如果输出量很大，打印前缀或代表性部分</li></ul></li><li>一致性检测的代码</li><li style="list-style: none; display: inline"><ul><li>检测失败，则调用abort，它会导致程序以非正常方式终止，供排错系统分析</li></ul></li><li>写日志</li><li style="list-style: none; display: inline"><ul><li>确保flush日志输出，或者关闭日志文件的输出缓冲(setvbuf(NULL))</li><li>stderr一般是无缓冲的</li></ul></li><li>画图</li><li>使用diff/grep等外部工具</li><li>在简单程序中验证你对程序的理解</li><li>版本控制系统(VCS)，找出最近改动</li></ul></li><li>最后手段</li><li style="list-style: none; display: inline"><ul><li>调试器单步追踪</li><li>函数的实参顺序错了?</li><li>忘记重编译？测试代码有bug？</li><li>休息下，清醒大脑；做一些别的事情；和同事谈谈，请求帮助。答案可能从天而降</li><li>内存泄露</li></ul></li><li>不可重现错误</li><li style="list-style: none; display: inline"><ul><li>变量初始化</li><li>堆内存的写越界</li><li>两次释放同一块内库</li><li style="list-style: none; display: inline"><ul><li>应该开启分配器库的一致性检测开关</li></ul></li><li>一个环境行，而在另一个环境不行</li><li style="list-style: none; display: inline"><ul><li>读哪些文件？文件的权限？</li><li>环境变量？</li><li>搜索路径？</li><li>启动文件？</li></ul></li></ul></li><li>其他人的错误</li><li style="list-style: none; display: inline"><ul><li>首先确认它真的是错误，不浪费作者时间，不损害自己的信誉</li><li>依赖的程序是否是最新版本？</li><li>提交错误报告时，提供最小的测试用例，附上程序版本号、编译系统、操作系统以及硬件信息</li></ul></li><li>strings如果检测到文件是执行文件，则只搜索文本段和数据段</li><li>unix没有文本文件/二进制文件之分；windows有</li><li>应该设法避免错误，在第一次的时候就努力写好；书写良好的代码一开始错误就比较少，剩下的错误也容易查清楚</li></ul><div>21. 程序设计实践，第6章，测试</div></div><div><ul><li>Edsger dijkstra: 测试能够说明程序中有错误，但不能说明其中没有错误</li><li>系统化的进行测试，能够帮我们保证程序一开始就能正确工作，并且演进的过程中也是对的；自动化能帮助我们减少手工操作，鼓励人们更广泛的测试</li><li>产生无错代码的一个途径是用程序生成代码</li><li style="list-style: none; display: inline"><ul><li>如果某些程序的工作已经彻底理解清楚，写代码的方式很机械化，那么就应该把它机械化，即代码生成</li><li>例子：高级语言到汇编；正则；电子表格中的SUM(A1:A50)的记法</li></ul></li><li>编码过程中的测试</li><li style="list-style: none; display: inline"><ul><li>问题发现越早越好，如果你在写代码的时候就系统的考虑过了，就应该立刻验证它</li><li>测试代码边界情况</li><li style="list-style: none; display: inline"><ul><li>测试precondtion, postcondition</li><li>loop invariant</li><li>off-by-one error</li><li>在脑中模拟循环的执行</li><li>如果在边界上能工作得很好，一般在其他地方也正确</li><li>防御性编程，应对非法使用和输入</li><li style="list-style: none; display: inline"><ul><li>空指针</li><li>下标越界</li><li>除0</li><li>检测system call返回值</li></ul></li><li>千年虫是有史以来最大的边界问题</li></ul></li><li>编码中的测试，开销最小，回报丰厚</li><li style="list-style: none; display: inline"><ul><li>写代码的时候你很清楚程序在做什么</li><li>如果等到将来某个时候才崩溃，你可能已经忘记代码怎样工作的了，而在强大的工作压力下把它搞清楚，需要更多的时间，而且理解可能也会不完全</li></ul></li></ul></li><li>系统化测试</li><li style="list-style: none; display: inline"><ul><li>增量测试。测试应该与编码同步进行</li><li>先测试简单部分。即先测试依赖链的上游</li><li>弄清楚期望的输出。部分程序测试很困难：</li><li style="list-style: none; display: inline"><ul><li>编译器。运行编译结果并输出，然后对比输出和已知输出</li><li>数值程序。验证算法特性</li><li>图形程序。读取并校验结果</li><li>如果程序有逆，应该检测求逆后能否得到输入。如加解密、无损压缩、打包拆包</li><li>比较相互独立的实现</li><li style="list-style: none; display: inline"><ul><li>比较竞争软件的输出</li><li>做编译器的时候，一个人汇编，一个人做反汇编，看汇编码是否相同</li></ul></li></ul></li><li>度量测试的覆盖面</li><li style="list-style: none; display: inline"><ul><li>行覆盖</li><li>状态覆盖</li></ul></li></ul></li><li>测试自动化</li><li style="list-style: none; display: inline"><ul><li>手工测试既枯燥又不可靠，因为严格的测试涉及大量测试用例、大量输入，以及比较大量输出</li><li>自动回归测试。将输出与一个正确的旧版本输出对比。因为修改可能破坏旧的东西</li><li style="list-style: none; display: inline"><ul><li>作者在实现awk的时候，附带了1000个测试程序，如果全通过了，则什么都不会输出。这些测试能发现预料之外的错误，避免了awk作者当众出丑</li><li>发现一个错误后，添加一个能发现这个问题的新测试用例</li></ul></li></ul></li><li>测试台</li><li style="list-style: none; display: inline"><ul><li>如果是测试一个纯数值函数，比如数学函数、字符串函数、排序函数，构造测试台的任务很简单：设置输入，调用函数，检测结果</li><li>应该枚举大量的代表性输入</li><li>先编写简单的代码，然后用它做正确性参考</li></ul></li><li>压力测试</li><li style="list-style: none; display: inline"><ul><li>由机器生成的大量输入</li><li>量本身也可能破坏某些东西：输入缓冲区溢出、数组或者计数器溢出</li><li style="list-style: none; display: inline"><ul><li>用scanf("%20s", buf)或者fgets来代替gets</li></ul></li><li>随机输入：应对“人们不会做这种事”的假设</li><li>任何输入，无论是直接还是间接，都应该先检验再使用</li><li>整数的默默溢出可能是灾难</li><li>类型转换导致的溢出</li><li>在文本程序中输入二进制数据可能导致崩溃</li><li>用空文件作为输入</li><li>用特殊文件名测试枚举目录的程序</li><li style="list-style: none; display: inline"><ul><li>bash作者，建立了一个目录，其中包括254个单字符文件名的文件（除开'\0'和'\'这两个非法文件名），然后对这个目录中的文件做模式匹配等测试。多年来这个目录一直是文件树枚举程序的杀手</li></ul></li></ul></li><li>测试秘诀</li><li style="list-style: none; display: inline"><ul><li>将buf的大小临时性的改小，检测溢出情况</li><li>让散列函数返回常数，演示最坏性能</li><li>写一个malloc返回NULL，测试存储器分配失败时的回复策略</li><li>把数组和变量初始化为一个以辨认值而非0（如0xDEADBEEF）</li><li>变更测试用例</li><li>如果错误已经存在，则解决后才能测试后续东西，因为依赖方可能受影响</li><li>在输出中打印测试参数，以便重现</li><li>在不同的机器、操作系统、编译系统上做测试，避免如字节顺序、回车符/换行符、字符编码、库/文件头等特殊属性的依赖</li></ul></li><li>黑盒测试</li><li style="list-style: none; display: inline"><ul><li>由程序实现者或其他可以解除源码的人做的测试都称为白盒测试</li><li>做测试的原因是为了发现错误，而不是为了表明程序可以工作，所以，测试应该是恶毒的；发现错误，不应该恐慌，它是你的测试方法有效的证明</li><li>测试边界条件</li><li>大量非法、随机的输入</li><li>beta测试是发布前请用户介入的方式，但不应该用来代替彻底测试</li><li>交互程序的测试特别困难，可用技术：</li><li style="list-style: none; display: inline"><ul><li>捕捉用户真实输入，然后播放</li><li>建立描述事件序列和时间的脚本语言</li></ul></li><li>对测试代码的测试</li></ul></li><li>例子，对马尔科夫链的测试</li><li style="list-style: none; display: inline"><ul><li>测试用例1：几个小文件，内容是"a", "ab", "abc", "abcd", "abcde"，他们的输出都应该是本身</li><li>测试用例2：写awk脚本，验证输出的词必然也包含在输入中</li><li>测试用例3：统计性质。输入时"abcabc...abd..."，每10个"abc"才有一个"abd"，统计输出中的"c"应该是"d"的10倍</li></ul></li><li>对于测试，唯一的、最重要的规则是：必须做</li></ul><div>21. 程序设计实践，第7章，性能</div></div><div><ul><li>只在程序真的非常慢，能够保证正确性、健壮性、清晰性的情况下提高性能的时候，才考虑优化</li><li>优化的第一要义：不优化</li><li>一旦程序足够快了，停止优化</li><li>Don knuth: 一个程序中少于4%的部分占用了一半以上的时间</li><li>当一个函数单独成为瓶颈时，有两条路：</li><li style="list-style: none; display: inline"><ul><li>采用更好的算法来改进函数</li><li>删掉这个函数，重写调用方</li></ul></li><li>加速策略</li><li style="list-style: none; display: inline"><ul><li>在优化之前，先确认，它确实太慢，再弄清楚它慢在哪里</li><li>使用更好的算法或数据结构。这一步是跨机器、跨语言的</li><li>代码调优</li><li>让编译器优化</li><li>把焦点放在hotspot</li><li>到底应该在优化上面投入多少时间？在加快速度上面所化的时间不应该超过加速后的程序在整个生命周期中节省的时间</li><li>存在竞争的软件，游戏、编译器、编辑器、电子表格、数据库，他们在商业上的成功可能就因为性能上的差别</li><li>修改后确保性能确实得到改进；但要提防两个优化互相影响</li></ul></li><li>代码调优</li><li style="list-style: none; display: inline"><ul><li>编译器能为我们优化，同时，你的调整可能妨碍优化，因此，调整过后一定要测试，验证其作用</li><li>缓存频繁访问的值。如inline caching</li><li>写专用存储分配器。考虑分配、释放模式固定的分配器，以及块大小固定的分配器(freelist)</li><li>buffered IO。注意写关键数据时的flush，避免crash造成的应用层buffer数据丢失</li><li>特化。partial evaluation，如图像处理、正则当中的JIT</li><li>预计算。查表</li><li>使用近似值。查表</li><li>使用低级语言。用程序员时间来换</li><li>机器相关代码。如SSE，但破坏了移植性，也带来了维护困难</li></ul></li><li>空间效率</li><li style="list-style: none; display: inline"><ul><li>当今主存和二级存储器都便宜得令人惊讶，故，空间优化的要义仍然是：不优化</li><li>如果内存占用过多，造成反复的paging，性能又会极差</li><li>C/C++的位域是高度不可移植的，请改用位运算</li><li>重新计算，避免存储。时间换空间，这里善用封装</li><li>采用文本形式存储和转换，因为它易读、可移植，可以被各种工具处理。它和二进制格式的速度差异可能没那么大</li><li>对图像进行无损压缩能换来空间效率，但付出时间，取舍依据场合。比如为了利用网络带宽，可能空间效率优于时间</li></ul></li><li>优化的步骤：</li><li style="list-style: none; display: inline"><ul><li>测量</li><li>找到回报最高的地方，修改，验证，再测量</li><li>足够快了，停下来</li><li>保存初始版本，以对比正确性</li></ul></li></ul></div><div>21. 程序设计实践，第8章，移植性</div><div><ul><li>编程很难，所以，理想的情况下，希望把程序迁移到另一个编译系统、操作系统、处理器上时，可以什么都不该，或者改动尽可能少。这里，这种修改越容易，我们就说它移植性越强</li><li>应该让软件只依赖于它必须依赖的各种标准、接口和环境的交集中，不要为了移植性而写特殊的代码，相反，应该修改软件本身使他总是在不同环境的交集中；如果不可移植的代码不可避免，用抽象来封装它，使他的影响局部化。这样，你的代码在被移植后仍将清晰、通用</li><li>语言</li></ul><ul><li style="list-style: none; display: inline"><ul><li>二进制文件不可能很容易的移植，但源码可以</li><li>标准有时会故意不定义某些东西，如char的符号和大小，或者政治、技术上的妥协</li><li style="list-style: none; display: inline"><ul><li>如果char是无符号的，char c = getchar(); c == EOF，后者永远为false。故，<b>不要将char与EOF做比较</b></li></ul></li><li>1988年的ANSI C出台以前，C一直没有标准化。<b>标准化通常要等到语言已经有了多个不相容的实现，有了进行统一的需求的时候才做；同时语言必须被广泛接受，值得付出标准化的代价</b></li><li>类似near/far这样需要咨询语言专家才能确定是否属于标准的特性，避开它</li><li>C/C++对基本类型的大小没有明确定义。考虑int32_t、uint32_t等</li><li>Java明确定义了所有类型的大小，如byte是8位，char、short是16位，int是32位，long是64位。没有unsigned的概念，所有类型都是有符号的，只有char是无符号</li><li>求值顺序</li><li style="list-style: none; display: inline"><ul><li>C++对求值顺序定义很模糊，所以有下面的问题：</li><li style="list-style: none; display: inline"><ul><li>a[i] = ++i，不知道哪个元素被赋值</li><li>printf("%c %c", getchar(), getchar())，不知道第一个字符输出在前还是在后</li><li>printf("%f %s\n", log(-1), strerror(errno))，不知道errno有没有被设置</li></ul></li><li>Java对求值顺序有严格定义，表达式和副作用都要求从左到右。但考虑到将源码从Java移植到C/C++中的可能性，建议代码不要依赖于求值顺序</li></ul></li><li>语言间的转换是对移植性的极端测试</li><li>用多个编译器实验</li></ul></li><li>头文件和库</li><li style="list-style: none; display: inline"><ul><li>C/C++/Java的IO库，虽然不是语言的一部分，但是他们被期望作为支持语言的环境的一部分来使用，但是他们通常又要处理与系统相关的问题，所以很容易成为不可移植问题的避风港</li><li>strdup不是ANSI C的一部分</li><li>类似stdio.h的文件，内部需要用类似#ifdef __cplusplus、extern "C"的方法，兼容旧C、ANSI C、C++等多个语言</li><li>基于静态链接库的特点（只链接未定义的symbol），用户可以通过自定义函数的方法来覆盖标准库函数</li><li>ANSI C的signal定义了6个信号，posix定义了19个，而大部分的unix系统支持32+个信号，因此，一旦使用了非ANSI/posix的信号，就可能成为移植问题</li></ul></li><li>程序组织</li><li style="list-style: none; display: inline"><ul><li>达到可移植性的方式有两种</li><li style="list-style: none; display: inline"><ul><li>联合：通过条件编译等方式，根据不同的环境做特殊处理，提供所有系统的并集的能力。功能强大，但是安装复杂、维护困难，测试也不容易</li><li>交集：只用所有环境共有的特征。限制了系统的功能、性能，但更容易维护</li></ul></li><li>无论如何，尽量避免条件编译</li><li style="list-style: none; display: inline"><ul><li>更不要将条件编译和if等控制流混在一起</li><li>类似#ifdef NDEBUG等条件编译，尽量利用编译期的if (!DEBUG)来代替</li><li>如果需要移植到新环境，比起拷贝程序副本，再修改，更应该修改源文件以适应新环境，这样才能做到SPOT/DRY，不至于需要维护两个分支</li><li>条件编译的代码测试时，需要修改宏定义然后重新编译，才能覆盖不同的分支</li><li>代码的#ifdef越少，它的配置和安装才更简单、更可靠，移植性才更强</li></ul></li></ul></li><li>隔离</li><li style="list-style: none; display: inline"><ul><li>把对系统的依赖限制在独立的文件里，隐藏在接口的后面</li><li>Java等基于虚拟机的语言，其移植性是个好例子</li></ul></li><li>数据交换</li><li style="list-style: none; display: inline"><ul><li>比起二进制格式，文本格式才有可移植性，因为前者需要专门的工具才能操作，对版本有要求。另外，大量的网络协议是采用的文本格式，为了工作在其之上，你也必须使用文本</li><li>文本格式的一个缺陷：换行符。windows，\r\n；unix，\n；mac，\r。HTTP为了兼容各系统，也采用和windows一样的\r\n作为换行符</li><li>注意fopen时用"rb"</li></ul></li><li>字节顺序</li><li style="list-style: none; display: inline"><ul><li>总是以固定的字节顺序进行short/int/long/float/double的序列化，如big-endian，目标系统的实际顺序可以运行时判断（付出一点性能代价）</li><li>Java没有字节顺序问题，Serializable包办了</li><li>另外一种屏蔽字节顺序的方式是，用文本格式替代二进制格式做序列化</li></ul></li><li>可移植性和升级</li><li style="list-style: none; display: inline"><ul><li>系统软件的升级可能导致与现有软件不可兼容</li><li>注意维持程序和数据的版本兼容。很多软件的新版本没能处理好旧数据</li></ul></li><li>国际化</li><li style="list-style: none; display: inline"><ul><li>不要假定ASCII</li><li>不要假定英文或者中文</li><li>将所有待国际化的文本汇总到一处，用ID来索引</li><li>mm/dd/yy的日期格式有国际化问题</li><li>货币符号有国际化问题</li></ul></li></ul><div>21. 程序设计实践，第9章，记法</div></div><div><ul><li>采用合适的语言可能使某个程序变得容易很多</li><li>程序员的武器库里，除了C/C++/Java这样的通用目的语言，还有shell、python等脚本语言和awk、sed、regex等DSL</li><li>正则表达式使我们以非常紧凑的形式定义一个字符串类</li><li>如果你发现自己为某些平庸的任务写了太多的代码，或者你需要表述的过程遇上了大麻烦，那么你可能正在使用一种不合适的语言</li><li>如果合适的语言不存在，那么自己创建一种，printf的format串就可以看做是一种简单的描述打印类型、对齐、宽度的语言</li><li>我们希望对计算机说“请解决我的问题”，这与为完成任务实际需要做的事之间，永远有一条鸿沟，这条鸿沟越窄越好，那样我们更容易说出我们的要求，并且更不容易犯错。这就是DSL的目的</li><li>C++的iostream和Java的java.io类都不好使，因为他们只描述了类型，却不涉及对齐、宽度，所以printf更易用</li><li>类似的，当我们在C语言中想要做序列化的时候，可以像printf一样用format串简单的描述我们的包格式</li><li>Awk采用tree-walking的方式解释执行</li><li>用代码生成器的方法，parse元数据，生成代码，是SPOT的实践</li><li>带语义的注释：doxygen/java/python（literate programming，文档程序设计）、某些dbc框架(契约编程)</li><li>在C语言中，宏可以被用于生成代码，如图像处理函数、光栅器，既能用一份代码包括不同的情况，又不响应编译器优化。该用途在C++中完全可以用模板来代替</li><li>在正则表达式、图像处理中，针对特定的模式，应用JIT技术</li><li>《方法论》：我发现的每个真理都变成了一条规则，它们帮我在将来发现其他东西</li></ul></div><div><br>
</div><div>21. 杂项</div></div><div><ul><li>并发不一定需要多线程，如io multiplexing，strtok；并发不一定是并行的，如单核型多线程</li><li>strtok的不可重入性，本质上是因为全局变量是反并发的(anti-concurrent)，既然反并发自然不是thread-safe的</li><li>不定长序列随机选1个的算法(适用于linked list的n选1): v = 0; n = 0; foreach(node) { v = rand() % ++n == 0 ? node.value : v; }</li><li>从集合中随机选n个的算法</li><li style="list-style: none; display: inline"><ul><li>random_shuffle过后取长为n的前缀</li><li>在前缀n上使用random_shuffle的算法: for (int i = 0; i < n; ++i) swap(a[i], a[rand(i, len(a))]);</li></ul></li><li>awk的关联数组支持任意多维，如"dict[a,b,c,d]"，等价于"dict[sep.join(a,b,c,d)]"</li><li>关于scanf中的*，表示匹配输入串，但不写入实参地址：</li><li style="list-style: none; display: inline"><ul><li>scanf("%*d %*s %d", &i)，跳过前两个格式串，只将第三个格式串parse后写入实参</li></ul></li><li>关于printf中的*，用法是"%.*s"，表示输出变长字符串，而不是找结束符:<br>
</li><li style="list-style: none; display: inline"><ul><li>printf("%.*s", 2, buf)，输出buf中的头两个字符。等价于printf("%.2s", buf)</li></ul></li><li>windows中的文本文件，即没有加"b"的方式读写文件</li><li style="list-style: none; display: inline"><ul><li>写的时候，会将\n变成\r\n；读的时候，会将\r\n变成\n，且会将\x1a看做EOF</li><li>二进制写0~255到文件，再读：</li><li style="list-style: none; display: inline"><ul><li>都没问题</li></ul></li><li>文本写0~255到文件，再读:</li><li style="list-style: none; display: inline"><ul><li>写：文件会有257个字节，因为在写\x0a的时候，实际会写\x0d\x0a</li><li>读：只能读出27个字节，因为把\x1a看做结尾</li></ul></li><li>stdin和stdout、stderr都是文本方式打开的，故在windows下用管道处理二进制文件会有问题</li></ul></li><li>fclose可能失败(返回EOF，并设置errno)</li><li>有符号数的>>到底是算数(添符号位)还是逻辑移位，在C/C++中没有规定</li><li>C/C++的位域是高度不可移植的，请改用位运算</li><li>C/C++中的char，标准没有规定有符号还是无符号，而且也没要求必须8位。C/C++只要求sizeof(char)<=sizeof(short)<=sizeof(int)<=sizeof(long)；sizeof(float)<=szieof(double)，同时，char至少8位，short、int至少16位，long至少32位</li><li>C/C++的求值顺序规定：分号前，或者函数被实际调用前，所有实参的副作用(函数调用和i++的自增等)必须完成；&&和||是从左到右的短路逻辑；?:只有真值的分支被执行</li><li>虽然echo命令在最初只是简单的输出字符串，但现在已经具有解释的语义了，会将'\n'当做换行符，类似printf</li><li>注意在va_arg的时候用int去提取char/short，因为C语言对...的默认规则</li><li>考虑同时使用三种断言：</li><li style="list-style: none; display: inline"><ul><li>D_ASSERT，只在debug版生效，检测逻辑错误，避免运行时开销，用在访问频繁的地方</li><li>R_ASSERT，release版也生效，抛出LogicError的异常，用于访问不频繁的逻辑错误检测</li><li>ENSURE，运行时错误检测，抛出RuntimeException，用于输入验证、系统调用等</li><li>LogicError，捕获上下文，捕获调用栈，发送minidump给developer，然后结束程序</li><li>RuntimeException，捕获上下文，debug版捕获调用栈，外层捕获异常后可以继续执行</li></ul></li><li>对于isdigit、isalpnum的实现，当然可以每个给char数组作为表；但其实，每种isxxx只需要一位即可，因此，实现为#define isdigit(c) (inttable[c] & DIGIT)</li><li>位域访问会被编译器翻译成位运算，由于有界，因此可能更慢。比如s.b3 = i，如果直接使用位运算，我们知道i不会越界，因此无需钳位，但编译器的bit field却不知道，所以需要对i钳位</li><li>Brian Kernighan提出和实现的awk叫BWK awk；在BWK awk开源之前，gnu实现了开源版的gawk；linux上自带的是mawk，是一种基于字节码的非常快的awk实现<br>
</li></ul><div>21. 编程珠玑，第4章，编写正确的程序</div></div><div><ul><li>当编写复杂的算法时，总是使用验证方法来增强自己对程序正确性的信心</li><li>正确性验证(验证手段可以是assert)：</li><li style="list-style: none; display: inline"><ol><li>验证pre condition</li><li>根据pre condition推导出initial invariant的正确性</li><li>进入循环</li><li>在循环体的尾部验证loop invariant的正确性</li><li>证明循环能结束，即halting proof</li><li>结束循环</li><li>验证post condition</li></ol></li><li>验证语言常用于程序代码初次完成以后，在进行初次模拟的时候开始使用</li><li>调试过程中，同时修正错误代码和错误断言：总是保持对代码的正确理解，不理会“只要能让程序工作，怎么改都行”的催促</li><li>熟悉验证技术的专业程序员，甚至会遇到，“困难”的代码总是一次就可以正确运行，“容易”的部分反而出错的情况</li></ul><div>21. 编程珠玑，第5章，编程小事</div></div><div><ul><li>程序员是乐观主义者，他们期望编写好的代码插入系统中就能工作；但实际上，99.9%的情况下发生的事情都是，函数出错，然后在巨型系统的迷宫中调试这个小小的函数</li><li>使用小型的测试数据驱动的console程序来验证概念和证明函数的正确性，在这种程序中，使用print甚至比复杂的调试器更有效</li><li>发布版的产品中完全没有断言是不靠谱的，Tony hoare比喻为操练时穿着救生衣、下水却脱掉的水手</li><li>为什么相信我们的程序是正确的？</li><li style="list-style: none; display: inline"><ul><li>利用验证技术分析了算法的正确性，并用assert确保无误</li><li>用测试数据自动化的测试了程序</li><li>分析的时空复杂度与测试结果吻合</li></ul></li><li>小故事：IBM的Yorktown heights研究中心的一个程序员，安装好新的工作站后，坐着时一切正常，站着就不能登录系统</li><li style="list-style: none; display: inline"><ul><li>原因：坐着时盲打，站着是眼睛盯着键盘输入，而键盘上有两个键帽位置反了...</li></ul></li><li>小故事：芝加哥的银行系统正确运行了好几个月，但第一次用于国际数据就意外退出了</li><li style="list-style: none; display: inline"><ul><li>原因：厄瓜多尔的首都基多（Quito）被解释为quit...</li></ul></li></ul><div>21. 编程珠玑，第6章，程序性能分析</div></div><div><ul><li>许多程序有严格的时间要求，包括实时程序（游戏）、数据库和交互式软件（常驻，如操作系统和QQ）</li><li>效率的一个优点是可度量：每个人都会认可程序块了2.5倍，但是，讨论用户界面却会陷入个人喜好之争</li><li>虎书的作者，将重力场中多个物体相互作用的经典"n体"问题加速了400倍，文章是”An efficient program for many-body simulations“。加速比：</li><li style="list-style: none; display: inline"><ul><li>算法和数据结构——二叉树使得复杂度由O(n^2)减少到O(n*logn)。x12</li><li>算法调优——使用较大时间步进；在低层上对靠得近的物体使用小步进。x2</li><li>数据结构重组——产生适合树算法的簇。x2</li><li>系统无关的代码调优——float替换double。x2</li><li>系统相关的代码调优——用汇编重写关键函数。x2.5</li><li>硬件——换快一倍的机器。x2</li></ul></li><li>根据上面的案例，引申出优化的层级（实际上可以从软件结构直到晶体管）：</li><li style="list-style: none; display: inline"><ul><li>问题定义</li><li style="list-style: none; display: inline"><ul><li>追求快速的系统，可能在定义该系统需要解决的问题时就已经注定成败了</li><li>良好的问题定义可以避免用户对问题需求的过高估计</li><li>问题定义和程序效率之间具有复杂的相互影响</li><li style="list-style: none; display: inline"><ul><li><b>良好的错误恢复能力会使编译器运行得慢一些，但由于减少了总的编译次数，因此缩短了总的时间</b></li></ul></li></ul></li><li>系统结构</li><li style="list-style: none; display: inline"><ul><li>在构建出整个架构后，需要进行”粗略估算“，证明程序的性能在正确的范围内</li></ul></li><li>算法和数据结构</li><li style="list-style: none; display: inline"><ul><li>O(n^2)、O(n^3)的算法很有可能可以用分治法（如果子问题相互独立，甚至还可以DP）将复杂度从n减少到logn</li></ul></li><li>代码调优</li><li>系统调优</li><li style="list-style: none; display: inline"><ul><li>改变系统所依赖的软件往往比改变系统本身更容易</li><li>可以更换更快的数据库吗？</li><li>另一个操作系统是否更适合？</li><li>所有编译器优化开关都打开了吗？</li><li>更新版本的框架？</li></ul></li><li>硬件</li><li style="list-style: none; display: inline"><ul><li>更大的内存？更快的时钟频率？更多的核心？</li><li>将CPU的操作转移到声卡、显卡以及其他的专用处理器上？游戏开发者常用技巧以及DSP在家电上的应用</li></ul></li></ul></li><li>如果仅需要较小的加速比，就能使性能达到预期：对效果最佳的层面做改进</li><li>如果需要较大的加速比：对多个层面做改进</li><li>算法加速并不一定是独立于硬件的</li><li>程序的其他度量包括：容错性、可靠性、安全性、开销、开销/性能、精度，以及对用户错误的健壮性。仅当性能在基本可接受的范围内时，前面几点比效率更重要（如果游戏的PFS不超过1，那么此时性能就是关键因素了）</li></ul><div>21. 编程珠玑，第7章，粗略估算</div></div><div><ul><li>基本技巧：</li><li style="list-style: none; display: inline"><ul><li>两个答案比一个答案好。用多种方法估算结果</li><li>快速校验</li><li style="list-style: none; display: inline"><ul><li>How to solve it中介绍了”单位校验“</li><li>加法的单位应该相同，比如”1米+2米“</li><li>乘法的单位是各式的乘积，比如”1米*1米=1米^2“</li></ul></li><li>经验法则</li><li style="list-style: none; display: inline"><ul><li>72法则：(1+x/100)^(72/x)==2，例如年利率6%，12年可以翻倍</li><li>pi秒就是一纳世纪：因此100年=3.15*10^9秒，即1年=3.15*10^7秒</li></ul></li><li>实践。经常联系估算：</li><li style="list-style: none; display: inline"><ul><li>某只箱子的包装塑料膜上有多少个泡</li><li>公司的人每天花多少时间上午茶、午餐、使用打印机等？消耗了多少工资？</li><li>成都三环路有多长？步行需要多久？</li></ul></li></ul></li><li>安全系数</li><li style="list-style: none; display: inline"><ul><li>将你的估算时间乘以2或更大的因子</li></ul></li><li>little定律</li><li style="list-style: none; display: inline"><ul><li>队列中物体的平均数量等于进入速率乘以平均停留时间（假设状态平衡，进入速率等于离开速率）</li><li>例子：人均年龄的80岁的话，那么，死亡率是1.25%</li></ul></li></ul><div>21. 编程珠玑，第8章，算法设计技术</div></div><div><ul><li>最大子向量问题的DP算法，复杂度O(n)</li><li>对于需要求数组中部分段累积的问题，可以先预计算一个数组b，b[i]=sum(a[0...i])，因此sum(a[i...j])=b[j]-b[i]。用来解的问题：</li><li style="list-style: none; display: inline"><ul><li>直线公路上，任意两村的距离</li><li>和最接近实数t的子数组：排序b，然后找两元素之差为t；特例，当t==0时，就是有序数组b中最接近的相邻两项</li></ul></li></ul><div>21. 编程珠玑，第9章，代码调优</div></div><div><ul><li>当malloc成为瓶颈时，为分配最多的固定size的内存块，使用基于freelist的allocator</li><li>如果瓶颈在IO上，减少计算时间没有用</li><li>如果瓶颈在内存访问上（reference pattern特殊，或者working set过大），减少计算时间受益很小</li><li>在C语言中，定义在文件中的短函数，对于同一个编译单元的其他函数来说，它相当于是内联的。因此，头文件中的static短函数定义，相当于inline，因此，在性能上完全可以取代对应的宏</li><li>哨兵可以用于减少边界判断</li><li style="list-style: none; display: inline"><ul><li>比如，顺序搜索，将最后一个元素设置为哨兵，则不用检测数组下表越界</li></ul></li><li>Don knuth: 不成熟的优化是万恶之源</li><li>效率问题可以用很多方法来解决，只有确信没有更好的解决方案时才考虑代码调优</li><li>代码调优是双刃剑，可能优化也可能劣化，因此，修改后，一定要重新profiling。Jurg Nievergelt：玩火者，小心自焚</li></ul><div>21. 编程珠玑，第10章，节省空间</div></div><div><ul><li>程序变小过后，加载更快，也更可能放入cache</li><li>网络传输需要的时间和数据大小成正比</li><li>特殊的机器内存仍然很小，比如家电的DSP</li><li>巨型机用来解决巨大规模的问题，也需要小心使用内存</li><li>小故事：Dennis Ritchie和Ken Thompson最初在只有8K个18位字的机器上开发出了Unix，空间约束迫使他们的设计更优雅</li><li>小故事：Fred brooks为某公司编写薪水程序，发现规律很奇怪，同时又无法将表格放入内存，研究立法机构的纪要过后，发现，其实表格的数据是由扣除周税后的简单函数生成的，最终完全不需要查表，靠两个函数调用计算薪水。这里的空间节省自正确的问题分析</li><li>小故事：1984年的Apple macintosh，只有128KB RAM，却具有惊人的用户界面和强大的软件集，它的大部分经过精确调优的系统调用都由汇编手工实现并被放在一个64KB的ROM中，他们估计其大小只有高级语言编译器生成的代码的一半</li><li>稀疏矩阵的行数组+列链表表示法，可以近似的看做hash()==row()的开链法的hash表</li><li>数据空间技术：</li><li style="list-style: none; display: inline"><ul><li>不存储，重新计算。时间换空间。例如测试的海量输入数据来自生成程序，而非预先存储。infinity等分型游戏的世界</li><li>稀疏矩阵，以及flightweight等共享模式</li><li>数据压缩</li><li style="list-style: none; display: inline"><ul><li>将行列编码在一个整数中</li><li>基于信息论的无损压缩，如gif</li><li>有损压缩和采样。比如控制采样频率的音频。有损的jpeg和mp3</li></ul></li><li>分配策略</li><li style="list-style: none; display: inline"><ul><li>动态分配。比如，以换行符来存储多行文本，而不是用等长二位矩阵</li></ul></li><li>垃圾回收</li><li>距离矩阵的对称存储</li><li>代码复用。DRY避免重复的同时，也减少了空间。其实是reverse inline。解释器、DSL也归于此类</li><li>使用低级语言。如果用汇编和链接命令的话，可以更精准的控制链接后尺寸</li><li>编译器选项可以控制输出的大小</li></ul></li><li>trade off：有时程序员必须牺牲程序的性能、功能以及可维护性，来换取内存，这种极端的决策只应该在已经研究过所有办法后才做出</li><li>对于现代程序，庞大的常常不是你所编写的代码，而是你所使用的库/框架代码</li></ul><div>21. 编程珠玑，附录</div></div><div><ul><li>关于设计过程的建议</li><li style="list-style: none; display: inline"><ul><li>解决正确的问题</li><li>探索所有可能的方案</li><li>观察数据</li><li>粗略估算</li><li>利用对成型</li><li>基于组件设计</li><li>建立原型</li><li>必要时进行trade off</li><li>保持简单</li><li>追求优美</li></ul></li><li>快排的时空复杂度</li><li style="list-style: none; display: inline"><ul><li>平均：时间，O(n*logn)；空间，O(logn)的栈</li><li>最坏：时间，O(n*n)；空间，O(n)的栈</li></ul></li><li>利用malloc(n) - malloc(n)的方法，可以粗略估计allocator对于payload==n时的overhead（主要是internal fragmentation）</li><li>对于复杂的if else序列，应该根据命中几率来重排</li><li>对于频繁调用的函数，如果参数空间够小（或者经过简单映射后的参数空间够小，比如hash(k)），可以以k或者h(k)为索引查表，以达到空间换时间的目的</li><li>一个对磁盘上的超大矩阵转置的算法（不是最快的，但新颖）：</li><li style="list-style: none; display: inline"><ol><li>遍历矩阵的每行，将每项v转换成row,col,v的行输出。awk脚本</li><li>读取上面的输出，以col为主关键字，row为次关键字，排序。sort命令，即sort row; 再sort col</li><li>读取输出，逐行提取v后以行遍历填入目标矩阵。awk脚本</li></ol></li><li>如果用公式对应的函数来模拟大型表格，无法满足精度需要，可以再填一个小表来矫正函数返回值。这里的用法就是公式+查表来模拟高精度的大表</li></ul><div>22. 算法导论</div></div><div><ul><li>一个算法包含对自身的调用时，其运行时间可以用递归式（recurrence）来表示。下面是解递归式的三种方法：</li><li style="list-style: none; display: inline"><ul><li>代换法（substitution method）：先猜测某个界，然后用数学归纳法证明该猜测的正确性</li><li>递归树方法（recursion-tree method）：将递归式转换成树形结构，树中的结点代表不同递归层次的代价，这样可以分别求出每层的总代价，进而得出整棵树的代价，即算法的界，最后交由带代换法证明（数学归纳）</li><li>主方法（master method）：给出递归式的界</li></ul></li><li>hash表的开放地址法（open address）</li><li style="list-style: none; display: inline"><ul><li>插入：检测所有的备选位置（h(k, 0), h(k, 1), h(k, 2)...）直到发现已经存在或找到一个空位置</li><li>查询：检测所有的备选位置，直到发现或者找到一个空位置（不存在）</li><li>删除：不能简单的将对应位置赋为nil，因为会打断后续查询和插入，可能需要引入DELETED的概念</li><li>总之，由于删除比较麻烦，所以open address法更适合用在只有插入和查询的情况下，实现简单性能也不错</li></ul></li><li>分治和和动态规划</li><li style="list-style: none; display: inline"><ul><li>有很多算法在结构上都是递归的，为了解决一个给定问题，算法需要一次或多次递归调用自身来解决相关子问题</li><li><b>分治法</b>（divide-conquer-combine）：将原问题划分成n个独立子问题，递归解决子问题后再将结果合并。三个步骤：</li><li style="list-style: none; display: inline"><ol><li>分解（divide）：将原问题划分成子问题</li><li>解决（conquer）：递归解决子问题。<b>如果子问题足够小，直接给出答案（这是关键）</b></li><li>合并（combine）：合并子问题的解</li></ol><ul><li>例子：</li><li style="list-style: none; display: inline"><ul><li>归并排序</li></ul></li></ul></li><li><b>动态规划</b>（dynamic programming）：和分治法一样，也是通过组合子问题的解从而解决整个问题的；区别是，如果子问题不互相独立，比如，各个子问题包含公共的子子问题，那么，分治法就会重复求解公共子问题；动态规划将子问题的解保存在表当中，从而避免了重复计算；根据父子问题的具体依赖关系，结果表可能会尽快丢弃不再需要的过小的子问题解</li><li style="list-style: none; display: inline"><ul><li>动态规划通常用于最优化问题，此类问题可能有多个解，我们希望找出最优（最大或最小）的解。（如非最优，可以直接gready求解）</li><li>两个要素：</li><li style="list-style: none; display: inline"><ul><li>最优子结构：如果问题的最优解中包含了子问题的最优解，则该问题具有最优子结构。当一个问题具有最优子结构的时，提示我们DP可能有用</li><li>重叠子问题：子问题空间很小，即解原问题的递归算法可能反复解同样的子问题，而不是一直产生新的子问题。相反，适合分治法的问题，总是在产生新的子问题，比如megeSort</li></ul></li><li>步骤：描述最优解的结构——>递归定义最优解的值——>自底向上的计算最优解的值——>根据结果构造最优解</li><li>例子：</li><li style="list-style: none; display: inline"><ul><li>最长公共子序列（longest common subsequence）：一个序列的子序列就是去掉0个或多个元素后（可以不连续）的序列，找出X、Y的最长公共子序列</li><li style="list-style: none; display: inline"><ul><li>递归最优解：L(a(n), b(n)) = a[n-1]==b[n-1]? L(a(n-1), b(n-1)) : max(L(a(n-1), b(n)), L(a(n), b(n-1)))</li></ul></li><li>最长递增子序列（longest increasing subsequence）：序列(a1, a2, ...an)中，找到最长递增子序列（和上题一样，不要求子序列元素连续）。例，炮弹拦截问题...</li><li style="list-style: none; display: inline"><ul><li>递归最优解：L(i)=1+max(L(0),L(1)...L(i-1))</li></ul></li><li>多副本背包问题：背包重量W，有n个物品，每个重量wi价值vi，每个物品不限制个数，求最大价值</li><li style="list-style: none; display: inline"><ul><li>递归最优解：V(w)=max{V(w-wi)+vi}。即子问题是放入某物品后，剩余空间怎么安排</li></ul></li><li>单副本背包问题（0-1背包问题）：每个物品只能拿一件</li><li style="list-style: none; display: inline"><ul><li>递归最优解：V(w,i)=max(V(w-wi, i-1)+vi, V(w, i-1))</li></ul></li><li>和最大的连续子序列：</li><li style="list-style: none; display: inline"><ul><li>递归最优解：endwith(i) = endwith(i-1) > 0 ? endwith(i-1)+v(i) : v(i)，再求max(endwith(1), endwith(2), ...endwith(n))</li></ul></li><li>加入最少字符构成回文：</li><li style="list-style: none; display: inline"><ul><li>法1：加入的字符数是 length(s) - LCS(s, reverse(s))</li><li>法2：out(s) = s[0]==s[-1] ? (s[0] + out(s[1:-1]) + s[0]) : min(out(s[1:]), out(s[0:-1]))，用备忘录法避免重复计算</li></ul></li><li>最长相同连续子序列：在S中找连续子序列s1和s2，使得s1==s2</li><li style="list-style: none; display: inline"><ul><li>后缀数组（Trie tree），然后O(n)的遍历，找最长的相邻串公共前缀</li></ul></li><li>最长不重复连续子序列：在S中找连续子序列s1，使得s1中没有相同字符</li><li style="list-style: none; display: inline"><ul><li>int maxL = 0, L = 0; int place[256]={-1,...}; for (int i = 0; i < len(S); ++i) { if (place[S[i]] == -1) ++L; else { L = i - place[S[i]]; } place[S[i]] = i; maxL = max(maxL, L)}</li></ul></li></ul></li></ul></li><li><b>备忘录</b>（memoize）</li><li style="list-style: none; display: inline"><ul><li>DP的变形，递归定义最优解的部分和DP一样</li><li>DP是自底向上，用数组+迭代，求出所有子问题的解</li><li>备忘录是自顶向下，用递归+hash表，只需要求解用到的子问题。由于是自顶向下，而且是直接递归，比DP的实现更自然</li><li>如果所有子问题都需要求解，则DP比备忘录快一个常因子，因为递归和hash表开销；如果最优解无需求解所有子问题，则备忘录可能更快，因为它只求需要的子问题的解</li><li>例子：</li><li style="list-style: none; display: inline"><ul><li>背包问题，因为重量不连续，所以可能不需要求解所有子问题</li></ul></li></ul></li><li>分支和动规对比的一个典型案例就是fibonacci的递归法和迭代法</li></ul></li></ul><div>22. 浪潮之巅</div></div><div><ul><li>好的总结，100P：<a href="http://www.moways.com.sg/glcb_image/dsh/20110823lczd.pdf" target="_blank">http://www.m<wbr>oways.com.sg<wbr>/glcb_image/<wbr>dsh/20110823<wbr>lczd.pdf</a></li><li>AT&T（American Telephone Telegraph，美国电报电话公司，前身是贝尔公司）</li><li style="list-style: none; display: inline"><ul><li>1875年，贝儿和沃森发明电话</li><li>1877年，贝尔公司，1892年将生意扩展到美国中部，1915年，生意扩展到全国，1927年，扩展到欧洲</li><li>1880年，长途电话业务开通</li><li>1916年，贝尔公司进入道琼斯指数，今天，当时的20家公司只有通用电气还在（大多在二战前的金融危机中消失了）</li><li>1913年，和美国政府达成第一次反垄断协议</li><li>1925年，贝尔实验室（Bell laboratories）。历史上最大、最成功的私有实验室，AT&T将电信业的垄断利润的3%投入到贝尔实验室的研发工作中</li><li style="list-style: none; display: inline"><ul><li>射电天文望远镜，晶体管，数字交换机，Unix，C语言，电子的波动性，信息论，第一课通信卫星，第一条商用光纤</li><li>11位诺贝尔奖获得者</li><li>2万人，22亿美元每年的经费</li></ul></li><li>1982年，美国司法部打赢长达8年的针对贝尔电话公司的反垄断官司</li><li>1984年，因反垄断法，贝尔公司被拆分成7个小的贝尔公司和AT&T。7个baby bell从事市话业务，AT&T从事长途和通信设备制造</li><li>1996年，为了得到另外两家长途电话公司MCI和Sprint的通信设备订单，AT&T分家成从事电信服务业务的AT&T、从事设备制造业务的朗讯、和从事计算机业务的NCR</li><li>朗讯（Lucent technologies）</li><li style="list-style: none; display: inline"><ul><li>1996年，朗讯由摩根士丹利（Morgan stanley）领衔上市，市值达到180亿美元。员工和华尔街因为股票收益</li><li>朗讯继承了贝尔实验室的名字，但失去了AT&T的垄断电信业务利润后，朗讯的贝尔实验室被迫放弃基础研究，开始从事能尽快赚钱的研究</li><li>朗讯为了盈利，借钱给各公司来买朗讯的设备，随着2000年互联网泡沫破裂，朗讯借出去的钱成了净亏损，股价下降</li><li>2000年，拆分无线设备部门Avaya出去，独立上市</li><li style="list-style: none; display: inline"><ul><li>编程珠玑作者Jon bentley，就先后经历了贝尔实验室、朗讯、Avaya</li><li>2000年，Ken thompson从贝尔实验室退休，2006年加入Google</li></ul></li><li>2001年，关闭贝尔实验室几乎全部的研究部门，只是象征性的留下一两个部门，保住贝尔实验室的招牌</li><li>2001年，一次次裁员、变卖资产，人数从巅峰时的16.5万人减少到3万</li><li>2006年，被法国阿尔卡特（Alcatel）公司收购，贝尔实验室迁往法国</li></ul></li><li>1996年以后的AT&T</li><li style="list-style: none; display: inline"><ul><li>失去了贝尔实验室的名字，将AT&T实验室更名为香农实验室</li><li>长话和电信业务受互联网和无线通信的冲击</li><li>1999年，一拆四，分成长途电话、移动电话、企业服务、宽带。其中，AT&T移动（AT&T wireless）在高盛的帮助下挂牌上市，募资100亿美元</li><li>分家后的长途电话公司有钱，但没前途；移动电话有前途，没钱</li><li>互联网兴起后，再也没人为1分钟3美元的长途电话买单了，AT&T的长话暴利过去了</li><li>2004年，AT&T被道琼斯指数除名，被原7小贝尔的SBC取代</li><li>2005年，SBC经过连续小吃大过后，最终吃下AT&T，新公司采用了AT&T的名字，但标志换了</li></ul></li></ul></li><li>IBM大事记</li><li style="list-style: none; display: inline"><ul><li>1924，老沃森控股原打表机公司，改名IBM。</li><li>1925，进入日本市场，此前打表机公司已经开始逐渐进入欧洲市场。</li><li>1933，IBM工程实验室成立。</li><li>1936，在罗斯福新政时，获得美国政府大订单。</li><li>1940，20世纪40年代进入亚洲市场。</li><li>1943，IBM研制出真空管放大器。</li><li>1945，沃森实验室成立。</li><li>1952，小沃森成为IBM总裁，开始了快速发展的20年计算机时代。</li><li>1953，研制出使用磁鼓的计算器。</li><li>1964，IBM360大型计算机问世。</li><li>1969，开始语言识别的研究，司法部开始对IBM进行反垄断调查。</li><li>1971，小沃森退休。</li><li>1972，江崎玲於奈（Leo Esaki）博士因在电子隧道效应上的研究为IBM获得第一个诺贝尔奖。</li><li>1981，IBM-PC诞生。</li><li>1993，郭士纳接管IBM，开创IBM 10年黄金时代。</li><li>1997，计算机深蓝战胜国际象棋世界冠军卡斯帕罗夫。</li><li>2005，IBM将PC部门卖给联想，从此退出PC市场。<br>
</li></ul></li><li>苹果大事记</li><li style="list-style: none; display: inline"><ul><li>1976，苹果计算机公司成立。</li><li>1977，发明个人电脑。</li><li>1984，推出采用图像视窗界面操作系统的麦金托什电脑。</li><li>1985，乔布斯和新CEO斯卡利开始权力斗争，前者失败离开苹果公司。</li><li>1994，苹果告微软的视窗操作系统抄袭它的麦金托什操作系统，官司最终和解。</li><li>1997，乔布斯回到苹果公司，经过权力斗争，接管了多年亏损的公司；同年，和微软的官司以微软注资， 果而得到和解。</li><li>1998，iMac诞生，苹果重新盈利。</li><li>2001，iPod诞生，颠覆了音乐产业。</li><li>2007，iPhone诞生，颠覆了整个手机行业。</li><li>2010，iPad诞生，同年苹果公司的市值再次超过微软，成为全球最值钱的IT公司。</li><li>2011，乔布斯卸任苹果CEO，由首席运营官库克接任<br>
</li></ul></li><li>计算机工业的生态链</li><li style="list-style: none; display: inline"><ul><li>摩尔定律：每18个月，计算机等IT 产品的性能会翻一番<br>
</li><li>反摩尔定律：如果你反过来看摩尔定理，一个IT 公司如果今天和18个月前卖掉同样多的、同样的产品，它的营业额就要降一半</li><li>安迪-比尔定律：What Andy gives, Bill takes away。以微软为首的软件开发商吃掉硬件提升带来的全部好处（软件所占的内存和计算速度越来越来大），迫使用户更新机器让惠普和戴尔等公司受益，而这些整机生产厂再向英特尔这样的半导体厂订货购买新的芯片、同时向Seagate 等外设厂购买新的外设</li></ul></li><li>Intel大事记</li><li style="list-style: none; display: inline"><ul><li>1968，英特尔成立。</li><li>1971，开发出英特尔第一个商用处理器Intel 4004。</li><li>1978，英特尔公司开发出8086微处理器，它成为IBM-PC的CPU。</li><li>1982，80286CPU问世。</li><li>1985，32位的80386处理器问世。</li><li>1986，英特尔公司上市。</li><li>1987，安迪·格鲁夫担任英特尔CEO，英特尔开始了快速发展的10年，并且成为全球最大的半导体公司。</li><li>1989，定点和浮点处理合一的80486处理器问世。</li><li>1993，奔腾系列处理器问世，在随后的十年里，英特尔推出了很多代的奔腾处理器。</li><li>2000，英特尔的手机处理器X-Scale问世。</li><li>2001，英特尔的64位服务器处理器Itanium问世，英特尔在服务器市场彻底超越RISC的代表太阳公司。</li><li>2005，基于ARM的处理器占到了智能手机处理器市场的98%，英特尔在这个市场明显落后于高通公司和德州仪器公司。</li><li>2006，双核处理器问世。同年，英特尔的手机处理器部门X-Scale卖给了Marvell公司，从此退出手机处理器市场。</li><li>2009，四核处理器问世，英特尔继续在服务器处理器市场上占优势<br>
</li><li>CISC和RISC之争：20世纪80年代末，Intel面临一次重大抉择——是继续开发与8086系列兼容的复杂指令处理器，还是转到全行业都认同的精简指令处理器。“偏执”的Intel选择了前者，这将意味着它成为唯一一家开发复杂指令处理器的公司，它将凭一己之力对抗整个行业！最终，英特尔不是靠技术，而是靠市场打赢了这场指令集战争<br>
</li></ul></li><li>微软大事记</li><li style="list-style: none; display: inline"><ul><li>1975，微软公司成立。</li><li>1980，微软为IBM-PC提供DOS操作系统。</li><li>1981，微软和苹果开始合作。</li><li>1990，微软推出基于图像界面的视窗3.0操作系统，微软帝国开始形成。</li><li>1993，微软推出视窗版制表软件Excel，并最终挤垮了这个领域的莲花公司。</li><li>1995，word95问世，微软最终挤垮了这个领域的WordPerfect公司；同年，浏览器IE问世，微软最终以此挤垮了网景公司；但是，微软在进入互联网上行动迟缓，最终落后于雅虎公司。</li><li>2000，微软成为全球市值最高的公司，市值超过5000亿美元；同年，美国华盛顿地方法院裁定微软的垄断行为，要求微软一分为二成为两个独立公司，后来在共和党当政期间向高等法院上述，驳回了原判；同年，鲍尔默接替盖茨成为微软CEO。</li><li>2004，微软进入搜索领域，开始了和Google的重量级竞争。</li><li>2007，微软推出视窗Vista操作系统，该软件如此糟糕使得用户宁愿选择早期的XP版本，Vista成为微软历史上最失败的操作系统。</li><li>2009，微软试图收购雅虎，但是失败了<br>
</li></ul></li></ul><div>27. 杂项</div></div><div><ul><li>按照C89/C99兼容旧版本的设计，无参函数的前置声明应该用"void func(void)"，如果省略那个"(void)"，将会视为旧版函数声明，即放弃参数的类型检查。C++没有这个问题</li><li style="list-style: none; display: inline"><ul><li>一个误用旧声明的例子（放弃参数类型检查）：</li><li style="list-style: none; display: inline"><ul><li>main.c: void add(); int main() { add("abcd"); }</li><li>add.c: int add(int a, int b) { return a + b; }</li><li>这个程序编译、运行得起来；改声明为“void add(void);”，gcc将发现参数类型不匹配错误</li></ul></li></ul></li><li>Python project: Calendar类，还可以打印</li><li>C++ project: 以2的幂为步进的lowerBound，比原始版本快一半；出自编程珠玑，最早出自MIT；涉及知识点：（1）速算n以2的幂对齐的ceil（2）程序验证（loop invaraint）</li><li>C++ project: 插入最少字符构成回文；分别用分治（divide-and-conquer）、动态规划、备忘录来解；分治直接超时，动规比备忘录快很多，就本题而言，可能是内存使用的原因</li><li>C++ project: KMP。测试文本中的表现：strstr>sunday>kmp>for x for>for x memcmp，还没有strstr快...</li><li>C++ project: AC-automation。测试用例是在man bash的文本中搜索每个单词的出现，比strstr实现的逐个匹配快几十倍</li><li>C++ project: 3-way quicksort（左边<，右边>，中间==，递归只处理左右）, 主要处理当序列中有大量重复值出现时；常规的2-way在遇到重复值时会退化，比如，按<=和>来partition的算法，空间复杂度是O(occurs(v))，时间复杂度是O(occurs(v)^2)</li><li>C++ project: Skiplist；提供map的ADT，即有序关联数组，另外还支持用getKth来O(logn)的获取第k项</li></ul><div>27. 浪潮之巅</div></div><div><ul><li>思科</li><li style="list-style: none; display: inline"><ul><li>1984，思科公司成立。</li><li>1986，思科推出第一款多协议路由器产品。</li><li>1990，思科上市。</li><li>1995，钱伯斯担任思科CEO（至今），开创了思科王国。</li><li>2000，思科发展达到高潮，垄断了多协议路由器的世界市场；当年思科市值一度超过微软成为全球价值最高的公司，思科股票一天的交易额一度超过整个上海股市。</li><li>2001，随着互联网泡沫的破裂，思科业绩急速下滑，股价下跌80%以上，公司有史以来第一次裁员。</li><li>2003，思科在VoIP等领域快速发展，公司重回上升轨迹。<br>
</li></ul></li></ul><div>28. 编程珠玑，第11章，排序</div></div><div><ul><li>纸牌玩家保持手中卡牌有序的方法是插入排序</li><li>shellsort，步进为3n+1</li><li>quicksort，逆向，以x[l]为guard</li><li>quicksort处理好有序、大量重复这两种特殊输入后，基本就可用了；前者的对策是swap mid/rand，后者对策是2way/3way</li></ul></div><div>28. 杂项</div><div><ul><li>C++ project: quickSort, guard</li><li>C++ project: quickSort, 2way, optimal</li><li>C++ project: shellsort, 3n</li></ul><div>29. 浪潮之巅</div></div><div><ul><li>雅虎</li><li style="list-style: none; display: inline"><ul><li>1995，雅虎成立。</li><li>1996，仅一岁的雅虎上市，创下了新公司上市最短时间的奇迹。</li><li>1998，成为世界上最大的互联网公司，并且长期压制住了美国在线和微软的MSN。</li><li>2000，采用Google的搜索引擎。</li><li>2001，由于互联网泡沫，雅虎股价达到创纪录的每股400美元的天价（考虑到后来的每次2:1分割，相当于今天的每股100美元），但是以后不再有机会接近这个价位。</li><li>2002，收购搜索引擎Inktomi，并于第二年和Google分道扬镳。</li><li>2003，收购搜索广告公司Overture，和Google开了白热化的竞争。</li><li>2005，投资中国的阿里巴巴公司，成为它最成功的投资。</li><li>2006，被Google超越，退居互联网行业第二名，从此一蹶不振。</li></ul></li><li>Google</li><li style="list-style: none; display: inline"><ul><li>1998，Google成立。</li><li>1999，美国最大的两家风险投资公司KPBC和红杉资本同时投资Google，这是这两家公司第一次同时投资一家Startup。第二年，雅虎采用Google的搜索引擎。2001 Google推出搜索广告系统Adwords，并于当年第4季度实现盈利；同年，埃里克·施密特成为Google正式的CEO。</li><li>2002，美国在线采用Google的搜索引擎和广告系统，Google占到为全球搜索流量的70%。</li><li>2003，Google第二个广告产品Adsense上线。</li><li>2004，Google采用竞拍的方式上市；同年Google革命性的Gmail和Google Earth产品上线。</li><li>2006，Google在线支付产品Checkout上线，效果极差，成为Google第一款失败的主要产品；同年Google收购YouTube。</li><li>2007，Android联盟成立。</li><li>2008，第一款基于Android的手机由HTC出厂，但是销路一般；同年Google推出Chrome浏览器。</li><li>2009，受金融危机的影响，Google第一次裁员，但是很快回到增长的轨迹；同年随着摩托罗拉Droid手机上市，Android手机操作系统获得巨大的成功。</li><li>2010，Google的手机操作系统Android市场占有量超过苹果的iPhone，浏览器Chrome也从微软手中夺得15%的市场份额，但是它在社交网络上一直输给facebook。</li><li>2011，共同创始人佩奇接替施密特成为Google新CEO。<br>
</li></ul></li></ul><div>29. 编程珠玑，第12章，取样问题</div></div><div><ul><li>原理：</li><li style="list-style: none; display: inline"><ul><li>正确理解所遇到的问题。确保无歧义</li><li>提炼出问题的抽象。即挖掘需求</li><li>考虑尽可能多的算法。花1小时思考+1小时实现，比1分钟思考+1天来实现更好</li><li>实现一种解决方案。</li><li style="list-style: none; display: inline"><ul><li>作者给的反例：参加过大型软件开发项目的学生提交了10多页的作业，作者给分不及格，因为，好的算法只需要5行而他们提交了10多页，软件工程的目的是控制复杂度而不是增加复杂度</li></ul></li><li>回顾。《How to solve it》说，改进的余地总是存在的，经过充分的研究和思考，任何解决方案都可能被改进</li></ul></li><li>几个随机算法</li><li style="list-style: none; display: inline"><ul><li>random_shuffle</li><li>给定长为n的序列，选m个</li><li style="list-style: none; display: inline"><ul><li>random_shuffle+head(m)</li><li>for i in [0, m): swap(i, rand(i, n))</li></ul></li><li>只支持前向迭代（如链表、文件中的行）的序列中，随机选择一项</li><li style="list-style: none; display: inline"><ul><li>i = 1; for v in list: if rand() % i++ == 0: select = v;</li></ul></li><li>从0~n中选m</li><li style="list-style: none; display: inline"><ul><li>简单的应用集合：while (S.size() < m) S.insert(rand(0, n))</li><li style="list-style: none; display: inline"><ul><li>缺点：当m接近n的时候，开销很大；比如当m==n的时候，随机次数是n^2</li><li>适用：m<<n</li></ul></li><li>先生成n个元素的序列，然后随机选前m个</li><li style="list-style: none; display: inline"><ul><li>缺点：空间</li><li>适用：n较小的时候</li></ul></li><li>knuth的算法：choose(R, m, n) => if (rand(0, n) < m) {R.insert(m); choose(R, m - 1, n - 1); } else { choose(R, m, n - 1); }</li><li style="list-style: none; display: inline"><ul><li>缺点：n和m相差较大的时候很难停止（复杂度几乎是n-m），因此如果n、m相差较大且n也很大，则很慢</li><li>适用：n较小或者n、m接近的时候</li></ul></li><li>floyd的算法：choose(S, m, n) => choose(S, m - 1, n - 1); v = rand(0, n); if (v in S) { S.insert(n); } else { S.insert(v); }</li><li style="list-style: none; display: inline"><ul><li>适用：各种情况</li></ul></li><li>n和m都很大，但n-m很小，可以改生成"0~n中选n-m个"，然后输出不在结果集中的数</li></ul></li></ul></li></ul><div>29. 编程珠玑，13章，搜索</div></div><div><ul><li>用链表进行中部插入，为什么可能比数组更慢：</li></ul><ol><li style="list-style: none; display: inline"><ol><li>链表需要的内存更大，可能放不进缓存</li><li>链表的访存模式不连续，空间局部性差</li></ol></li></ol><ul><li>对于链表、树等结构，都可以添加哨兵，以简化代码提高性能</li></ul><div>29. 编程珠玑，14章，堆</div></div><div><ul><li>为循环编写代码时，首先应该精确说出它的不变式</li><li>好的工程师应该能分清某个组件做什么（抽象功能）和怎么做（黑盒实现）之间的差别</li><li>make_heap可以实现为n个push_heap，复杂度为O(n*logn)；也可以采用n个siftdown(i, n)，单次开销为O(log(n)-log(i))，总开销为O(n)（用recursion-tree来计算）</li><li>基于heap的priority_queue可以用在操作系统的优先级调度、timer的最早事件选择等场合</li><li>优先级队列：push_heap，pop_heap</li><li>heap_sort: make_heap，然后n个pop_heap，总复杂度是O(n)+O(n*logn)；比n个push_heap再n个pop_heap的方案快个常因子，后者是O(n*logn)+O(n*logn)</li><li>因为heap的索引是1~n，所以在C语言中可以使用--begin的技巧</li></ul><div>29. 编程珠玑，15章，字符串</div></div><div><ul><li>进行string interning的时候，比起用set<string>来存储字符串，不如将字符串存放在多个大的字节数组中（deque），然后用set<const char*>来保证唯一，后者占用内存更小</li><li>后缀数组：a={str, str + 1, str + 2, str + 3, ...}; a = sorted(a); 适用问题：</li><li style="list-style: none; display: inline"><ul><li>求串的最长重复子串：遍历a，找max(common_substr(a[i], a[i+1]))</li><li>至少出现k次的最长子串（上面的应用是k=2的特例）：遍历a，找max(common_substr(a[i], a[i+k-1]))。显然a[i]和a[i+k-1]的公共前缀，也是a[i+1]...a[a+k-2]的公共前缀</li></ul></li><li>后缀数组也可以用Trie来代替，只是内存占用可能多点</li></ul><div>29. 杂项</div></div><div><ul><li>无符号数的作用：实现biginteger、bit field、shift right logical、hash caculation、array index（table[(unsigned char)buf[i]]）</li><li>两个off-by-one技巧：</li><li style="list-style: none; display: inline"><ul><li>end[-1]或者top[-1]这样，用-1来访问指针的前一个元素</li><li>由于minimum heap中，使用的索引是1~n，而C语言中的索引是0~n-1，因此可以，--begin，然后 begin[1], begin[n]</li></ul></li><li>搬移和交互语义分别是赋值和swap，前者如插入排序、heap的shiftdown/siftup，后者如reverse、quicksort中的swap(a[0], a[m])等。当然，某些时候，用连续swap代替连续赋值能让代码更简洁，付出一些性能代价...</li><li>想用两次rand()生成更大范围的随机数，因为不知道RAND_MAX的位数（linux是30位，windows是15位），所以不能用位移，一个可移植的方案是：rand() * RAND_MAX + rand()</li><li>一个浮点数组求和，为了将精度损失降到最小，应该用优先队列，每次pop两个最小值，相加后再push</li><li>只支持前向迭代的序列容器（如链表，组成文件的非连续扇区），访问第i个元素需要O(n)的时间，因为每个节点只有i->i+1的指针，如果再添加一个i->2*i的指针，则访问第i个元素的复杂度是O(logn)，因为这实质上成了堆。算法：</li><li style="list-style: none; display: inline"><ul><li>index(i) => if (i % 2) { index(i - 1); } else { index(i / 2); } print(i);</li></ul></li><li>x86的bsr指令可以计算整数最高位1的位置</li><li style="list-style: none; display: inline"><ul><li>可以用来加速step 2^n的lower_bound：主要是switch的时候可以根据log(n/2)直接索引jump table跳转到固定位置，进而开始无迭代的缩小检测范围</li><li>可以用来计算2^ceil(log(n))，即((1<<bsr(n-1))*2)；当然，这个计算用C来也容易，不需要循环</li></ul></li><li>C++ project: elimination series，淘汰赛队伍安排算法</li></ul><div>30. 杂项</div></div><div><ul><li>string interning的好处：</li><li style="list-style: none; display: inline"><ul><li>size: str.size</li><li>hash：hash((long)str)，或者，str.hash</li><li>equal：str1 == str2</li></ul></li><li>C++11的auto和decltype</li><li style="list-style: none; display: inline"><ul><li>auto默认丢掉赋值号右边的引用、const属性，需要的话，用auto &、const auto来声明；C++14中有decltype(auto)，使得auto的右边是变量时，规则同decltype</li><li>decltype总是同表达式类型相同，包括const和左右引用属性</li></ul></li><li>C++ project: string interning，比起直接用set<string>做internning，用开链hash表+内存池+wordStream的方案，性能是3.5倍，空间是2.32倍；和python、lua比起来，性能是2倍，空间是3倍</li><li>C++ project: suffix array用于多模式匹配</li><li>C++ project: randSeq.h，包括set、knuth、floyd等在内的"生成m个0~n的数"算法；以及randomShuffle、randomChoise、randomHead算法</li></ul></div></div>