存档

文章标签 ‘Programming’

使用 Sikuli 实现同时登录两个 Dropbox 帐户

2010年2月1日 Solrex Yang 6 条评论

来自 MIT 的用图片编程的 Sikuli 语言最近着实火了一把,看着对岸的程序员 Vgod 开发出如此酷的软件着实令人羡慕。但除了 Demo 之外,能不能拿 Sikuli 来 engineer a better life 呢?显然是可以的,就如 Vgod 这篇文章所说,Sikuli 有无穷的潜力,那我们就来玩儿一把,展示一下 Sikuli 的一个现实应用。

1. Dropbox

Dropbox 是一个在线文件存储系统,可以用来存储和在不同电脑间共享文件,但是一个 Dropbox 用户只有 2G 的存储空间,当我们文件多的时候,就受到限制了。而一般情况下 Dropbox 只能运行一个例程,使用多个用户貌似不可行。但是到底可能吗?

当然可能,只是我们需要多个 Windows 帐户。也就是说,每个 Windows 帐户可以运行一个 Dropbox,如果你系统里有多个帐户,就可以运行多个 Dropbox。注意,受到安全策略的限制,这些帐户必须设置密码。比如我们新建一个"dropbox"帐户,密码也是"dropbox"。

2. 笨的方法

一般情况下使用其它帐户运行程序的方式为:在程序或者快捷方式上点右键,选择“运行方式”,然后选择“下列用户”,输入你期望的用户和密码(dropbox:dropbox)来执行该程序。

3. 聪明的方法

但是这样做太麻烦了,我们可以用批处理脚本做这件事情:

start D:\Program\Dropbox\Dropbox.exe
runas /user:dropbox D:\Program\Dropbox\Dropbox.exe

但这样还要手工输入密码,有很多种方法可以避免手工输入 runas 密码,但很遗憾它们大多在 Windows XP Home Edition 上不可用。

用 Home Edition 的同志还是得交互式的输入密码。能不能不手工输呢?可以,比如 expect 就是专门处理交互的语言。不过,学起来太麻烦了吧,要不来看看 Sikuli 怎么做?

4. 使用 Sikuli

下面这个图就是完成启动两个 Dropbox 的 Sikuli 程序:

使用 Sikuli 同时启动两个 Dropbox

首先switchApp("cmd")启动 Windows 的命令行,然后wait等待那个提示符出现,然后 type() 键入一行 runas 命令,wait 等待提示输入密码,type 输入密码 dropbox 加回车 \n,bingo,出来一个 dropbox 了,最后再 type 一行启动非 runas 的 dropbox,又出来一个 dropbox。

上述程序运行结果如下图所示:

两个 Dropbox 在运行

好玩吧!Sikuli 程序就是那么简单,我从下载 Sikuli 到完成这个程序大约花了四十分钟的时间,这可比去学 expect 快多了。这下 expact 之类的交互语言在简单的场景下可以无视了。

你可以将 Sikuli 程序导出成一个 .skl 文件,据说可以双击运行,不过我尝试未成功,这是一个遗憾,希望后续版本可以解决这个问题。

5. 注册 Dropbox

您如果对 Dropbox 感兴趣的话,可以点击下面我的两个邀请链接注册,这样咱们的空间都可以增加 250M。本人将非常感谢您的支持。(如果您打算再注册一个的话,最好不要用自己的邀请链接,因为同一台电脑上激活的用户不会奖励空间。)

https://www.dropbox.com/referrals/NTI0OTY1Mzk5
https://www.dropbox.com/referrals/NTE2NjMyMTU5

Math in CS:置换的轮换分解

2009年10月18日 Solrex Yang 7 条评论

随便一本《近世代数》或者《抽象代数》书上在讲到置换群的时候,应该都会讲到这样一个定理:
任何一个置换都可以表示为不相交轮换的乘积,若不计因子的顺序,其分解式是唯一的。

一、简单解释

没有数学背景的人,这句话很难读懂,下面我们来看一个简单的例子。假设我们有这样一个置换 P:

1, 2, 3, 4, 5
2, 5, 4, 3, 1

那么这个置换是什么样的轮换的乘积呢?我们先从 1 出发,1 被换到 2,2 被换到 5,5 又被换到 1,这就是一个轮换;然后再从 3 出发,3 被换到 4,4 又被换到 3,这又是一个轮换。也就是说 P 是两个不相交轮换 (1, 2, 5) 和 (3,4) 的乘积。

二、一个应用:全排列判断问题

下面我们来看这个定理有什么作用,考虑下面这道题目[1][2]:

给一个 n 长的数组,判断它是否为一个 1, 2, ..., n 的全排列,要求在线性时间,常数空间内实现。

我们可以容易看到,每个全排列都可以视为 1, 2, ..., n 上的一个置换。问题就转化为检测该数组是不是一个 1, 2, ..., n 的置换。由本文开头提到的定理可知,我们只需要检查该置换是不是由不相交的轮换构成的即可。

还是上面那个例子,怎么检查

1, 2, 3, 4, 5
2, 5, 4, 3, 1

是不是一个置换呢?首先从 1 开始,a[1]=2,那么再检查 a[a[1]]=a[2]=5,然后再检查a[a[a[1]]]=a[5]=1,这样就发现了一个轮换 (1, 2, 5)。然后接下来检测第二个,第三个轮换...

如何保证检查的高效以及所有轮换都不相交呢?我们每次检查完一个数,就将它置负,这样遇到负值,循环就终止了。如果终止前检查的那个数与起始的数相同,那么我们就发现了一个轮换,否则它就不是一个轮换,说明 P 不是一个置换。由于检查过的轮换中的数字都被置为负值,所以第二个轮换肯定不会与第一个轮换相交。如果到最后所有的数都被置为负值,且循环正常终止,那么说明它们都在不相交的轮换里,那么 P 就是一个置换。

如果想要查找过程不影响最终数组的值,到最后把所有置负的元素都重新置正即可。

代码实现如下[2]:

/* We use a n+1 elements array a[n+1] for convenience. a[0] is used to store
 * the return value, thus is not part of the permutation.  */
int test_perm(int *a, int n)
{
  int i, j;
  if (a == NULL)  return 0;     /* Test input */
  a[0] = 1;
  for (i = 1; i <= n; ++i)      /* Test input */
    if (a[i] < 1 || a[i] > n) { /* Is a[i] in the range 1~n? */
      a[0] = 0;
      return a[0];
    }

  for (i = 1; i <= n; ++i)
    if (a[i] > 0) {
      j = i;
      while (a[j] > 0) {        /* Follow the cycle */
        a[j] = -a[j];
        j = -a[j];
      }
      if (j != i)  a[0] = 0;    /* Test the cycle */
    }

  for (i = 1; i <= n; ++i)
    a[i] = a[i] > 0 ? a[i] : -a[i];

  return a[0];
}

三、另一个应用:100 囚徒碰运气问题

那么这个定理还有其它的用处没有呢?考虑下面这道题目[3][4]:

100 个囚犯,每人有一个从 1 到 100 的不重复不遗漏的号码,国王把这些号码收集起来,打乱放进 100 个箱子里,每个箱子里有且仅有一个号码。囚犯们一个一个地来到 100 个箱子面前,每人可以打开至多 50 个箱子来寻找自己的号码,可以一个一个打开(即可以根据之前箱子里看到的号码来决定后面要打开的箱子)。如果有一个囚犯没有找到自己的号码,那么这 100 个人一起被处死;只有当所有的囚犯都找到了自己的号码,他们才会被国王全部释放。

囚犯们可以在没开箱子前商量对策,但是一但打开了箱子,他就不能告诉别人箱子和号码的对应关系。问他们应该用什么样的策略以保证最大的存活概率?

显然,每个人随机选 50 个箱子打开,100 个人的存活概率会是 1/2 的 100 次方,即1/1267650600228229401496703205376,可以小到忽略不计。但是事实上有一种极简单的办法,其存活概率高达 30% 。至于有没有更好的办法?我不知道。

存活率达 30% 的策略就是:

囚犯打开自己号码对应的箱子,就按照箱子中的号码打开另一个箱子,一直到找到自己号码或者选50 次为止,这样就能保证整体有 30% 的存活概率。

这个策略背后的数学原理是什么呢?其实国王所作的事情,就是一个 1 到 100 元素集合的置换,囚犯所做的事情,就是顺着自己号码所在的轮换找自己号码。那么什么时候所有人都不用死呢?就是这个置换中所有的轮换长度都不大于 50,因为每个囚犯号码的轮换都不大于 50,那么他总能在 50 次以内找到自己的号码。

怎么计算这个概率 P 呢?{这个置换中所有的轮换长度都不大于 50 的概率},就是 1 - {存在轮换长度大于 50 的概率},进而 1 - {存在轮换长度为 51, 52, ..., 100 的概率},由此,我们可以得到下面的等式:

P=1-\frac{1}{100!}\sum_{k=51}^{100}\binom{100}{k}(k-1)!(100-k)!=1-\sum_{k=51}^{100}%20\frac{1}{k}=1-(H_{100}-H_{50})

其中,Hn 代表调和数(Harmonic Number)。虽然调和数没有精确的公式,但是我们知道调和数和自然对数有着密切的联系[5],那么我们就可以用自然对数来近似:

P\approx1-(ln(100)-ln(50))=1-ln(2)\approx0.30685281944005469059[6]

因此,我们可以得到,使用这种策略 100个囚犯的存活概率 P 约为 30%。

[1] http://yueweitang.org/bbs/topic/22
[2] http://fayaa.com/tiku/view/84/
[3] http://tydsh.spaces.live.com/Blog/cns!435F1A315756AD5D!833.entry
[4] http://fayaa.com/tiku/view/141/
[5] http://en.wikipedia.org/wiki/Harmonic_number#Calculation
[6] 求和得到的更精确的结果是:0.31182782068980479698,Bash 代码:

STR="1-("
for i in `seq 51 99`; do
  STR+="1/$i+"
done
STR+="1/100)"
echo $STR | bc -l

Cygwin GCC qsort 函数错误(续)

2009年10月16日 Solrex Yang 没有评论

上一篇文章中提到我在为 qsort 写 compare 函数时犯了一个愚蠢的错误:我脑袋陷入了一个错误的逻辑,以为 compare 函数嘛,就是要 compare 一下,那么我用 '>' 或者 '< ' 这种比较算符就可以满足要求(潜意识里认为 > 会返回 1 或者 -1,显然是错的,上篇文章的评论者 Stephen 开始也犯了同样的直觉错误,不过他马上就醒悟过来了)。我当时脑袋里也犹豫了一下要不要处理相等的情况,后来想快排算法中没有判断相等的情况,那么我没必要加上等号。

这个错误直接导致了快排算法失效。

但是为什么在 Linux 下的 gcc 可以输出正确的排序结果呢?我想了很久,最终还是把 glibc 的代码看了一下,才发现,原来当数组规模比较小时时(数组大小小于物理内存的四分之一),glibc 的 qsort 其实不使用 quick sort(_quicksort),而是使用 merge sort(msort_with_tmp)。而且在 msort_with_tmp 中,对 compare 的处理是比较其返回值是否 <=0,这样排序的结果就是正确的了。[1]

事实上最简单的快排算法是只使用 '<' 号或者 '<='的,比如 Wikipedia 上给出的快排算法,那么我们的 compare 只返回 -1 和 0 行吗?这取决于实现,比如对快排算法的优化中有一个就是对数组中有大量相等元素情况下的优化,其中一种实现 Three-way partition, 就需要使用到三种情况:大于、小于或等于。原始的快排 partition 是将数组按照与 pivot 的比较分为两段,Three-way partition 则是将数组分为三段,中间增加一段与 pivot 值相等的子数组。C 玩具代码的实现如下:

void qsort_3way(int a[], int lo, int hi)
{
  if (hi <= lo) return;
  int lt = lo, gt = hi, i = lt;
  int v = a[lo], t;
  while (i <= gt) {
    if (a[i] < v) {
      t = a[i]; a[i] = a[lt]; a[lt] = t;
      ++i; ++lt;
    } else if (a[i] > v) {
      t = a[i]; a[i] = a[gt]; a[gt] = t;
      --gt;  
    } else i++;
  }
  qsort_3way(a, lo, lt - 1);
  qsort_3way(a, gt + 1, hi);
}

但是 '<' 和 '>' 真的都需要吗?理论上来讲,'>' 是不需要的,我们显然可以将 a[i] > v 改成 v < a[i]。这也是 C++ 里面做的,C++ 中的 sort 函数只需要类重载 '< ' 运算符。但是 C 中并没有这种约定,我们不能预设 qsort 如何拿 compare() 的返回值与 0 比较。因此让 compare() 按照 C 的约定,返回大于、小于和等于 0 的三种情况是绝对正确的而且必要的。

我了解了正确的结果怎么得来的,但是我仍然不知道错误的结果是怎么得来的。看起来 Cygwin 使用的 libc 中没有采取类似 Linux 下 gcc 的策略(比如无法取到物理内存大小?)。quick sort 算法有很多优化的技巧和实现:有的使用 '< ' 符号比较,有的在分支数组足够小时采用插入排序,有的同时使用 '<', '> 两个符号,有的随机取 pivot,有的取三点中值作为 pivot。[2] 没有看到代码和调试,很难判断 Cygwin 的 libc 使用了什么算法(当然,尝试分析不同的输入输出是可以得到规律的,比密码分析还是要简单一些)。

[1] glibc/stdlib/msort.c.
[2] Jon Bentley and M. Douglas McIlroy, "Engineering a sort function", Software - Practice and Experience, Vol. 23 (11), 1249-1265, 1993.

Cygwin GCC qsort 函数错误

2009年10月13日 Solrex Yang 4 条评论

我平时在 Windows 下写代码时,经常使用 Cygwin 的 gcc。但是今天我居然发现 Cygwin 下 gcc 的 qsort 函数是错误的!这种基本的函数出错,太让人惊讶了。为了验证是不是代码有错,我使用 tcc 和 Linux 下的 gcc 都编译了同样一段程序,它们两个都输出了期望的结果,只有 Cygwin 的 gcc 是错的。下面是示例代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *p, const void *q)
{
  return *(const char *)p > *(const char *)q;
}

int main()
{
  char a[] = "1312515";
  printf("%sn", a);
  qsort(a, strlen(a), sizeof(char), compare);
  printf("%sn", a);
  return 0;
}

按说它应该输出:

1312515
1112355

但是我用 Cygwin gcc 编译后,它居然运行出这样的结果:

1312515
2111355

太诡异了。我尝试调试它,结果 gdb 无法步入 qsort 代码中。谁能告诉我是为什么?

附 Cygwin gcc 信息:

$ gcc -v
Using built-in specs.
Target: i686-pc-cygwin
Configured with: /gnu/gcc/package/gcc4-4.3.2-2/src/gcc-4.3.2/configure --srcdir=/gnu/gcc/package/gcc4-4.3.2-2/src/gcc-4.3.2 --prefix=/usr --exec-prefix=/usr --bindir=/usr/bin --sbindir=/usr/sbin --libexecdir=/usr/sbin --datadir=/usr/share --localstatedir=/var --sysconfdir=/etc --infodir=/usr/share/info --mandir=/usr/share/man --datadir=/usr/share --infodir=/usr/share/info --mandir=/usr/share/man -v --with-gmp=/usr --with-mpfr=/usr --enable-bootstrap --enable-version-specific-runtime-libs --with-slibdir=/usr/bin --libexecdir=/usr/lib --enable-static --enable-shared --enable-shared-libgcc --enable-__cxa_atexit --with-gnu-ld --with-gnu-as --with-dwarf2 --disable-sjlj-exceptions --enable-languages=ada,c,c++,fortran,java,objc,obj-c++ --disable-symvers --enable-libjava --program-suffix=-4 --enable-libgomp --enable-libssp --enable-libada --enable-threads=posix AS=/opt/gcc-tools/bin/as.exe AS_FOR_TARGET=/opt/gcc-tools/bin/as.exe LD=/opt/gcc-tools/bin/ld.exe LD_FOR_TARGET=/opt/gcc-tools/bin/ld.exe
Thread model: posix
gcc version 4.3.2 20080827 (beta) 2 (GCC)

我犯了一个愚蠢的错误,感谢来自 Stephen 的评论

你的compare函数有问题,你的compare函数不会返回负数。修改compare为:
int compare(const void *p, const void *q)
{
return *(const char *)p - *(const char *)q;
}
再编译运行就正确了。

字符串参数的模板函数推导问题(续)

2009年10月7日 Solrex Yang 没有评论

前面一篇文章我们讨论了字符串作为参数的模板函数推导问题,下面我们看一下使用不同字符串参数类型对模板函数实例化的影响。代码如下,在语句后面的注释为该句的输出。该输出是 g++ 编译后产生的输出,主要是因为输出简洁,而且我们这里只关心模板函数的不同实例,并不关心 const 类型。

#include <iostream>
#include <typeinfo>
#include <vector>
#include <string>
using namespace std;

template<typename T>
void foo(const T& t)
{
  cout << "foo: generic(" << t << ") " << typeid(t).name() << endl;
}

template<typename T>
void bar(const T t)
{
  cout << "bar: generic(" << t << ") " << typeid(t).name() << endl;
}

/*
$ c++filt [-t] A1_c A2_c A3_c Ss PKc
char [1]
char [2]
char [3]
std::basic_string<char, std::char_traits<char>, std::allocator<char> >
char const*
*/
int main()
{
  foo("");                              // foo: generic() A1_c
  foo("0");                             // foo: generic(0) A2_c
  foo("01");                            // foo: generic(01) A3_c
  foo(static_cast<string>(""));         // foo: generic() Ss
  foo(static_cast<string>("0"));        // foo: generic(0) Ss
  foo(static_cast<string>("01"));       // foo: generic(01) Ss
  foo(static_cast<const char *>(""));   // foo: generic() PKc
  foo(static_cast<const char *>("0"));  // foo: generic(0) PKc
  foo(static_cast<const char *>("01")); // foo: generic(01) PKc
  foo(*(new string("")));               // foo: generic() Ss
  foo(*(new string("0")));              // foo: generic(0) Ss
  foo(*(new string("01")));             // foo: generic(01) Ss
  bar("");                              // foo: generic() PKc
  bar("0");                             // foo: generic(0) PKc
  bar("01");                            // foo: generic(01) PKc
  bar(static_cast<string>(""));         // foo: generic() Ss
  bar(static_cast<string>("0"));        // foo: generic(0) Ss
  bar(static_cast<string>("01"));       // foo: generic(01) Ss
  bar(static_cast<const char *>(""));   // foo: generic() PKc
  bar(static_cast<const char *>("0"));  // foo: generic(0) PKc
  bar(static_cast<const char *>("01")); // foo: generic(01) PKc
  bar(*(new string("")));               // foo: generic() Ss
  bar(*(new string("0")));              // foo: generic(0) Ss
  bar(*(new string("01")));             // foo: generic(01) Ss
  return 0;
}

基于前一篇博客的分析,我们知道形如 "hello" 的常量字符串在编译时的类型是 char 数组。不同长度的 char 数组,其类型是不一样的,我们可以使用下面语句:

cout << (typeid(char [1]) == typeid(char [2])) << endl;

来验证这一想法。因此,如果我们使用不同长度的字符串作为参数调用 foo,编译器就会为模板函数 foo 实例化不同的实例函数,这一点已经由 foo 的前三个输出验证。我们还可以通过 readelf 来读取目标文件符号表,或者 objdump 查看目标文件反汇编代码中 foo 的实例函数的数量。

$ readelf -s test.o | c++filt -t | less
$ objdump -S test.o | c++filt -t | less

这也就是说,我们使用原始字符串调用了三次 foo,其实是三个不同的实例函数,这样显然会导致目标代码臃肿。那么怎么避免这种情况出现呢?下面我们使用了三种不同的方法,将字符串 static_cast 成 string 或者 const char * 类型,或者使用字符串构造一个 string 对象作为参数,这三种情况都能保证不同(内容)字符串参数的调用使用的是同一个实例化的模板函数。

有没有方法避免类型转换呢?我们可以使用非引用参数类型作为模板函数的模板参数,如 bar 模板函数所示。如前一篇中的分析,此时 char 数组类型会被隐式转换成 char 指针类型,然后进行模板函数推导。所以我们看到即使传的是原始字符串参数,其调用的实例化函数仍然是 char const * 类型的。由于这里类型 T 被推导为 char const * 类型,所以传递的仍然是指针。

但是下面的 string 类型的实例化模板函数实现的就是值传递了,这在函数运行效率上可能会有一些影响。不过现代的函数库对 string 都实现为 copy-on-write(例如 MFC 的 CString 和 Qt 的 QString),我想 STL 的 string 应该也不例外,而 const T 参数并不允许对参数修改,所以效率上的影响应该还是比较小的。只是在语义上与传一个指针就有不同了,假如不限定 T 是 const,那么值传递 string 时,对 string 的修改就无法反映到原来 string 上了。

最后,到底哪个方法好呢?我不知道,我没有足够的实践经验来评论哪种方法更好。我这两篇文章的目的仅仅是探讨一下使用不同形式字符串作为模板函数参数时可能发生的奇怪现象,以及要注意的方面,至于哪种方法更好,可能要留待实际需求来决定。

附:第一段代码的 VS 2008 编译器编译结果执行的输出:

foo: generic() char const [1]
foo: generic(0) char const [2]
foo: generic(01) char const [3]
foo: generic() class std::basic_string,class std::allocator >
foo: generic(0) class std::basic_string
,class std::allocator >
foo: generic(01) class std::basic_string
,class std::allocator >
foo: generic() char const *
foo: generic(0) char const *
foo: generic(01) char const *
foo: generic() class std::basic_string
,class std::allocator >
foo: generic(0) class std::basic_string
,class std::allocator >
foo: generic(01) class std::basic_string
,class std::allocator >
bar: generic () char const *
bar: generic (0) char const *
bar: generic (01) char const *
bar: generic () class std::basic_string
,class std::allocator >
bar: generic (0) class std::basic_string
,class std::allocator >
bar: generic (01) class std::basic_string
,class std::allocator >
bar: generic () char const *
bar: generic (0) char const *
bar: generic (01) char const *
bar: generic () class std::basic_string
,class std::allocator >
bar: generic (0) class std::basic_string
,class std::allocator >
bar: generic (01) class std::basic_string
,class std::allocator >

字符串参数的模板函数推导问题

2009年10月6日 Solrex Yang 没有评论

国庆长假期间又翻了翻 《C++ Primer》,看到模板函数特化,就想起来以前遇到的一个问题。这个问题我曾经在 TopLanguage 讨论组请教过(链接),今天翻出来又仔细想了想,做一个总结吧。

困惑起源于以字符串作为参数,如何匹配到特化的模板函数。代码如下,其中注释部分是该句对应的输出(使用 VS2008 编译器,一会儿再讨论 g++ 的问题):

#include <iostream>
#include <typeinfo>
using namespace std;

template<typename T>
void foo(const T& t)
{
  cout << "foo: generic " << typeid(t).name() << endl;
}

template<>
void foo<const char *>(const char * const& t)
{
  cout << "foo: special " << typeid(t).name() << endl;
}

template<typename T>
void bar(const T t)
{
  cout << "bar: generic " << typeid(t).name() << endl;
}

template<>
void bar<const char *>(const char * t)
{
  cout << "bar: special " << typeid(t).name() << endl;
}

int main()
{
  char str[] = "hello";
  const char con_str[] = "hello";
  const char * const p = "hello";
  foo("hello");                                  // foo: generic char const [6]
  foo(static_cast<const char * const>("hello")); // foo: special char const *
  foo(static_cast<const char *>("hello"));       // foo: special char const *
  foo(str);                                      // foo: generic char const [6]
  foo(con_str);                                  // foo: generic char const [6]
  foo(p);                                        // foo: special char const *
  bar("hello");                                  // bar: special char const *
  bar(str);                                      // bar: generic char *
  bar(con_str);                                  // bar: special char const *
  bar(p);                                        // bar: special char const *
  cout << typeid("hello").name() << endl;        // char const [6]
  cout << typeid(str).name() << endl;            // char [6]
  cout << typeid(con_str).name() << endl;        // char const [6]
  cout << typeid(p).name() << endl;              // char const *
  return 0;
}

首先让我奇怪的问题是,第一个 foo 函数调用 foo("hello"),为什么实际调用的不是特化的 foo 函数?

其实这个例子是有起源的,《C++ Primer》第四版 Section 16.6.1 的最后给出这样一个例子:

// define the general compare template
template <class T>
int compare(const T& t1, const T& t2) { /* ... */ }

int main() {
    // uses the generic template definition
    int i = compare("hello", "world");
    // ...
}

// invalid program: explicit specialization after call
template<>
int compare<const char*>(const char* const& s1,
                         const char* const& s2)
{ /* ... */ }

并解释说:

This program is in error because a call that would match the specialization is made before the specialization is declared. When the compiler sees a call, it must know to expect a specialization for this version. Otherwise, the compiler is allowed to instantiate the function from the template definition.

那么我认为作者暗含的意思里有,compare("hello", "world") 这个函数调用是 match 特化的 compare 函数的。但是从我们给出的第一段代码输出来看,并不是这个样子的,所以我谨慎地怀疑,《C++ Primer》给出的这个例子是有错的。虽然这段程序的确有错,但是即使将特化函数提到前面,compare("hello", "world") 仍然不会调用该特化函数。

请教了别人、书本和标准之后,下面我试着对上面每句的输出做一下解释(当然,可能有错,请指正):

1.   foo("hello");                                  // foo: generic char const [6]

"hello"具有类型 char const [6],由于 foo 模板使用的是引用参数,因此数组实参不会被转换成指针,而是追求一个较为精确的匹配,因此编译器实例化一个 void foo<char const [6]>(const char (& t)[6]) 模板函数(VS2008),这也是为什么我们能看到参数的类型输出是 char const [6];

2.   foo(static_cast<const char * const>("hello")); // foo: special char const *

"hello"被 cast 成了 const char * const 类型,自然与特化的函数 void foo<const char *>(const char * const& t) 能够精确匹配,因此调用的是特化的 foo;

3.   foo(static_cast<const char *>("hello"));       // foo: special char const *

"hello"被 cast 成了 const char * 类型,虽然少了一个 const,但是 C++ 标准中有这样的说法:

14.8.2.3
If the orignial A is a reference type, A can be more cv-qualified than the deduced A

这种 cv-qualifier 并不影响推导,最终仍然是匹配到特化的 foo 函数;

4.   foo(str);                                      // foo: generic char const [6]

str 和 "hello" 也是仅仅相差一个 cv-qualifier,也不影响推导,其结果与 1 是一致的;

5.   foo(con_str);                                  // foo: generic char const [6]

con_str 和 "hello" 的类型一样,显然其结果与 1 应是一致的;

6.   foo(p);                                        // foo: special char const *

p 的类型其实就是 2 中参数被 cast 之后的类型,显然其结果应该与 2 一致;

7.   bar("hello");                                  // bar: special char const *

乍一看就有些奇怪,为什么把模板参数换成值(而不是引用),特化的情况就与 foo 不同了呢?C++ 标准中有这样的规定:

14.8.2.3
If A is not a reference type:
-- If P is an array type, the pointer type produced by the array-to-pointer standard conversion (4.2) is used in place of P for type deduction;

因此,这里 "hello" 原本是一个数组类型,由于模板的参数不是引用类型,所以 "hello" 的类型被转换为指针类型 char const * 参加推导,正好与特化的 bar 函数匹配;

8.   bar(str);                                      // bar: generic char *

由于模板参数不是引用类型,没有 const 限定的 str 无法匹配特化的 bar,因此编译器实例化一个 void bar<char *>(char * t) 模板函数;

9.   bar(con_str);                                  // bar: special char const *

由于 con_str 与 "hello" 的类型一样,因此其结果与 7 是一致的;

10.   bar(p);                                        // bar: special char const *

这里 p 的类型本身就是特化函数的参数类型,显然要被推导为调用特化函数。

解释完了字符串参数的模板函数推导问题,下面来讨论一下 g++ 和 VS2008 的不同。上面同样的代码,使用 g++ 编译之后,输出是这个样子的:

foo: generic A6_c
foo: special PKc
foo: special PKc
foo: generic A6_c
foo: generic A6_c
foo: special PKc
bar: special PKc
bar: generic Pc
bar: special PKc
bar: special PKc
A6_c
A6_c
A6_c
PKc

当然,需要解释的是 g++ 内部对符号的字面做了一些变化,我们可以使用 c++filt demangle 这些符号:

$ c++filt [-t] A6_c PKc Pc
char [6]
char const *
char *

与 VS2008 的输出相比,我有一个疑问,为什么 g++ 没有为 const char [6] 输出正确的 const 类型名呢?

还有,我们提到了第 1 种情况下,编译器为 foo("hello") 调用实例化了一个 void foo<char const [6]>(const char (& t)[6]) 类型的函数。假如我们提供了一个类似的特化函数,那么 foo("hello") 会调用该特化函数;但是,使用 g++ 编译器时,特化函数的类型必须是 void foo<char [6]>(const char (& t)[6]) 而不是 void foo<char const [6]>(const char (& t)[6]),这让我感觉非常奇怪。只有不提供模板参数时,比如 void foo(const char (& t)[6]),两个编译器才能都推导出调用特化函数。

需要验证的话,您可以尝试在第一段代码中增加下面两个特化函数,再在两个编译器上编译那段代码:

template<>
void foo<char [6]>(const char (& t)[6])
{
  cout << "foo: special<char [6]> " << typeid(t).name() << endl;
}

template<>
void foo<char const [6]>(const char (& t)[6])
{
  cout << "foo: special<char const [6]> " << typeid(t).name() << endl;
}

将文本文件读入数组-C语言实现

2009年9月29日 Solrex Yang 7 条评论

要求:使用 C 语言将文本文件的每一行读入为数组的一个元素,返回一个 char ** 指针。

由于行长度和文本文件行数均未知,相当于二维 char 数组的两维长度都未定义。由于 getline 函数可以自动扩充 char 数组长度,我最初的想法是使用 getline 得到每行,然后每次对 char ** 进行 realloc,直到读完整个文件。

但是这种做法并不好,首先 getline 是 glibc 的扩展,而不是 C 语言的标准函数,使用除 gcc 以外的编译器是不一定能编译通过的;其次,每次对 char ** 指针进行 realloc 显得代码很 ugly。可以使用 fgets 替代 getline,但是就要自己来控制一维 char 数组的长度。

后来想想,换了一种思路,首先将整个文件读入内存,然后根据 '\n' 的个数来计算文件的行数,作为二维数组的长度,然后将所有的 '\n' 替换成 '\0',并将每一行的指针赋给二维 char 数组,代码如下:

char ** text_2_array(const char *filename)
{
  char *p, **array;
  int lines;
  if(filename == NULL) return NULL;

  FILE *fp = fopen(filename, "r");
  if(fp == NULL) return NULL;

  /* Get file size. */
  fseek(fp, 0L, SEEK_END);
  long int f_size = ftell(fp);
  fseek(fp, 0L, SEEK_SET);

  /* Allocate space for file content. */
  char *buf = (char *) calloc(f_size, sizeof(char));
  if(buf == NULL) return NULL;

  fread(buf, sizeof(char), f_size, fp);
  fclose(fp);

  /* Get number of lines. */
  for(p=strchr(buf, '\n'), lines=1; p!=NULL; p=strchr(p, '\n'), lines++) {
    if(*p == '\n') p++;
  }

  /* Allocate space for array; split file buffer to lines by change '\n' to
     '\0'. */
  array = (char **) calloc(lines+1, sizeof(char*));
  array[0] = buf;
  for(p=strchr(buf, '\n'), lines=1; p!=NULL; p=strchr(p, '\n')) {
    if(*p == '\n') *p++ = '\0';
    if(p != NULL) array[lines++] = p;
  }
  /* Add a terminate NULL pointer. */
  array[lines] = NULL;
  return array;
}

其实读文本文件入数组这个功能在很多语言中是很简单的操作,比如 PHP 的 file 函数,或者 Bash 的 (`cat filename`),都可以直接实现这个功能。但是对 C 这种更低级的语言来说,貌似就没那么简单了。我想要了解的是,除了我上面提到的两种思路,有没有更简单或者直接的方法来解决这个问题?比如一些我不熟悉的函数,或者一些 trick。

豆瓣好友统计图标

2009年7月28日 Solrex Yang 3 条评论

自从 Feedburner 订阅数统计图标成为博客装逼工具之后,各种各样的统计图标层出不穷,比如我也使用的 Twitter Counter。但是我一直没发现我认为很有装逼范儿的豆瓣提供好友数统计图标,因此我就使用豆瓣的 API 自己搞了一个。其实我主要是觉得在博客侧栏放豆瓣图书列表太多了,而一个小“豆”字也没啥意思,搞个好友数图标就挺好玩了。

我想没准你也会感兴趣,所以我把这个服务发布了出来。豆瓣好友统计图标的主页在:

http://solrex.cn/douyou/

下面是直接从主页拷贝过来的内容,您也可以到我的博客侧栏看看效果。

介绍

呃——我觉得写主页比写主程序还费劲。简单来说,这个东西就跟 Feedburner 的订阅数统计图标类似,利用豆瓣提供的 API 抓取你的豆瓣好友数量,并做成一个小图片出来让你可以放在自己的博客上秀一秀。比如下面就是我的豆瓣好友统计图标:

豆瓣

你还可以移步到我的博客右侧栏,看看豆瓣好友统计图标和其它统计图标共存的状况。本统计图标一天更新一次,因此统计数并不完全实时,这是为了减轻服务器负载,请理解。

这个小项目完全是出于兴趣写成的,因此很简陋且维持在可用的水平上,我也没有更优化它的想法。在我服务器能承受的情况下我会尽量维持它,但本人不对服务的有效性和可用性做出任何承诺。

我觉得这个服务本身应该由豆瓣提供,如果你是豆瓣的工作人员,觉得这个站点有趣并想在豆瓣中加入此服务的话,欢迎你和我联系,我将无偿提供所有的代码,仅仅希望在对应产品中加上一个 Thanks to 到我的链接。

生成图片

输入豆瓣 UID:
(豆瓣用户 UID,英文或数字,非登录 email 地址)

(若没有即刻显示请稍等后多提交一次,服务器抓取信息可能有延迟。不知道自己的 UID 的话,可以登录豆瓣,查看自己的设置->username项。)

豆瓣

您可以把下面这段代码嵌入到您的博客或者主页中来显示豆瓣好友统计:

<a href="http://www.douban.com/people/solrex" title="豆瓣好友统计"><img src="http://solrex.cn/douyou/dc/solrex" style="border: 0pt none ;" alt="豆瓣" height="26" width="88"></a>

分类: IT, Programming 标签: , , , ,

JPerf Single Jar with UDP BW Unit Fixed

2009年7月22日 Solrex Yang 没有评论

JPerf is the GUI frond-end of IPerf, a TCP and UDP bandwidth performance measurement tool which allows the tuning of various parameters and UDP characteristics.

The official JPerf release (2.0.2 version) has some flaws. First, it mistakenly uses bytes/sec as the unit of UDP bandwidth, which should be bits/sec according to IPerf man-page:

-b, --bandwidth #[KM]
       for  UDP,  bandwidth  to  send  at  in  bits/sec (default 1 Mbit/sec,
       implies -u)

Second, starting it from command line is error prone. The command to start it (jperf.sh) is:

java -classpath jperf.jar:lib/forms-1.1.0.jar:lib/jcommon-1.0.10.jar:lib/jfreechart-1.0.6.jar:lib/swingx-0.9.6.jar net.nlanr.jperf.JPerf

We can see that all jar paths in classpath are relative paths. So if we create a symbol link to the jperf.sh script, e.g. /usr/bin/jperf -> /opt/jperf-2.0.2/jperf.sh. Then calling /usr/bin/jperf will result in some errors like:

Exception in thread "main" java.lang.NoClassDefFoundError: net/nlanr/jperf/JPerf
Caused by: java.lang.ClassNotFoundException: net.nlanr.jperf.JPerf
at java.net.URLClassLoader$1.run(URLClassLoader.java:200)
at java.security.AccessController.doPrivileged(Native Method)
at java.net.URLClassLoader.findClass(URLClassLoader.java:188)
at java.lang.ClassLoader.loadClass(ClassLoader.java:307)
at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:301)
at java.lang.ClassLoader.loadClass(ClassLoader.java:252)
at java.lang.ClassLoader.loadClassInternal(ClassLoader.java:320)
Could not find the main class: net.nlanr.jperf.JPerf. Program will exit.

This error can be fixed by resolving the real path of the symbol link, as I reported.

However, a better way to solve this problem is to pack all libs JPerf needed(i.e. forms*.jar, jcommon*.jar, jfreechart*.jar, swingx*.jar) to a single jar, and add a proper "Manifest". Then we will be able to start JPerf with a much simpler command:

java -jar jperf.jar

And finally, I gave a try to solve the above 2 flaws and put my work (deb/jar/src packets) on my site. You can find them here .

在 Ubuntu 9.04 上安装 Kscope

2009年7月8日 Solrex Yang 4 条评论

Kscope 是我很喜欢的 Linux 平台上的代码查看工具,因为我不会用 Emacs,vim + ctags 又用得不熟,看看小程序还可以,看大项目就傻眼了。以前也尝试过 Source-Navigator(这个项目N年没更新,06年时候我装都装不上,08年底居然又复活了,有空了再去试试)、Eclipse、Kdevelop、CodeBlocks,总之都没有 Kscope 用着最舒服。Kscope 让我欣赏的特点主要有:

1. 它号称是代码编辑环境(source-editing environment),而不是IDE。我不用在建立 Kscope 项目时烦心地去选择项目类型、编译器、编译选项等等。编译我有 Makefile,我就是找个工具看看代码,用得着那么麻烦吗。 建立 Kscope 项目时只需要干两件事:选择项目名、项目保存地址和添加源文件。

2. 它不会在源文件目录下建立一堆乱七八糟的文件,影响市容。我记得 Eclipse、CodeBlocks 等都会把项目信息保存在源文件目录下,而 Kscope 的项目保存位置可以自己选,比如我一般都保存在 workspace/kscope 目录下面,这样对要查看的源文件目录没有任何影响。因此 Kscope 的项目和源文件基本没关系,我可以添加任何位置的源文件到某个项目中去。

3. 它不会去读非指定类型的文件。这是针对 Eclipse 来说的,每次在 Eclipse 项目中搜索时,一堆 .svn 目录中文件的结果让我感觉非常闹心,两年没用不知道现在的 Eclipse 是不是更智能点儿了,但是 Eclipse 改不了的毛病就是慢和吃内存。

4. 它支持代码查看的基本功能。其实我最常用的也就那么几个功能:语法高亮、同时打开多文件、整个项目中搜索字符串、查找函数定义位置和引用、项目文件列表+搜索。在这些条上据说 Windows 下的 SourceInsight 做得更好,但我没用过没有发言权。

简而言之,Kscope 与其它工具比就是快、简单、省心。但是时代在变革呀,转眼到了 KDE4 的时代,而 Kscope 仍然停留在 KDE3.5 上。现在的 Ubuntu 9.04 的依赖关系里,居然已经撤掉了 Kscope,在 9.04 上 sudo apt-get install kscope,会得到这样的消息:E: Couldn't find package kscope,真是让人丧气。

其实 Kscope 之所以不能安装,主要原因是它依赖于 Kate 的两个库:libkateinterfaces.so.0 和 libkateinterfaces.so.0,只需要从 KDE3.5 的 Kate 中提取出来这两个库安装到系统中后,Kscope 就可以正常运行了。Ubuntu 9.04 的依赖关系中虽然找不到 Kscope,但是 Ubuntu 的软件仓库中还有 Kscope 的包,我们可以手动下载安装。下面这个脚本的功能就是自动安装 kscope 到 Ubuntu 9.04,稍微修改一下也可以用于在其它 KDE4 桌面系统中安装 Kscope,或者解决 Kscope 无法运行的问题。您也可以从这里下载到该脚本:

#!/bin/bash
# This script helps you install Kscope on Ubuntu 9.04.
# You can also use it to fix "Kscope doesn't run in KDE4" bug.

echo "Determining machine hardware name... "
MACHINE=`uname -m`
case "$MACHINE" in
  i386 | i586 | i686)
    ARCH="i386"
    ;;
  x86_64)
    ARCH="amd64"
    ;;
  *)
    ARCH="i386"
    ;;
esac

# If Kscope is not installed, install it.
which kscope &> /dev/null
if [ $? -ne 0 ]; then
  echo "Installing kscope..."
  sudo apt-get install kscope || \
  wget http://archive.ubuntu.com/ubuntu/pool/universe/k/kscope/kscope_1.6.0-1_${ARCH}.deb && \
  sudo dpkg -i kscope_*.deb || \
  sudo apt-get -fy install || \
  echo "Oops, some error happens..."
fi

kscope -v &> /dev/null
if [ $? -eq 0 ]; then
  echo "Kscope works fine."
  exit
fi

echo "Downloading KDE3 libraries needed by kscope..."
wget http://ftp.debian.org/debian/pool/main/k/kdebase/kate_3.5.9.dfsg.1-6_${ARCH}.deb
dpkg -x kate_3*.deb kate

echo "Installing KDE3 libraries..."
sudo cp kate/usr/lib/libkateinterfaces.so.0.0.0 /usr/local/lib/
sudo cp kate/usr/lib/libkateutils.so.0.0.0 /usr/local/lib
sudo ln -s /usr/local/lib/libkateinterfaces.so.0.0.0 /usr/local/lib/libkateinterfaces.so.0
sudo ln -s /usr/local/lib/libkateutils.so.0.0.0 /usr/local/lib/libkateutils.so.0
sudo ldconfig

echo "Finished."

分类: Linux 标签: , , , , ,