RSS Feed

October, 2011

  1. Scheme实现函数的Memoization以及为什么要学习Lisp

    October 19, 2011 by xudifsd

    什么是Memoization

    似乎我已经在很多书上看到函数的Memoization了,《JavaScript语言精粹》提到过,《SICP》也提到过。然而《JavaScript语言精粹》里面提到的那个memoization没什么意思,因为它那个函数并不通用,但是《SICP》提到的就不一样了,它几乎做到了通用性。

    从维基上可以看到具体的定义,简单来说Memoization可以对重复并且计算量大的函数进行优化,并且该函数必须没有状态,也就是说无论调用该函数多少次函数值都一样。Memoization的做法就是将计算的值保存起来,并且在下次再调用同样参数时直接返回该值。

    Scheme的Memoization实现

    其实以前我就写过这样的文章,它是C语言实现,但是与《JavaScript语言精粹》一样做不到通用,只能针对一个参数而且类型为整型的,而且更加不通用的是写函数的人必须意识到Memoization的存在。Google的MapReduce就几乎不需要使用者意识到这个系统的存在,要是能做到MapReduce那样的通用性就好了,结果今天在《SICP》中看到下面这个Scheme语言实现的函数,当时就被震惊了,这个函数几乎实现了最大的通用性。

    (define memo-fib
      (memoize (lambda (n)
         (cond ((= n 0) 0)
               ((= n 1) 1)
               (else (+ (memo-fib (- n 1))
                  (memo-fib (- n 2))))))))
    
    (define (memoize f)
      (let ((table (make-table)))
        (lambda (x)
          (let ((previously-computed-result (lookup x table)))
            (or previously-computed-result
                (let ((result (f x)))
                  (insert! x result table)
                  result))))))

    使用的示例函数同样是计算斐波那契数,因为这个函数是O(n2)复杂度的,比较能体现优化的性能。其中memoize函数做缓存工作,并在没有缓存时再调用函数并进行缓存,memoize做的就是提供一个键值的映射,在这里是一对一的映射,但如果稍微修改一下程序就能处理多对一的映射了,从例子中也可以看出用户在编写计算斐波那契的函数时根本不需要意识到memoize的存在!它的实现原理就是Scheme函数所支持的Lambda演算,也就是说所有的支持Lambda演算的语言都能做到这样的通用性,众所周知的JavaScript就支持,不过唯一可惜的就是Scheme语言并没有提供make-table这个基本函数,需要用户自己实现,但是如果能实现一个非常快速查找表,那么它也可以与MapReduce一样通用。

    为什么要学习Lisp

    从这个例子也可以看出能够将函数当成参数来传递可以提供非常强大的抽象能力,也是许多赞扬Lisp的人的原因之一——你的编程语言能做到这样的通用性吗?其他语言很少有支持在函数内定义函数并把函数当值传递的,比较大众的语言中只有JavaScript支持这样的功能,而JavaScript又被许多人给用烂了,讨论JavaScript的都是讨论如何做一些特效的,根本没有讨论如何编程更优美的人。在豆瓣的Lisp小组中也能看到很多人学习Lisp主要是为了学习思想。学习Lisp的确能够让你学到在其他语言中学不到的很多思想,特别是《SICP》这本书,才到书的一半就已经提到了很多编程的模式了,学Lisp也并不是说其他语言就是垃圾,而是因为学习其他语言的人很少讨论语言的优雅性。总的来说学习Lisp能够真正让你体会到编程的乐趣。


  2. Ubuntu 11.10截图及Ubuntu发布规律

    October 15, 2011 by xudifsd

    好吧,这是我第一次写软文,但是今天刚刚试用了ubuntu11.10,感觉非常好。这次ubuntu使用了全新的LightDM登录管理器,非常漂亮,而且如果将面板调为半透明非常有感!

    现在我算是明白Canonical公司发布ubuntu的规律了,众所周知Canonical每隔6个月发布一个ubuntu版本,但是并不是每一个都值得去升级的,每隔两年它都会发布一个LTS(长期支持)版本,这样的版本是绝对推荐升级的,从ubuntu发布的历史来看8.04和10.04都是划时代的,但是其他的非长期支持版本就并不是太引人注目了,主要由于每次非长期支持版本会引进很多新功能,界面的跨度比较大,像11.04突然使用Unity界面,甚至在正式版中的启动器还有很多影响美观的bug。这样我们可以把非长期支持版本看成更大的dev版,Canonical通过发布非长期支持版本得到市场的反馈,再通过这些反馈得到一个真正的划时代版。

    按这个规律明年发布的12.04绝对值得期待!不说了,贴一些11.10的截图

    ubuntu11.10登录界面

    ubuntu11.10的lightdm登录界面

    ubuntu11.10_1

    ubuntu11.10中程序选择器到玻璃纸效果

    ubuntu11.10_2

    ubuntu11.10文件管理器样式

    ubuntu11.10_3

    ubuntu11.10桌面


  3. Git源码阅读——文件路径

    October 5, 2011 by xudifsd

    最开始在学习git用法的时候就听说了git不像其他版本管理软件(subversion)把版本信息分别放在各个子目录,而是将整个版本信息放在项目的根目录,当时就觉得这种实现似乎很有意思,但是却不知道如何实现这一点,因为每次运行git add等命令时都有可能在任意子目录。唯一能想到的方法就是绝对路径:所有版本的文件的路径都使用绝对路径来表示,但是这样一来将项目的目录进行移动或者分布式开发就有问题,而且使用od(1)来查看git的index文件也发现存的是相对路径而不是绝对路径。

    git的实现

    在源代码中就可以找到实现原理:几乎所有的git命令都会在启动时调用setup_git_directory,这是git的内部API,函数原型在setup.c中,这个函数就负责检查git环境并统一所有的文件路径:它尝试调用access(2)来判断该目录是否是git项目的根目录,如果不是则调用chdir(2)切换工作目录到父亲目录,如此循环直到到达根目录或者到达git项目根目录,如果成功到达项目根目录该API会返回从git根目录到之前工作目录的prefix,之后所有的对路径的操作就可以用prefix和执行命令时的相对路径来进行,git也提供了进行这样操作的API:prefix_path,这个函数负责去掉命令行参数路径中的.和..,并返回正确的路径。通过将路径统一成相对项目根目录的形式可以减轻对路径处理的工作量,所有上层命令只需在程序开始时调用setup_git_directory取得prefix,在操作路径时调用prefix_path,就能正确处理路径问题了。

    Linux环境中对路径的处理

    《APUE》可以得知所有的进程都有工作目录,所有的相对路径的操作都会基于工作目录,而chdir(2)可以让进程在不同的工作目录中进行切换,由内核负责保存进程的工作路径,想要取得当前工作路径只要使用getcwd(2)即可,但是需要注意的是工作目录是进程的属性,任何在子进程中修改的属性父进程都无法获得,所以在使用gdb进行调试时不可能使用getcwd来得到调试项目的工作路径的,因为调试项目是gdb的子进程。还有一点需要注意的是PWD环境变量,git在切换目录之后不会修改PWD环境变量,似乎也没有哪个应用程序会修改这个变量,这种环境变量似乎只是shell为了给shell脚本提供的,在应用程序中这样的变量是靠不住的。


  4. 缓存的威力

    October 2, 2011 by xudifsd

    “程序需要对非常难以计算的数值进行缓存,使用空间换取时间”

    相信大多数写过程序的都知道这一点,但是如果没有真正对比一下是不会留下深刻印象的。
    今天看《SICP》里提到斐波那契函数是树形的递归调用,突然想到计算斐波那契数可以非常好地显示缓存的威力,斐波那契数求法如下

    unsigned long long fib(unsigned int n){
        if ( n < 2 )
            return n;
        return fib(n-1) + fib(n-2);
    }

    这是一个递归的函数,对于参数为4的调用树见下图:

    fib

    斐波那契函数调用树

    从图中可以看出fib(4)函数会调用fib(3)和fib(2),然后fib(3)又会调用fib(2)和fib(1),问题就出在这:fib(4)调用了fib(2)一次,而fib(3)也调用了fib(2)一次,这样对于每次对fib函数的调用都会产生两棵完全相同的子树,这样的计算完全不划算,要计算的数值越大,重复的子数也就越多,但如果使用缓存效率就会有巨大的提升,所谓缓存就是先不进行计算,查看缓存中是否已经有计算好了的值,如果有就直接拿来用,没有再进行计算,并将结果存入缓存再返回。使用缓存的fib函数如下:

    unsigned long long fib_cache(unsigned int n){
        static unsigned long long *cache = NULL;
        if ( n < 2 )
            return n;
        if ( cache == NULL ) {
            cache = calloc(n - 1, sizeof(unsigned long long));
            memset(cache, n - 1, 0);
        }
        if ( cache[n - 2] == 0 )
            cache[n - 2] = fib_cache(n-1) + fib_cache(n-2);
        return cache[n - 2];
    }

    使用缓存后计算5000的斐波那契数也是瞬间完成,但是没有使用缓存的算法连50都让人等不下去了。
    这便是缓存的威力。