A Humble Programmer

这是我为Ruby中文电子期刊写的第一篇文章，顺便发在自己blog上。我准备抽空写出一个系列，在展示Ruby的语言特性的同时讨论一些程序设计和算法应用的技巧。错误在所难免，欢迎留言改正。

第一篇从一个所有学过程序设计的人都熟悉的问题说起，那就是 Fabonacci 数：

[tex] [ F_i = \begin{cases} i & 0 \le i < 2 \ F_{i-1} + F_{i-2} & i \ge 2 \end{cases} ] [/tex]

大学的第一门程序设计课时候通常会以这个为例子介绍递归。大家都知道用递归求 Fabonacci 数很慢，求第n个数的时间复杂度是[tex]$O(2^n)$[/tex]。大家也都知道改为迭代可以把时间复杂度降低到O(n)。用 Ruby 写出来就是：

f0=0
f1=1
for i in (2..100000)
    f0, f1 = f1, (f0+f1)
end
puts f1

这个程序计算第10万个 Fabonacci 数，不包括输出需要14.48秒（这个数字是用ruby -r profile得到的）。 能不能更快些呢？或许很多人会想到去找一个闭合公式(closed form)，其实仅依靠定义就可以找到更快的解法。下面介绍的算法时间复杂度为O(log(n))。注意到下面的等式成立：

[tex] \begin{pmatrix}F_{i+1} & F_i \end{pmatrix} = \begin{pmatrix} F_i & F_{i-1} \end{pmatrix} \times \begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix} [/tex]

所以要计算[tex]$F_n$[/tex]只要计算：

[tex] [ \begin{aligned} \begin{pmatrix}F_{n} & F_{n-1} \end{pmatrix} &= \begin{pmatrix} F_{n-1} & F_{n-2} \end{pmatrix} \times \begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix} \ &= \begin{pmatrix} F_{n-2} & F_{n-3} \end{pmatrix} \times \begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix}^2 \ & \cdots \ &= \begin{pmatrix} F_{1} & F_{0} \end{pmatrix} \times \begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix}^{n-1} \end{aligned} ] [/tex]

实现这个算法需要 Ruby 的 Matrix 模块：

require "matrix"

a = Matrix[[1,1],[1,0]]
b = Matrix[[1,0]]
c = b * (a ** (100000-1))
puts c[0,0]

这个新的程序只需要0.77秒。效率显著提高的原因在于计算[tex]A^n[/tex]只需要O(log(n))步。作为验证，我们不使用 Ruby 提供的幂操作符，自己求矩阵的n次方：

require "matrix"

a = Matrix[[1,1],[1,0]]
b = Matrix[[1,0]]
t = Matrix.I(2)    # 单位矩阵
i = 100000-1
c = a
while i != 1
    if (i % 2) == 0
        i = i / 2
        c = c * c
    else
        i = i - 1
        t = t * c
    end
end
d = b * t * c
puts d[0,0]

这个程序只需要0.65秒，说明 Ruby 内部对幂的实现基本是这样的。用自己的实现在效率上有微小的提高，原因可能是 Ruby 对幂操作符的实现有一些额外的操作。但对比最后两个程序，显然用语言提供的结构要简练很多，益处远超过效率的提高。

就语言的设计来说，上面的例子也体现了使用 Ruby 或 Python 这类动态语言描述算法的自然和优雅。不相信的话可以试试用C++或者Java实现一下上面的算法。;-)

• Update (Aug/7/2006): 我原本定义operator <<的时候用了 call-by-value，影响效率，应该改成 call-by-const-reference。现在已经改过了。

今天写了几个调试程序用的函数备用，主要是在TopCoder比赛的时候很有用。写例子测试的时候如果老用 insert() 和 push_back() 去构造容器的话很吃亏。

首先是个用任意类型的C数组初始化 C++ STL 容器的函数：

using namespace std;

template <typename T, typename C>
void init_container(C &container, const T array[], int n)
{
  insert_iterator<c> ii(container, container.begin());
  copy(&array[0], &array[n], ii);
}

后来想写个函数用来输出任意顺序容器的内容，开始是这样写的：

template<typename C>
  ostream & operator<<(ostream &os, const C &v)
  {
    std::operator<<(os, "[\t");
    copy(v.begin(), v.end(),
        ostream_iterator<typename C::value_type>(os, "\t"));
    std::operator<<(os, "]");
    return os;
  }

这样的话，所有类型的 << 都被重载了，输出非容器类型的时候就会出错。想来想去没有什么办法，就只好把它藏到一个 namespace 里，再分别给每个容器定义一个公开的操作符：

namespace very_private_ns {
  template<typename C>
    ostream & operator<<(ostream &os, const C &v)
    {
      std::operator<<(os, "[\t");
      copy(v.begin(), v.end(),
          ostream_iterator<typename C::value_type>(os, "\t"));
      std::operator<<(os, "]");
      return os;
    }
}

template<typename T>
ostream & operator<<(ostream &os, const vector<t> &v)
{
  return very_private_ns::operator<<(os, v);
}

template<typename T>
ostream & operator<<(ostream &os, const list<t> &v)
{
  return very_private_ns::operator<<(os, v);
}

这个办法感觉很不优雅，哪位有更好的方法请告诉我。

写个 main() 测试一下

int main()
{

  vector<int> vec;
  list<int> lis;
  int arr1[] = {1, 2, 3, 4, 5};
  int arr2[] = {4, 5, 6, 67, 83};
  init_container(vec, arr1, sizeof(arr1)/sizeof(int));
  init_container(lis, arr2, sizeof(arr2)/sizeof(int));
  cout << "vec = " << vec << endl;
  cout << "lis = " << lis << endl;
  return 0;
}

输出：

vec = [ 1       2       3       4       5       ]
lis = [ 4       5       6       67      83      ]

回到北京一个星期了，一直没时间写 blog

前段时间药师在准备出 C++ 面试题，这个题目是和他讨论的时候想到的：事先给出n，要求程序在编译时计算出第 n 个 Fibonacci 数，也就是说在运行时只是运行一个输出语句。这个问题可以用 template 解决。

首先是Fibonacci的递归定义：

template <int n>
struct fab {
    const static int value = fab<n-1>::value
        + fab<n-2>::value;
};

然后是 base cases:

template <>
struct fab<1> {
    const static int value = 1;
};

template <>
struct fab<2> {
    const static int value = 1;
};

例子：输出第20个 Fibonacci 数：

int main(void) {
    std::cout << fab<20>::value << std::endl;
    return 0;
}

关于这方面的技巧， Todd Veldhuizen 的 Template Metaprograms 是个不错的介绍。

简介

我使用Ruby不久，有句话叫“The best way to learn something is to teach it.“，所以我打算写几篇关于Ruby的文章，这是第一篇。为了对别人有些用，我尽量写一些一般的Ruby教程中不会着重讲的东西。

Alan J. Perlis说

A language that doesn’t affect the way you think about programming, is not worth knowing. Alan Perlis 是 Yale CS 的前辈，第一个图灵奖得主。这句话出自于Epigrams in Programming。

盲目地学新的语言确实是件无聊且浪费时间的事。不过对于用惯了传统的过程语言或者是 C++, JAVA 一类流行的面向对象语言的人来说， Ruby 或许是一个能让你对程序设计有更多思考的语言。对函数式程序设计语言（ functional language, 如 Haskell, ML, Lisp, etc. ）比较了解的人则会在这个被成为“纯面向对象“的语言中发现不少熟悉的元素。

问题说明

我的第一个 Ruby 程序是为了解决一个实际问题。以前我用 F-Spot 管理我的照片，这个软件功能设计不错，不过毕竟太新，总体质量只能算 alpha 水平，有一次 F-Spot 崩溃的时候把它的数据文件损坏了，从那以后 F-Spot 就不能再启动。 F-Spot 的目录树是按照照片的日期整理的（例如：在2005年7月28日照的照片被放在 $HOME/Photos/2005/07/08 中），脱离 F-Spot 就不好查找照片。最近把桌面从 Gnome 换成了 KDE ，也就用 digiKam 替换了 F-Spot 。我得把照片从原来 F-Spot 的目录结构中导出到同一层目录中，再用 digiKam 导入。由于 F-Spot 不能启动，所以只能自己想法实现了。过去一年我有数千张照片，分布在有四五百个目录的目录树中，自然不太可能用手工拷贝了。本来可以写一个 shell script 来做的，不过既然看了 Ruby ，就实践一下。

解法一

最直观的方法是递归遍历这个目录树，把每个叶结点（文件）复制到目标目录。为了代码可以重用，我先写一个函数返回一个包含所有文件的路径的数组，再用一个循环把每个文件移动到目标目录。这个方法用任何过程式语言都很容易实现。

#!/usr/bin/env ruby

require 'pathname'

def getFileNames(path_str)
  path = Pathname.new(path_str)
  filenames = []
  path.children.each do |entry|
    if entry.directory?
      subentries = getFileNames(entry)
      subentries.each {|f| filenames << f}
    elsif entry.file?
      filenames << entry
    end
  end
  return filenames
end

getFileNames(ARGV[0]).each {|f| `mv #{f} #{ARGV[0]}`}

这样做虽然直观，但缺点是遍历目录树的时候只是找出所有文件，要对文件做具体操作还要再遍历返回的文件列表，效率比较低。如果把对文件的操作（如移动、删除等）放到遍历目录树的代码中，则这些代码无法再做其他用途。

除此之外还有一个更加微妙的问题。如果文件的数量很多，遍历目录树会花费较长时间。假设这个程序不是用来整理个人的文件而是用来管理一个分布式文件系统，或者是一个并行系统的一部分， 那么在遍历目录树和对文件进行具体操作之间一些文件很可能已经被别的进程移动或删除，使得旧的文件名无效。一个安全的实现应该在这个期间把这些文件锁住，但这样的话别的进程就在一段相对较长的时间內无法操作这些文件。

解法二（higher-order function and closure）

由于在 Ruby 中函数是普通的数据类型，一个对解法一理所当然的改进是把要对每个文件进行的操作作为参数传给遍历函数。把一个函数作为参数传递给另一个函数术语叫 higher-order function ，不知道正确的中文说法是什么（高阶函数？），知道的朋友请告知。这样既可以保持遍历函数的通用性，又能在遍历目录的同时完成对文件的操作。修改后的遍历函数如下：

def walk_dir(path_str, op)
  path = Pathname.new(path_str)
  path.children.each do |entry|
    if entry.directory?
      walk_dir(entry, op)
    elsif entry.file?
      op.call(entry)
    end
  end
end

对文件的操作由参数决定，比如下面的调用打印出指定目录及子目录下的所有文件

walk_dir(ARGV[0], lambda {|f| puts f})

另外一个实现同样效果的方法是传递一个代码块 closure 。因为省掉了一个参数，这样看起来更加简洁。

def walk_dir(path_str)
  path = Pathname.new(path_str)
  path.children.each do |entry|
    if entry.directory?
      walk_dir(entry) {|x| yield(x)}
    elsif entry.file?
      yield(entry)
    end
  end
end

类似地，打印所有文件的路径：

walk_dir(ARGV[0]) {|f| puts f}

解法三（Curry）

上面的遍历函数看似已经很通用，其实仍有不足。解法二中的遍历函数可以很方便地对目录树里的每个文件进行操作，可是一些常见的对文件系统的操作对于每个文件并不是独立的，比如：

• 计算所有文件大小的总和
• 查找最大或最小的文件
• 查找重复的文件

这些任务的特点是在遍历的同时必须访问、积累和修改一些辅助信息。我们还是可以用解法二，把这些辅助信息放在全局变量里，但这个办法不elegent，一般来说全局变量是应该尽量避免的。另一种办法是增加额外的变量，以在遍历的时候传递额外的信息，但这样会使负责遍历树的代码变得复杂和不通用。

解决问题的一个办法在程序设计语言里面叫curry，也叫 partial function application ，后面这个名称更加形象一些。简单地说，如果 f(x, y) 是一个关于x和y的函数，如果把x的值固定（如x=1)，那么 f(1,y) 就是一个关于y的函数。这种通过把一个函数的部分参数确定使它成为一个新函数的技巧就叫做 curry 。ruby 中函数的参数和返回值都可以是函数，所以很容易实现 curry。

def walk_dir(path_str, fun)
  path = Pathname.new(path_str)
  path.children.each do |entry|
    if entry.directory?
      fun=walk_dir(entry, fun)
    elsif entry.file?
      fun = fun.call(entry)
    end
  end
  return fun
end

这样对树结构的操作可以方便地封装起来，如求目录树中所有文件的大小：

def cur_sum(sum)
 return lambda {|file| (file==nil) ? sum : cur_sum(sum + file.size)}
end

然后再传递给遍历过程：

puts walk_dir(ARGV[0], cur_sum(0)).call(nil)

这个方法有个缺点：上面的cur_sum函数返回值的类型不确定。如果参数是nil，返回值就是一个整数，否则的话返回一个函数。一般来说，这在程序设计中应该避免。这种现象只有在动态类型（ dynamic-typing ）的语言里面有可能，在 C++ 和 JAVA 一类语言里面是不会出现的。

解法四（Monad）

我觉得最通用的解法是使用Monad关于Monad，可参考Wikipedia: Monads in Functional Programming。Monad 最初来自于 category theory ，在 Haskell 里面是一个很普遍的概念，随处可见，为了保持 Haskell 的纯函数性，几乎所有的 side effect 都是用 Monad 实现的。简单地说， monad 是用来实现除纯数学和逻辑计算以外的隐含操作的方法，如错误和异常处理，输入输出等等。把这些方面封装起来，可以让设计者把精力集中到程序中最重要的逻辑。这个概念通常比较难以理解，不过我们的例子很简单，只需要使用最简单的 Identity monad：

class Identity
  attr_reader :value
  def initialize(v)
    @value = v
  end

  def Identity.m_return(v)
    new(v)
  end

  def bind
    yield @value
  end
end

遍历过程调用所有Monad都具有的通用操作bind，并不关心对树节点的具体操作。对节点的处理完全封装在参数op里。

def walk_dir(path_str, m, op)
  path = Pathname.new(path_str)
  path.children.each do |entry|
    m = m.bind { |v| m.class.m_return(op.call(v, entry)) }
    if entry.directory?
      m = walk_dir(entry, m, op)
    end
  end
  return m
end

下面的调用求目录树中所有文件大小的总和：

m = Identity.m_return(0)
puts walk_dir(ARGV[0], m,
    lambda {|v,e| e.file? && (v + e.size) || v}).value

---