Aiur

zellux 的博客

CLRS Problem 11.1-4

简单来说就是给定一个未初始化的巨大的数组,然后通过它实现一个字典。所谓未初始化是指一开始里面元素的值都是随机的,巨大是指可以假设数组长度范围很大,对这个数组做初始化工作(例如清零)的代价自然也是很大。现在的问题是,利用这个数组设计出来的字典,要求初始化、查找、插入、删除操作都能在O(1)时间内完成。 Intructor’s Manual 上的解答设计了一个很巧妙的验证策略。假设T为那个巨大的数组,S为辅助栈,那么对于一个键k,如果k存在于这个字典中,则T[k]保存的是 k在S中的位置j,而S[j]则保存了k值。即1 ≤ T[k] ≤ top[S], S[ T[k] ] = k, T [ S[j] ] = j,我们称这个条件为“验证环”。这个设计的关键在于T和S能够互相验证,从而排除了未初始化位置上随机值的干扰。 还有一个问题就是,键k对应的值v应该怎么保存呢?其实只要维护另外一个和T或者S平行的数组就行了,既然S的元素个数远小于T,选择和S平行即可。 根据这个验证策略,我们就能设计出词典的基本操作了: 初始化:建立一个大小为0的栈 查找:给定键k,检查 1 ≤ T [k] ≤ top[S] && S[ T[k] ] = k,如果满足则返回对应值,否则返回NULL 插入:如果键已经存在则直接替换;否则将新的键值入栈,并且维护T[k] ← top[S] 删除:要确保两件事,一是验证环要被破坏,二是栈S的空洞要被填补。通过把栈顶的元素移动到要删除的元素位置,我们能同时确保这两点: S[ T[k] ] ← S[ top[S] ] S[ T[k] ] ← S [ top[S] ] T[ S[ T[k] ] ] ← T [k] T[k] ← 0 top[S] ← top[S] − 1 所有操作都能在O(1)时间内完成 阅读全文 →

两个和函数构造相关的趣味面试题

http://stackoverflow.com/questions/731832/interview-question-ffn-n http://stackoverflow.com/questions/732485/interview-question-ffx-1-x

问题描述很简单,第一个问题是实现一个函数f,参数为一个带符号的32位整型,使得f(f(x)) = -x,即调用两次后返回的结果为原来的相反数;另一个问题也是实现一个函数g,参数为一个32位浮点,最后使得g(g(x)) = 1/x。如果不能满足所有的情况,就满足尽可能多的情形。

第二个问题比第一个问题简单一点,目前支持数最高的两个答案如下:

阅读全文 →

带环链表求环的起点

很经典的问题了,求环的长度可以用两个步长分别为1和2的指针遍历链表,直到两者相遇,此时慢指针走过的长度就是环的长度。另外相遇后把其中指针重新设定为起始点,让两个指针以步长1再走一遍链表,相遇点就是环的起始点。 证明也很简单,注意第一次相遇时 慢指针走过的路程S1 = 非环部分长度 + 弧A长 快指针走过的路程S2 = 非环部分长度 + n * 环长 + 弧A长 S1 * 2 = S2,可得 非环部分长度 = n * 环长 - 弧A长 指针A回到起始点后,走过一个非环部分长度,指针B走过了相等的长度,也就是n * 环长 - 弧A长,正好回到环的开头。 阅读全文 →

Sorting Networks

算法导论第27章,在并行处理的条件下效率很高的排序算法。 介绍 如下面左图所示,每条横线(wire)代表一个待 比较的数值,竖线(comparator)表示连接的两条横线要做一次比较,并将较小的值放在输出横线的上方,较大的放在下面。排序过程就是从左往右依次 调用各个comparator(在同一位置上的comparator可以同时做) 有图表示了四个数字3, 2, 4, 1在经过这个Sorting Network时的行为。(由于背景为深色,建议点击图片查看) 下图是一个冒泡排序的Sorting Network表示 可以看到所有的比较都没有并行,效率很低。接下来先介绍一个0-1原理,然后利用它来构造一些比较高效的网络。 性质 首先是引理27.1: 对 于输入数据A = ,如果某个比较网络(comparison network)的输出是B = ,那么对于任一单调递增的函数f,这个网络能把输入数据f(A) = 变为f(B) = 这个引理的证明很简单,关键在于min(f(x), f(y)) = f(min(x,y)) 接下来就是0-1原理: 一个有n个输入数据的比较网络,如果它能将仅由0和1组成的序列正确的排序(这种输入共有2^n种可能),那么它也能正确的将任意数字组成的序列排序。 证明也不难,利用前面的引理反正即可得到这个定理。 双调排序 接 下来先考虑双调序列(bitonic sequence)这种特殊情况,所谓双调序列就是先单调递增,后单调递减,或者可以通过环形旋转变化出上述特性的序列,比如和都满足条件(对于后面一种序列,只要把最后的3, 5移到序列开头就行了)。 双调排序(bitonic sorter)有若干步骤,其中有一步叫做half-cleaner,每一次half-cleaner讲数据放到一个深度为1的排序网络中,第i行和第i+n/2行比较(i=1,2,..,n/2) 引理27.3: 做完上述的half-cleaner后,输出的上半部分和下半部分都保持双调的特点,而且上半部分的每个元素都不大于下半部分的任一元素。 分四种情况讨论即可。 通过递归调用half-cleaner即可完成双调队列的排序。要对n个元素进行双调排序Bitonic-Sorter(n),首先调用Half-Cleaner(n),将元素分成上下两部分,接着依次对这两部分执行Bitonic-Sorter(n/2)即可。 调用的深度D(n) = lgn 归并网络 书上只给出了对0-1序列排序的算法,任意数字的排序算法留作了习题。 合并网络基于这样一个事实:对于两个已经排序了的序列X = 00000111,Y = 00001111,将Y倒过来后和X拼接的结果是一个双调序列。对这个双调序列再做一次Bitonic-Sorter就能有序。 通 过修改Bitonic-Sorter方法的第一步就能实现Merger,关键在于隐式的反转输入的下半部分。Half-Cleaner方法中比较了第i和 第i+n/2两个元素,如果下半部分反转的话就相当于比较第i和第n-i+1个元素。直接继续执行Bitonic-Sorter方法即可,如下图所示。 排序网络 我们已经有了构造一个排序网络所需的工具,接下来介绍一种利用归并网络进行排序的并行版本。 大致方法和传统的归并排序类似,从最小的颗粒开始二分增长,直到整个序列有序。 这样,一共需要lg(n)次Merger,每次归并中需要做lg(i)次Sorter,排序的总深度 D(n) = 0 (n = 1) D(n/2) + lg(n) (n = 2^k且 k>=1) 由Master Method可推出D(n) = big-omega(lg^2(n)) 也就是说理想的并行环境中,n个数可以在O(lg^2(n))时间内完成排序。 阅读全文 →