zhangyu8374
- 浏览: 93705 次
- 性别:
- 来自: 北京
-
最新评论
-
ethan_shan：
反向索引（Inverted Index） -
337240552：
...
反向索引（Inverted Index） -
yanqingluo：
我的HADOOP源码是最新的,总是编译不过.
编译不过是因为 ...
Hadoop系列－IPC模型 -
aquester：
java_somuch 写道我的理解是，任何时候NameNod ...
Hadoop系列－IPC模型 -
aquester：
详细的Hadoop IPC分析，请参见：http://bbs. ...
Hadoop系列－IPC模型
文章列表
周末两天被BM算法折磨的要死。《a fast string search algorithm》论文中提到的算法思想倒是理解的差不多，但网上（http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140）给出的实现可就是看不懂。通过Baidu，Google一搜，可以看到很多Boyer-Moore的实现。但绝大部分实现都是简化版本，只考虑了bad-character shift，而忽略了good-suffix shift。它思想的源泉是从右向左匹配字符串将获得更多有用的信息。The algorithm precomputes t ...
- 2007-06-02 05:59
- 浏览 2698
- 评论(0)
题目 You have been given 2 special, extremely rugged Xboxes. You are in an office building that is 100 stories high. Using the fewest possible number of drops from windows in your office building, determine the highest floor you can drop an Xbox from and have it survive: for example, they might be able ...
- 2007-06-02 05:59
- 浏览 1699
- 评论(0)
题目村子中有50个人，每人有一条狗。在这50条狗中有病狗（这种病不会传染）。于是人们就要找出病狗。 每个人可以观察其他的49条狗，以 判断它们是否生病（如果有病一定能看出来），只是自己的狗不能看。观察后得到的结果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要枪 毙自己的狗（发现后必须在一天内枪毙），而且每个人只有权利枪毙自己的狗，没有权利打死其他人的狗。 第一天大家全看完了，但枪没有响，第二天仍没有枪响。到了第三天传来一阵枪声，问村里共有几条病狗，如何推算得出？答案3条病狗分析 假设有n条病狗，那么就有50-n个人的狗不是病狗。第一天大家枪都没有响， 那么n必然大于 ...
- 2007-06-02 05:58
- 浏览 1859
- 评论(0)
Skip List号称性能与BST（Binary Sort Tree）树有得一拼，于是把它翻了个底朝天。代码是阐述其思想的最好方式，那我们还是看看它的具体实现（采用Java语言）public class SkipList { public static final int NOT_FOUND = -1; public static final int HEADER_KEY = -2; public static final int NIL_KEY = Integer.MAX_VALUE; // optimum probability public static final float OPT ...
- 2007-06-02 05:58
- 浏览 2305
- 评论(0)
特色：Library sort优于传统的插入排序（时间复杂度为O(n^2))，它的时间复杂度为O（nlogn），采用了空间换时间的策略。 思想：一个图书管理员需要按照字母顺序放置书本，当在书本之间留有一定空隙时，一本新书上架将无需移动随后的书本，可以直接插空隙。Library sort的思想就源于此。 实现：有n个元素待排序，这些元素被插入到拥有(1+e)n个元素的数组中。每次插入2^(i-1)个元素，总共需要插logn趟。这2^(i-1)个元 素将被折半插入到已有的2^(i-1)个元素中。因此，插入i趟之后，已有2^i个元素插入数组中。此时，执行rebalance操作，原有处在(1+ e)2^ ...
- 2007-06-02 05:58
- 浏览 2564
- 评论(0)
插入实现（传指针地址的地址）： void InsertNode(struct node **node_ptr, struct node *newNode) { struct node *node = *node_ptr; if (node == NULL) *node_ptr = newNode; else if (newNode->value <= node->value) InsertNode(&node->left, newNode); else InsertNode(&node->r ...
- 2007-06-02 05:57
- 浏览 1396
- 评论(0)
用堆栈实现递归其实并没有消除递归，只不过人工做了本来由编译器做的事情。真正的非递归是指运算时所需要的空间是常数，即所需空间与问题的输入规模无关。并非所有递归都可以转换成非递归，比如著名的Ackmann函数。递归转非递归方法：（1）用一般公式直接代替。象经常看到的斐波那契数列，它就存在通项公式，而无需采用递归实现。（2）使用栈来实现（3）通过Cooper变换、反演变换将一些递归转化为尾递归，从而迭代求出结果至于什么是Cooper变换，反演变换，这可得好好研究数学。这里贴两个变换实例。计算阶乘的递归实现（用Haskell实现的，谁都看得懂）：f x ＝ if x = 0 then 1 else f( ...
- 2007-06-02 05:56
- 浏览 2033
- 评论(0)
顺序表的实现，天下人都知道，最最简单的一种，不过我还是贴出两个实现，大家看看：int search(int a[],int key,int length){int i;for(i=length-1;i>=0;i--){if(a[i]==key) return i;}return -1;}/** 实际数组元素是从1号位置起开始存储，0号位置存储key*/int search(int a[],int key,int length){int i;a[0] = key;for(i=length;!(a[i]==key);i--);return i;}由此，想到了字符串的拷贝实现： for(i= ...
- 2007-06-02 05:56
- 浏览 1184
- 评论(0)
性质1：一颗二叉树（严格的二叉树，即没有度为1的节点），有N个内部节点，那么它将有N＋1个外部节点。 采用归纳法证明： 如果只有一个外部节点，即单独的一个根节点，那么内部节点数为0，结论显然成立。 假设有N－1个内部节点时，结论成立。那么二叉树拥有N个内部节点时，左子树有k个内部节点，右子树有N－k－1个内部节点，此外包括一个根节点。由于左 右子树的节点数都小于N，所以由前面假设可得左子树有k＋1个外部节点，右子树有N－k个节点，总共有k＋1＋(N-k)个节点，即N＋1个节点。 由性质1可得，一颗有N个外部节点的二叉树需要用数组存储，那么需要申请一个拥有2N－1个元素的数组。性质2：在一个已排序 ...
- 2007-06-02 05:55
- 浏览 1807
- 评论(0)