终于可以优雅的捕获 shell heredoc 内容了

作者: rockeet 发表日期: 2010年02月06日分类: shell 评论: 0 条阅读次数: 2,401 次

看下面的示例：继续阅读 →

shell heredoc 微妙之处

作者: rockeet 发表日期: 2010年02月05日分类: shell 评论: 0 条阅读次数: 2,620 次

here doc 的一般用法是：

[cmd] <<word
here-document
delimiter

继续阅读 →

通过管道向 hadoop put 文件

作者: rockeet 发表日期: 2010年02月05日分类: MapReduce, shell 评论: 0 条阅读次数: 2,501 次

使用 hadoop file shell 可以方便地向 hdfs put 文件，但是，该 shell 不支持从管道读取数据并放到 hdfs 文件中。它仅支持这样的 put 命令：继续阅读 →

shell 中验证管道是否正确执行

作者: rockeet 发表日期: 2010年02月05日分类: shell 评论: 0 条阅读次数: 2,467 次

象这样的 shell 代码： prog1 | prog2 | prog3 | prog4

$? 只能得到最后一个命令的返回值，该如何检查整个命令是否全部正确执行？

有一个数组变量PIPESTATUS，保存了最近一个管道命令中所有子命令的返回值

该返回值与 $? 一样，每次命令都会改写它，因此，要保存它就必须马上！

用以下代码可以检查管道命令:

prog1 | prog2 | prog3 | prog4
if [[ "0 0 0 0" == ${PIPESTATUS[*]} ]]
then
    echo success
else
    echo failed &gt;&amp;2
fi

1

2

3

4

5

6

7

prog1 | prog2 | prog3 | prog4

if [[ "0 0 0 0" == ${PIPESTATUS[*]} ]]

then

echo success

else

echo failed >&2

fi

my PipelineProcessor

作者: rockeet 发表日期: 2010年02月05日分类: C++, 操作系统评论: 0 条阅读次数: 2,229 次

刚看到，intel tbb::pipeline 实现的功能，和我以前实现的一个pipeline ： febird::thread::PipelineProcessor
，介绍：

1. 多线程的 pipeline 设计模式

2. 多线程 Pipeline 的改进

几乎就是同一个东西：多线程流水线执行，按次序，stage划分……

可惜啊，它只在我的几个程序中用过，现在有了tbb，它还没来得及壮大就得夭折了。

聊以自慰：

1. 英雄所见略同

2. 这个轮子很有价值

3. 发明轮子之前，先多看看

4. 多看看，碰到问题就免得发明轮子

简单的代码生成器创建领域语言

作者: rockeet 发表日期: 2010年02月05日分类: C++, shell, 操作系统, 杂谈评论: 0 条阅读次数: 2,841 次

有一类问题，代码模板相同，但有少部分地方不同，一般可以写一个复杂的程序，使用不同的选项，完成不同的任务。或者，把公共的部分抽象成一个代码库，然后在不同程序中引用。但是，如果公共的部分很少，并且比较“专用”，或者因为其它原因，比较难以部署。怎么办？

实际上，有另一种完全不同的编程模式来实现：代码生成器。unix世界中最知名的代码生成器莫过于lex和yacc了。但是，不比每个代码生成器都那么复杂，比如这个代码生成器就非常简单，它只是简单地转换行记录：

#! /bin/sh
field_seperator="||"
output=b
while getopts :F:vo: arg
do
case $arg in
        F ) field_seperator=$OPTARG;;
        v ) ;;
        o ) output=$OPTARG;;
        : ) echo "$0: missing arg for -$OPTARG " >&2
            exit;;
        /?) echo "Invalid option -$OPTARG ignored." >&2
            exit;;
esac
done
if [ $OPTIND -gt $# ]
then
#       echo OPTIND=$OPTIND argc=$# >&2
        echo "no program" >&2
        exit
fi
program=${!#}
echo field_seperator=$field_seperator
cat > a.cpp <<+TemplateCFile
#include <vector>
#include <string.h>
#include <stdio.h>
const char field_seperator[]="||";
void split_row(char* line, std::vector<char*>& F, const char* fs)
{
        char* col = line;
        F.resize(0);
        size_t fslen = strlen(fs);
        if (fslen == 1) {
                for (;;) {
                        F.push_back(col);
                        col = strchr(col, fs[0]);
                        if (col) {
                                col[0] = '/0';
                                col += 1;
                        } else
                                break;
                }
        }
        else {
                for (;;) {
                        F.push_back(col);
                        col = strstr(col, fs);
                        if (col) {
                                col[0] = '/0';
                                col += fslen;
                        } else
                                break;
                }
        }
}
int main(int argc, char* argv[])
{
        size_t  len1 = 0;
        ssize_t len2;
        char*   line = NULL;
        std::vector<char*> F;
        while ((len2 = getline(&line, &len1, stdin)) != -1)
        {
                split_row(line, F, field_seperator);
                int NF = F.size();
//--- begin user program
+TemplateCFile
echo $program >> a.cpp
cat >> a.cpp <<+TemplateCFile
//--- end user program
; // avoid user program missing ;
                printf("/n");
        }
        if (line) free(line);
        if (ferror(stdin)) {
                perror("ferror(stdin)");
                return 1;
        }
        return 0;
}
+TemplateCFile
sed -i 's//(field_seperator/[/]=/).*";//1"'$field_seperator'";/g' a.cpp
gcc -O2 a.cpp -lstdc++ -o $output
exit $?

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

#! /bin/sh

field_seperator="||"

output=b

while getopts :F:vo: arg

do

case $arg in

F ) field_seperator=$OPTARG;;

v ) ;;

o ) output=$OPTARG;;

: ) echo "$0: missing arg for -$OPTARG " >&2

exit;;

/?) echo "Invalid option -$OPTARG ignored." >&2

exit;;

esac

done

if [ $OPTIND -gt $# ]

then

# echo OPTIND=$OPTIND argc=$# >&2

echo "no program" >&2

exit

fi

program=${!#}

echo field_seperator=$field_seperator

cat > a.cpp <<+TemplateCFile

#include <vector>

#include <string.h>

#include <stdio.h>

const char field_seperator[]="||";

void split_row(char* line, std::vector<char*>& F, const char* fs)

{

char* col = line;

F.resize(0);

size_t fslen = strlen(fs);

if (fslen == 1) {

for (;;) {

F.push_back(col);

col = strchr(col, fs[0]);

if (col) {

col[0] = '/0';

col += 1;

} else

break;

}

else {

for (;;) {

F.push_back(col);

col = strstr(col, fs);

if (col) {

col[0] = '/0';

col += fslen;

} else

break;

}

int main(int argc, char* argv[])

{

size_t len1 = 0;

ssize_t len2;

char* line = NULL;

std::vector<char*> F;

while ((len2 = getline(&line, &len1, stdin)) != -1)

{

split_row(line, F, field_seperator);

int NF = F.size();

//--- begin user program

+TemplateCFile

echo $program >> a.cpp

cat >> a.cpp <<+TemplateCFile

//--- end user program

; // avoid user program missing ;

printf("/n");

}

if (line) free(line);

if (ferror(stdin)) {

perror("ferror(stdin)");

return 1;

}

return 0;

}

+TemplateCFile

sed -i 's//(field_seperator/[/]=/).*";//1"'$field_seperator'";/g' a.cpp

gcc -O2 a.cpp -lstdc++ -o $output

exit $?

可以象awk一样写程序：

# 相当于 awk -F,  '{printf("%s/t%s/n", $1, $5)}'  
# 使用 ',' 做列分隔符，输出第 1 和第 5 个字段，生成二进制可执行程序 myprog  
./gencode.sh -F , -o myprog 'printf("%s/t%s/n", F[0], F[4])'

1

2

3

# 相当于 awk -F, '{printf("%s/t%s/n", $1, $5)}'

# 使用 ',' 做列分隔符，输出第 1 和第 5 个字段，生成二进制可执行程序 myprog

./gencode.sh -F , -o myprog 'printf("%s/t%s/n", F[0], F[4])'

# 相当于 awk -F,  '{printf(&quot;%s/t%s/n&quot;, $1, $5)}'
# 使用 ',' 做列分隔符，输出第 1 和第 5 个字段，生成二进制可执行程序 myprog
./gencode.sh -F , -o myprog 'printf(&quot;%s/t%s/n&quot;, F[0], F[4])'

1

2

3

# 相当于 awk -F, '{printf("%s/t%s/n", $1, $5)}'

# 使用 ',' 做列分隔符，输出第 1 和第 5 个字段，生成二进制可执行程序 myprog

./gencode.sh -F , -o myprog 'printf("%s/t%s/n", F[0], F[4])'

我当初写这个生成器的原因是发现非常简单的 awk 程序也比 C 慢 40 倍，以为这是本质上的性能差距，后来才发现不是。

对这个简单的程序，使用awk更方便更安全，也不比C慢，但是一旦碰到其它类似问题而 awk 解决不了，这种模式就可以派上用场了。

LC_ALL=en_US.UTF-8 让 awk 慢了 40 倍！

作者: rockeet 发表日期: 2010年02月05日分类: shell, 杂谈评论: 0 条阅读次数: 2,369 次

　　无意中发现，在一台服务器上，非常简单的awk程序，比C的等价物要慢40倍，感觉有点不太正常，还以为的确是awk太慢。不得其解，到另一台服务上试了一下，相同的 awk 程序，相同的测试数据，这台服务器的速度与C相当，也就是说，同样是awk，两台机器速度差了 40倍，而两台机器配置基本相当。非常困惑，找了两小时的原因，终于发现gawk手册里面有一段话：

For other single-character record separators, using ‘LC_ALL=C’will give you much better performance when reading records. Otherwise,gawk has to make
several function calls, per inputcharacter to find the record terminator.

再看两台机器的 locale，结果发现，慢的机器上：

[root@slow-server]# locale
LANG=en_US.UTF-8
LC_XXXX=en_US.UTF-8

…
LC_ALL=en_US.UTF-8

快的机器上：

[root@fast-server]# locale
LANG=en_US
LC_XXXX=en_US

…
LC_ALL= <空>

马上试验，将slow-server的locale改掉：

export LC_ALL=C

速度马上快了40倍，与fast-server相当。

这应该是awk实现上的一个缺陷，即便是对utf8，也不应该慢这么多，如果缓冲合适，最多慢２～３倍就可以了，为什么非要gawk has to make several function calls,
per inputcharacter ？

count, sum, avg by range in log(n) time

作者: rockeet 发表日期: 2010年02月05日分类: 算法评论: 0 条阅读次数: 1,964 次

考虑一下这样一个查询：

select count(*), sum(tax), avg(weight)

from pepole

where id >= ${minid} && id < ${maxid};

怎样才能实现更小的时间复杂度？

一般情况下，最简单的方法就是遍历这个区间。但是这需要O(logn +m)的时间复杂度，其中m是区间长度，n是总记录数。

实际上，可以略增一点存储代价，对该查询实现O(logn)的时间复杂度。我以前写过一篇文章
，可以对count(*)实现logn复杂度:

count(*, minid, maxid) = rank(maxid) – rank(minid)

其中，rank(id) 表示该记录在整个表中的序号（排序名词）。这很容易理解。

如果要计算sum(x)或avg(x)，需要扩张一下，在每个结点中存储一个隐藏值，用来表示该以结点为根的子树的sum(x)值，那么，插入/删除/修改的代价也是O(logn)，计算sum(x),avg(x)的代价也是O(logn)。

sum(x, minid, maxid) = node(maxid).hidesumx – node(minid).hidesumx

avg(x, minid, maxid) = sum(x)/count(*, minid, maxid)

BekeleyDB中，可以实现 count(*) 的log(n)时间复杂度，因为它提供了类似rank()函数的功能，使用btree表，建表时提供DB_RECNUM标志。查询时，使用DBC::get，用DB_GET_RECNO flag：

 DB_ENV** dbenv;  
 DB* db;  
 /*.....*/  
 db_create(&db, dbenv, 0);  
 db->open(db, NULL, "tablename", "filename", DB_BTREE, DB_CREATE, 0);  
 db->set_flags(db, DB_RECNUM);  
   
 /*.....*/  
   
 int get_rank(DB* db, const void* key, size_t klen, db_recno_t* rank)  
 {  
     int  ret;  
     DBC* curp;  
     DBT  key = {0}, data = {0}, ignore = {0}, recno = {0};  
   
     key.data = key;  
     key.size = klen;  
     recno.data = rank;  
     recno.size = sizeof(*rank);  
   
     ret = curp->get(curp, &key, &data, DB_SET);  
     if (0 == ret) {  
         ret = curp->get(curp, &ignore, &recno, DB_GET_RECNO);  
     }  
     return ret;  
 }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

DB_ENV** dbenv;

DB* db;

/*.....*/

db_create(&db, dbenv, 0);

db->open(db, NULL, "tablename", "filename", DB_BTREE, DB_CREATE, 0);

db->set_flags(db, DB_RECNUM);

/*.....*/

int get_rank(DB* db, const void* key, size_t klen, db_recno_t* rank)

{

int ret;

DBC* curp;

DBT key = {0}, data = {0}, ignore = {0}, recno = {0};

key.data = key;

key.size = klen;

recno.data = rank;

recno.size = sizeof(*rank);

ret = curp->get(curp, &key, &data, DB_SET);

if (0 == ret) {

ret = curp->get(curp, &ignore, &recno, DB_GET_RECNO);

}

return ret;

}

MapReduce应该做更少的事情

作者: rockeet 发表日期: 2010年02月05日分类: MapReduce 评论: 0 条阅读次数: 3,765 次

MapReduce 做的事情太多了。相比 unix 思想，它更多的是提供了一种策略(Policy)，而非一种机制(Machanism)。

对于并行计算，如果我仅仅需要一种机制，暂且把这种机制叫做S，那么S只需要提供：继续阅读 →

字符串基数排序

作者: rockeet 发表日期: 2010年02月05日分类: C++, 算法评论: 2 条阅读次数: 2,494 次

　　对字符串使用基数排序，以前，我一直觉得：因为字符串的长度不一，无法使用基数排序。前两天因为有需要，忽然想通了！即便长短不一，也可以使用链式基数排序！

　　首先，将字符串长度当作最低有效位，因为基数排序是从最低有效位开始排的，就先用分配-收集算法对长度做一趟。对字符串中的具体某一位字符进行排序相比，算法是一样的，只是写法稍有不同。要将排序结果的lenRadix指针保存起来，后面要用。

　　接下来，从lenRadix中取字符串最长的那个sublist，对该sublist排序，然后将这一趟的结果first保存起来，连接到长度次短的那个sublist之后，然后对这两个链接起来的列表进行一趟分配-收集。如此，直到最高有效位。

　　所有的工作就做完了，根据此算法，对所有待排序字符串中的每个字符，均需要一次且仅一次访问！另外，还需要
O((radix+1)*max_str_len)的时间复杂度用于扫描链接表，(radix+1)是因为还有一个strlen链接表。所以，总的时间复
杂度是O(n+(radix+1)*max_str_len)，其中N是所有字符串的总字符数。

　　在排序过程中，可以插入一个codetab，来实现不同的排序准则（例如忽略大小写），如果提供了wchar_t codetab，就按 wchar_t 排序，如果wchar_t codetab 非 NULL，就按转换了的 wchar_t 排序。

　　如果对unicode排序，最好指定一个codetab，把radix变小，不然的话，时间复杂度就太大了！

　　经过测试，在大约20000~30000个字符串的情况下，比std::sort快5~7倍。数据规模再增大，至5,000,000个字符串时，比std::sort大概快1.8~2.5倍！

代码：

http://code.google.com/p/febird/source/browse/trunk/febird/src/febird/radix_sort.cpp

http://code.google.com/p/febird/source/browse/trunk/febird/src/febird/radix_sort.h

测试(bench mark)代码：

http://code.google.com/p/febird/source/browse/trunk/febird/codelite/RadixSort/main.cpp