Oenhan Google Reader

    Oen 通过 Google 阅读器发送给您的内容：     一些鲜为人知却非常实用的数据结构 于 13-5-27 通过 博客园_256code, 生活与技术 作者：Haippy 作为程序猿（媛），你必须熟知一些常见的数据结构，比如栈、队列、字符串、链表、二叉树、哈希，但是除了这些常见的数据结构以外，还有没有其他不是很有名，但却非常实用的数据结构呢，有人在 stackoverflow 上问了这样一个问题，得到了很多热心观众的回答，我们今天就来看看那些鲜为人知却非常实用的数据结构吧。 首先，维基百科上的一个页面列举了 常见的数据结构 ，你可以先去那个页面看看。下面我们就来看看一些不是很常见的数据结构吧： Tries (前缀树) Bloom filter (布隆过滤器) Rope : 主要用于某些文本编辑器中，可用于字符串高效地插入、删除、追加等操作。SGI 的 STL 中实现了 Rope(http://www.sgi.com/tech/stl/Rope.html) Skiplist (跳表) Spatial Indices (空间索引)，如 R-trees 和 KD-trees Splay trees (伸展树) Disjoint Set (并查集) Fibonacci heaps (斐波那切堆) Huffman trees (哈夫曼树) ring buffer (又名circular buffer) Merkle trees (哈希树) min-max heap bitset (又称bit array, 位数组) Xor linked list AA tree Log-structured merge-tree Radix tree Judy array       本文链接     可从此处完成的操作：...

    Oen 通过 Google 阅读器发送给您的内容：     gdb的基本工作原理是什么？ 于 10-10-28 通过 SpongeLiu的blog 作者：sponge 还是面某M的时候，面试官问我："用过gdb么？" 答："用过，调了两年bug了"。"那好，给我解释下gdb是怎么工作的？或者说跟内核什么地方有关系？"。 是阿， gdb凭什么可以调试一个程序？凭什么能够接管一个程序的运行？ 我以前也想过这样的问题，但是后来居然忘记去查看了。我想到了我们的二进制翻译器，想到了intel的pin，Dynamo。这些都是将翻译后的代码放到codecache中去运行，然后接管整个程序的执行。gdb是不是也一样呢？ 如果真是这样，为什么我记得用gdb跑一个程序，这个程序会有一个单独的进程？gdb的attach功能又是怎么实现的？ 想了想，我还是没有答上来。面试就是由这么一个又一个细节的小杯具最后汇集成一个大杯具。 那么，gdb到底是凭什么接管的一个进程的执行呢？其实，很简单， 通过一个系统调用：ptrace 。ptrace系统调用的原型如下： #include <sys/ptrace.h>   long ptrace ( enum __ptrace_request request , pid_t pid , void * addr , void * data ) ; 说明：ptrace系统调用提供了一种方法来让父进程可以观察和控制其它进程的执行，检查和改变其核心映像以及寄存器。 主要用来实现断点调试和系统调用跟踪。（man手册） 其实，说到这里，一切原理层面应该都比较明朗了（且先不去管内核中是怎么实现ptrace的）。gdb就是调用这个系统调用，然后通过一些参数来控制其他进程的执行的。 下面我们来看ptrace函数中request参数的一些主要选项： PTRACE_TRACEME： 表示本进程将被其父进程跟踪，交付给这个进程...

    Oen 通过 Google 阅读器发送给您的内容：     字符串匹配的Boyer-Moore算法 于 13-5-2 通过 阮一峰的网络日志 上一篇文章，我介绍了 KMP算法 。 但是，它并不是效率最高的算法，实际采用并不多。各种文本编辑器的"查找"功能（Ctrl+F），大多采用 Boyer-Moore算法 。 Boyer-Moore算法不仅效率高，而且构思巧妙，容易理解。1977年，德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法。 下面，我根据Moore教授自己的 例子 来解释这种算法。 1. 假定字符串为"HERE IS A SIMPLE EXAMPLE"，搜索词为"EXAMPLE"。 2. 首先，"字符串"与"搜索词"头部对齐，从尾部开始比较。 这是一个很聪明的想法，因为如果尾部字符不匹配，那么只要一次比较，就可以知道前7个字符肯定不是要找的结果。 我们看到，"S"与"E"不匹配。这时， "S"就被称为"坏字符"（bad character），即不匹配的字符。 我们还发现，"S"不包含在搜索词"EXAMPLE"之中，这意味着可以把搜索词直接移到"S"的后一位。 3. 依然从尾部开始比较，发现"P"与"E"不匹配，所以"P"是"坏字符"。但是，"P"包含在搜索词"EXAMPLE"之中。所以，将搜索词后移两位，两个"P"对齐。 4. 我们由此总结出 "坏字符规则" ： 　　后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置 如果"坏字符"不包含在搜索词之中，则上一次出现位置为 -1。 以"P"为例，它作为"坏字符"，出现在搜索词的第6位（从0开...

    Oen 通过 Google 阅读器发送给您的内容：     字符串匹配的KMP算法 于 13-5-1 通过 阮一峰的网络日志 字符串匹配 是计算机的基本任务之一。 举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？ 许多算法可以完成这个任务， Knuth-Morris-Pratt算法 （简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。 这种算法不太容易理解，网上有很多 解释 ，但读起来都很费劲。直到读到 Jake Boxer 的文章，我才真正理解这种算法。下面，我用自己的语言，试图写一篇比较好懂的KMP算法解释。 1. 首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。 2. 因为B与A不匹配，搜索词再往后移。 3. 就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。 4. 接着比较字符串和搜索词的下一个字符，还是相同。 5. 直到字符串有一个字符，与搜索词对应的字符不相同为止。 6. 这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。 7. 一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。 8. 怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。 9. 已知空格与D不匹配时，前...