探索Ruby正则表达式算法(译)

来源:Exploring Ruby’s Regular Expression Algorithm(2012)

ps. 业余翻译的,求轻拍。有什么问题可以直接指出。

大家都熟悉正则表达式,它是开发者的“瑞士军刀”。不管你想查找哪种信息,解析哪些字符串,总有一种正则表达式适合你。事实上,你可能用过很久的ruby所使用的正则表达式了——正则表达式已经被集成到几乎所有主要的语言中好多年了:Perl、javascript、PHP、Java等等。ruby支持是在90年代中期,而正则表达式是在60年代中期发明的,早了30年。

但是正则表达式是怎样工作的呢?如果你对正则表达式引擎后面的计算机原理感兴趣的话,可以读一下这三篇Russ Cox写的极棒的文章:

在这里我不打算重复Russ的内容。但是我准备在第二篇文章中快速的解释一下ruby所使用的“无递归的回溯实现”, 这意味着它可能也会像perl正则表达式一下慢吞吞。就是说,这意味着Ruby并没有使用目前最主流的正则表达式实现方法——Thompson NFA,也就是Russ第一篇文章中所描述的。

今天我们细看一下Oniguruma,也就是Ruby所使用的正则表达式引擎。我们使用一些插图来表现一些简单的正则示例,以此来弄清楚在使用正则的时候是Ruby内部是如何工作的——它比你想象的要复杂多了。

继续阅读

堆排序

上次写了个快排的文章,果不其然被大家鄙视了。大概平时是一个写脚本的,这东西也不会了,大学时代还能帮别人替考c语言,现在连c都不写了。

回归正题,这里使用二叉堆,二叉堆是一个近似的完全二叉树,在很多地方都会用到这个结构。

通常使用数组来表示一个堆:假设数组第一个元素为根节点,那么它的左孩子节点就是第二个元素,右孩子节点为第三个元素。以此类推,假设一个节点是数组的第n个元素,它的左孩子节点就是第2n个元素,右孩子节点就是2n+1,可以使用floor(n/2)来获取其父节点。

二叉堆分为最大堆(MAX-HEAP,大顶堆)和最小堆(MIN-HEAP,小顶堆),最大堆就是父节点的值大于或等于子节点值的堆,所以根节点应该是最大的节点,最小堆反之。这里使用了最大堆。

继续阅读

快速排序

前几天有人问起快排,我心想这不难呀,把原理讲完了以后发现自己写不出来……回去默默看着导论用ruby写了一个……

快排使用分治思想。最重要的是分区:取一个基准值,比基准值小的放到数组左边,比基准值大的放到数组右边,基准值自己放到中间。然后对左边和右边的数进行再分区,如此递归直到全部排列好。

基准值是从数组中获取到的,你可以自己选择,或者随机选择一个。如果是随机取基准值的快排,因为无法确定命中最好情况还是最坏情况,所以大量的排序情况下会趋近于期望值。

快排保持着两个变量或者指针,一个是当前迭代到的key,一个是当前需要交换的key。如果达到交换条件(比如迭代到的key对应的值相对比对值小)就和需要交换的key进行交换。这两个变量或者指针可以按照自己的意愿进行调整,不管是从左到右,还是从右到左。

这里要注意的是当前需要交换的数是什么,我们假设比基准数小的数叫小数,比基数大的叫大数,排列在数组中最左边的大数叫最左大数,那么在程序中和基准数比对时:

  • 当前数是小数,交换当前数和最左大数(此时最左大数可能被移到了其他大数右边,往下一位找到下最新的最左大数)
  • 当前数是大数,进入下一轮
  • 和基准值相等,这种情况算大数小数都是可以的,因为后面迭代时会重新排到正确位置

所有数字比对和移动完毕后,把基准数和最左大数交换,这样基准数就在所有数字的中间了。

下面是增加了随机的ruby版本