算法 | Terark & Topling 创始人雷鹏

第一个博弈程序

作者: csdn-whinah 发表日期: 2011年07月17日分类: 算法评论: 0 条阅读次数: 2,235 次

甲乙两人在玩一个游戏：一堆小石子，共n个，每次每人可以从中取1个，或2个，或4个，甲先开始，最后取的那个人输（不管他去1个，还是2个，还是4个）。

但是呢，甲乙两个人都是智力超群的天才，他们总会使用对自己有利的策略。继续阅读 →

合并两个有序序列

作者: csdn-whinah 发表日期: 2011年07月16日分类: 算法评论: 0 条阅读次数: 2,416 次

经典写法

合并两个有序序列，太简单了吧？还有专门讨论的必要吗？

这是一个最简单的 Merge 版本：继续阅读 →

枚举变量扩展-2

作者: csdn-whinah 发表日期: 2011年07月03日分类: 算法, 自动机评论: 0 条阅读次数: 1,906 次

在前一篇文章里，可能有人注意到了：扩展结果中会出现同一变量的不同实例，如果我们要增加一个限制，扩展结果中每个变量都必须引用相同的实例，该怎么做？

枚举变量扩展

作者: csdn-whinah 发表日期: 2011年06月26日分类: 算法, 自动机评论: 0 条阅读次数: 2,162 次

在很多配置文件中，都会牵涉到变量扩展，一个变量会有多少种可能的扩展结果，这在静态分析中非常重要。这里给出一个算法，使用 perl 来表达(expand.pl)，变量引用使用统一的形式：${varname}。继续阅读 →

将递归转化成迭代的通用技术

作者: csdn-whinah 发表日期: 2011年05月14日分类: 算法评论: 0 条阅读次数: 2,403 次

从理论上讲，只要允许使用栈，所有的递归程序都可以转化成迭代。

但是并非所有递归都必须用栈，不用堆栈也可以转化成迭代的，大致有两类

尾递归：可以通过简单的变换，让递归作为最后一条语句，并且仅此一个递归调用。

// recursive
int fac1(int n) {
    if (n <= 0) return 1;
    return n * fac1(n-1);
}
// iterative
int fac2(int n) {
    int i = 1, y = 1;
    for (; i <= n; ++i) y *= i;
    return y;
}

1

2

3

4

5

6

7

8

9

10

11

// recursive

int fac1(int n) {

if (n <= 0) return 1;

return n * fac1(n-1);

}

// iterative

int fac2(int n) {

int i = 1, y = 1;

for (; i <= n; ++i) y *= i;

return y;

}

自顶向下->自底向上：对程序的结构有深刻理解后，自底向上计算，比如 fibnacci 数列的递归->迭代转化。

// recursive, top-down
int fib1(int n) {
    if (n <= 1) return 1;
    return fib1(n-1) + fib1(n-2);
}
// iterative, down-top
int fib2(int n) {
    int f0 = 1, f1 = 1, i;
    for (i = 2; i <= n; ++i) {
        int f2 = f1 + f0;
        f0 = f1; f1 = f2;
    }
    return f1;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

// recursive, top-down

int fib1(int n) {

if (n <= 1) return 1;

return fib1(n-1) + fib1(n-2);

}

// iterative, down-top

int fib2(int n) {

int f0 = 1, f1 = 1, i;

for (i = 2; i <= n; ++i) {

int f2 = f1 + f0;

f0 = f1; f1 = f2;

}

return f1;

}

对于非尾递归，就必须使用堆栈。可以简单生硬地使用堆栈进行转化：把函数调用和返回的地方翻译成汇编代码，然后把对硬件 stack 的 push, pop 操作转化成对私有 stack 的 push, pop ，这其中需要特别注意的是对返回地址的 push/pop，对应的硬件指令一般是 call/ret。使用私有 stack 有两个好处：

可以省去公用局部变量，也就是在任何一次递归调用中都完全相同的函数参数，再加上从这些参数计算出来的局部变量。
如果需要得到当前的递归深度，可以从私有 stack 直接拿到，而用递归一般需要一个单独的 depth 变量，然后每次递归调用加 1。

我们把私有 stack 元素称为 Frame，那么 Frame 中必须包含以下信息：

返回地址（对应于每个递归调用的下一条语句的地址）
对每次递归调用都不同的参数

通过实际操作，我发现，有一类递归的 Frame 可以省去返回地址！所以，这里又分为两种情况：

Frame 中可以省去返回地址的递归：仅有两个递归调用，并且其中有一个是尾递归。

// here used a function 'partition', but don't implement it
tempalte<class RandIter>
void QuickSort1(RandIter beg, RandIter end) {
    if (end - beg <= 1) return;
    RandIter pos = partition(beg, end);
    QuickSort1(beg, pos);
    QuickSort1(pos + 1, end);
}
tempalte<class RandIter>
void QuickSort2(RandIter beg, RandIter end) {
    std::stack<std::pair<RandIter> > stk;
    stk.push({beg, end});
    while (!stk.empty()) {
        std::pair<RandIter, RandIter> ii = stk.top(); stk.pop();
        if (ii.second - ii.first) > 1) {
            RandIter pos = partition(beg, end);
            stk.push({ii.first, pos});
            stk.push({pos + 1, ii.second});
        }
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

// here used a function 'partition', but don't implement it

tempalte<class RandIter>

void QuickSort1(RandIter beg, RandIter end) {

if (end - beg <= 1) return;

RandIter pos = partition(beg, end);

QuickSort1(beg, pos);

QuickSort1(pos + 1, end);

}

tempalte<class RandIter>

void QuickSort2(RandIter beg, RandIter end) {

std::stack<std::pair<RandIter> > stk;

stk.push({beg, end});

while (!stk.empty()) {

std::pair<RandIter, RandIter> ii = stk.top(); stk.pop();

if (ii.second - ii.first) > 1) {

RandIter pos = partition(beg, end);

stk.push({ii.first, pos});

stk.push({pos + 1, ii.second});

}

Frame 中必须包含返回地址的递归，这个比较复杂，所以我写了个完整的示例：

以MergeSort为例，因为 MergeSort 是个后序过程，两个递归调用中没有任何一个是尾递归
MergeSort3 使用了 GCC 的 Label As Value 特性，只能在 GCC 兼容的编译器中使用
单纯对于这个实例来说，返回地址其实只有两种，返回地址为 0 的情况可以通过判断私有栈(varname=stk)是否为空，stk为空时等效于 retaddr == 0。如果要精益求精，一般情况下指针的最低位总是0，可以把这个标志保存在指针的最低位，当然，如此的话就无法对 sizeof(T)==1 的对象如 char 进行排序了。

#include <stdio.h>
#include <string.h>
# if 1
#include <stack>
#include <vector>
template<class T>
class MyStack : public std::stack<T, std::vector<T> >
{
};
#else
template<class T>
class MyStack {
	union {
		char*  a;
	   	T* p;
   	};
	int n, t;
public:
	explicit MyStack(int n=128) {
		this->n = n;
		this->t = 0;
		a = new char[n*sizeof(T)];
	}
	~MyStack() {
		while (t > 0)
			pop();
		delete[] a;
	}
	void swap(MyStack<T>& y) {
		char* q = y.a; y.a = a; a = q;
		int z;
		z = y.n; y.n = n; n = z;
		z = y.t; y.t = t; t = z;
	}
	T& top() const { 
		return p[t-1];
   	}
	void pop() {
		--t;
		p[t].~T();
	}
	void push(const T& x) {
		x.print(); // debug
		p[t] = x;
		++t;
	}
	int size() const { return t; }
	bool empty() const { return 0 == t; }
	bool full() const { return n == t; }
};
#endif
template<class T>
struct Frame {
	static T* base;
	T *beg, *tmp;
	int len;
	int retaddr;
	Frame(T* beg, T* tmp, int len, int retaddr)
		: beg(beg), tmp(tmp), len(len), retaddr(retaddr)
	{}
	void print() const { // for debug
		printf("%4d %4d %d/n", int(beg-base), len, retaddr);
	}
};
template<class T> T* Frame<T>::base;
#define TOP(field) stk.top().field
template<class T>
bool issorted(const T* a, int n)
{
	for (int i = 1; i < n; ++i) {
		if (a[i-1] > a[i]) return false;
	}
	return true;
}
template<class T>
void mymerge(const T* a, int la, const T* b, int lb, T* c) {
	int i = 0, j = 0, k = 0;
	for (; i < la && j < lb; ++k) {
		if (b[j] < a[i])
			c[k] = b[j], ++j;
		else
			c[k] = a[i], ++i;
	}
	for (; i < la; ++i, ++k) c[k] = a[i];
	for (; j < lb; ++j, ++k) c[k] = b[j];
}
template<class T>
void MergeSort1(T* beg, T* tmp, int len) {
	if (len > 1) {
		int mid = len / 2;
		MergeSort1(beg    , tmp    , mid);
		MergeSort1(beg+mid, tmp+mid, len-mid);
		mymerge(tmp, mid, tmp+mid, len-mid, beg);
		memcpy(tmp, beg, sizeof(T)*len);
	}
	else
		*tmp = *beg;
}
template<class T>
void MergeSort2(T* beg0, T* tmp0, int len0) {
	int mid;
	int cnt = 0;
	Frame<T>::base = beg0;
	MyStack<Frame<T> > stk;
	stk.push(Frame<T>(beg0, tmp0, len0, 0));
	while (true) {
		++cnt;
		if (TOP(len) > 1) {
			mid = TOP(len) / 2;
			stk.push(Frame<T>(TOP(beg), TOP(tmp), mid, 1));
			continue;
L1:
			mid = TOP(len) / 2;
			stk.push(Frame<T>(TOP(beg)+mid, TOP(tmp)+mid, TOP(len)-mid, 2));
			continue;
L2:
			mid = TOP(len) / 2;
			mymerge(TOP(tmp), mid, TOP(tmp)+mid, TOP(len)-mid, TOP(beg));
			memcpy(TOP(tmp), TOP(beg), sizeof(T)*TOP(len));
		} else
			*TOP(tmp) = *TOP(beg); 
		int retaddr0 = TOP(retaddr);
		stk.pop();
		switch (retaddr0) {
		case 0: return;
		case 1: goto L1;
		case 2: goto L2;
		}
	}
}
// This Implementation Use GCC's goto saved label value
// Very similiar with recursive version
template<class T>
void MergeSort3(T* beg0, T* tmp0, int len0) {
MyEntry:
	int mid;
	int retaddr;
	Frame<T>::base = beg0;
	MyStack<Frame<T> > stk;
	stk.push(Frame<T>(beg0, tmp0, len0, 0));
#define Cat1(a,b) a##b
#define Cat(a,b) Cat1(a,b)
#define HereLabel() Cat(HereLable_, __LINE__)
#define RecursiveCall(beg, tmp, len) /
	stk.push(Frame<T>(beg, tmp, len, (char*)&&HereLabel() - (char*)&&MyEntry)); /
	continue; /
	HereLabel():;
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// retaddr == 0 是最外层的递归调用，
// 只要到达这一层时 retaddr 才为 0,
// 此时就可以返回了
#define MyReturn /
	retaddr = TOP(retaddr); /
	stk.pop(); /
	if (0 == retaddr) { /
		return; /
   	} /
	goto *((char*)&&MyEntry + retaddr);
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	while (true) {
		if (TOP(len) > 1) {
			mid = TOP(len) / 2;
			RecursiveCall(TOP(beg), TOP(tmp), mid);
			mid = TOP(len) / 2;
			RecursiveCall(TOP(beg)+mid, TOP(tmp)+mid, TOP(len)-mid);
			mid = TOP(len) / 2;
			mymerge(TOP(tmp), mid, TOP(tmp)+mid, TOP(len)-mid, TOP(beg));
			memcpy(TOP(tmp), TOP(beg), sizeof(T)*TOP(len));
		} else
			*TOP(tmp) = *TOP(beg); 
		MyReturn;
	}
}
template<class T>
void MergeSortDriver(T* beg, int len, void (*mf)(T* beg_, T* tmp_, int len_))
{
	T* tmp = new T[len];
	(*mf)(beg, tmp, len);
	delete[] tmp;
}
#define test(a,n,mf) /
	memcpy(a, b, sizeof(a[0])*n); /
	MergeSortDriver(a, n, &mf); /
	printf("sort by %s:", #mf); /
	for (i = 0; i < n; ++i) printf("% ld", a[i]); /
	printf("/n");
int main(int argc, char* argv[])
{
	int n = argc - 1;
	int i;
	long* a = new long[n];
	long* b = new long[n];
	for (i = 0; i < n; ++i)
		b[i] = strtol(argv[i+1], NULL, 10);
	test(a, n, MergeSort1);
	test(a, n, MergeSort2);
	test(a, n, MergeSort3);
	printf("All Successed/n");
	delete[] a;
	delete[] b;
	return 0;
}

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

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

#include <stdio.h>

#include <string.h>

# if 1

#include <stack>

#include <vector>

template<class T>

class MyStack : public std::stack<T, std::vector<T> >

{

};

#else

template<class T>

class MyStack {

union {

char* a;

T* p;

};

int n, t;

public:

explicit MyStack(int n=128) {

this->n = n;

this->t = 0;

a = new char[n*sizeof(T)];

}

~MyStack() {

while (t > 0)

pop();

delete[] a;

}

void swap(MyStack<T>& y) {

char* q = y.a; y.a = a; a = q;

int z;

z = y.n; y.n = n; n = z;

z = y.t; y.t = t; t = z;

}

T& top() const {

return p[t-1];

}

void pop() {

--t;

p[t].~T();

}

void push(const T& x) {

x.print(); // debug

p[t] = x;

++t;

}

int size() const { return t; }

bool empty() const { return 0 == t; }

bool full() const { return n == t; }

};

#endif

template<class T>

struct Frame {

static T* base;

T *beg, *tmp;

int len;

int retaddr;

Frame(T* beg, T* tmp, int len, int retaddr)

: beg(beg), tmp(tmp), len(len), retaddr(retaddr)

{}

void print() const { // for debug

printf("%4d %4d %d/n", int(beg-base), len, retaddr);

}

};

template<class T> T* Frame<T>::base;

#define TOP(field) stk.top().field

template<class T>

bool issorted(const T* a, int n)

{

for (int i = 1; i < n; ++i) {

if (a[i-1] > a[i]) return false;

}

return true;

}

template<class T>

void mymerge(const T* a, int la, const T* b, int lb, T* c) {

int i = 0, j = 0, k = 0;

for (; i < la && j < lb; ++k) {

if (b[j] < a[i])

c[k] = b[j], ++j;

else

c[k] = a[i], ++i;

}

for (; i < la; ++i, ++k) c[k] = a[i];

for (; j < lb; ++j, ++k) c[k] = b[j];

}

template<class T>

void MergeSort1(T* beg, T* tmp, int len) {

if (len > 1) {

int mid = len / 2;

MergeSort1(beg , tmp , mid);

MergeSort1(beg+mid, tmp+mid, len-mid);

mymerge(tmp, mid, tmp+mid, len-mid, beg);

memcpy(tmp, beg, sizeof(T)*len);

}

else

*tmp = *beg;

}

template<class T>

void MergeSort2(T* beg0, T* tmp0, int len0) {

int mid;

int cnt = 0;

Frame<T>::base = beg0;

MyStack<Frame<T> > stk;

stk.push(Frame<T>(beg0, tmp0, len0, 0));

while (true) {

++cnt;

if (TOP(len) > 1) {

mid = TOP(len) / 2;

stk.push(Frame<T>(TOP(beg), TOP(tmp), mid, 1));

continue;

L1:

mid = TOP(len) / 2;

stk.push(Frame<T>(TOP(beg)+mid, TOP(tmp)+mid, TOP(len)-mid, 2));

continue;

L2:

mid = TOP(len) / 2;

mymerge(TOP(tmp), mid, TOP(tmp)+mid, TOP(len)-mid, TOP(beg));

memcpy(TOP(tmp), TOP(beg), sizeof(T)*TOP(len));

} else

*TOP(tmp) = *TOP(beg);

int retaddr0 = TOP(retaddr);

stk.pop();

switch (retaddr0) {

case 0: return;

case 1: goto L1;

case 2: goto L2;

}

// This Implementation Use GCC's goto saved label value

// Very similiar with recursive version

template<class T>

void MergeSort3(T* beg0, T* tmp0, int len0) {

MyEntry:

int mid;

int retaddr;

Frame<T>::base = beg0;

MyStack<Frame<T> > stk;

stk.push(Frame<T>(beg0, tmp0, len0, 0));

#define Cat1(a,b) a##b

#define Cat(a,b) Cat1(a,b)

#define HereLabel() Cat(HereLable_, __LINE__)

#define RecursiveCall(beg, tmp, len) /

stk.push(Frame<T>(beg, tmp, len, (char*)&&HereLabel() - (char*)&&MyEntry)); /

continue; /

HereLabel():;

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

// retaddr == 0 是最外层的递归调用，

// 只要到达这一层时 retaddr 才为 0,

// 此时就可以返回了

#define MyReturn /

retaddr = TOP(retaddr); /

stk.pop(); /

if (0 == retaddr) { /

return; /

} /

goto *((char*)&&MyEntry + retaddr);

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

while (true) {

if (TOP(len) > 1) {

mid = TOP(len) / 2;

RecursiveCall(TOP(beg), TOP(tmp), mid);

mid = TOP(len) / 2;

RecursiveCall(TOP(beg)+mid, TOP(tmp)+mid, TOP(len)-mid);

mid = TOP(len) / 2;

mymerge(TOP(tmp), mid, TOP(tmp)+mid, TOP(len)-mid, TOP(beg));

memcpy(TOP(tmp), TOP(beg), sizeof(T)*TOP(len));

} else

*TOP(tmp) = *TOP(beg);

MyReturn;

}

template<class T>

void MergeSortDriver(T* beg, int len, void (*mf)(T* beg_, T* tmp_, int len_))

{

T* tmp = new T[len];

(*mf)(beg, tmp, len);

delete[] tmp;

}

#define test(a,n,mf) /

memcpy(a, b, sizeof(a[0])*n); /

MergeSortDriver(a, n, &mf); /

printf("sort by %s:", #mf); /

for (i = 0; i < n; ++i) printf("% ld", a[i]); /

printf("/n");

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

{

int n = argc - 1;

int i;

long* a = new long[n];

long* b = new long[n];

for (i = 0; i < n; ++i)

b[i] = strtol(argv[i+1], NULL, 10);

test(a, n, MergeSort1);

test(a, n, MergeSort2);

test(a, n, MergeSort3);

printf("All Successed/n");

delete[] a;

delete[] b;

return 0;

}

服务器超时管理问题

作者: rockeet 发表日期: 2010年08月19日分类: 算法评论: 0 条阅读次数: 2,296 次

有一个最多能处理N个客户连接的服务器，活跃的连接总是少数；
为了能够处理更多的连接，需要对每个连接都增加一个超时机制，当总连接数达到N时，某个连接一旦超时，有新的连接请求时，就把超时的关掉，并处理新连接；继续阅读 →

对数复杂度的聚集算法

作者: rockeet 发表日期: 2010年07月12日分类: 算法评论: 0 条阅读次数: 2,306 次

SQL 有5个标准聚集函数：SUM, AVG, MIN, MAX, COUNT, 一般情况下，这几个函数的时间复杂度至少都是O(n), n是结果集的尺寸。然而，给定表：

继续阅读 →

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

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

考虑一下这样一个查询：

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;

}

字符串基数排序

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

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

　　首先，将字符串长度当作最低有效位，因为基数排序是从最低有效位开始排的，就先用分配-收集算法对长度做一趟。对字符串中的具体某一位字符进行排序相比，算法是一样的，只是写法稍有不同。要将排序结果的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

Threaded Red-Black Tree 线索红黑树

作者: rockeet 发表日期: 2009年05月26日分类: C++, 算法评论: 0 条阅读次数: 2,193 次

项目地址：http://code.google.com/p/febird

使用 libavl 中的 trb ，经过修改，实现了一个更高效更友好易用的版本，并且也支持范围查询，提供完备的std::map/set接口。

对基本类型的key，实现高效search
支持 lower_bound/upper_bound/equal_range
结点采用压缩方式，将colorbit(1bit)和tagbit(2bit)压缩到指针中
1. 从而每个结点的overhead是2ptr(32位环境下8byte，64位环境下16bits)
2. stl::map/stl::set 的节点overhead 一般是 4ptr
遍历tree的速度比stl::map/set快一倍
1. 线索树的线索(thread)可以直接访问next/prev，而不需要回溯到祖先结点再访问其最左/右叶子
2. 通过线索(thread)直接访问到next/prev的概率大约有50%
key的访问使用fieldoffset，C标准中有 offsetof(T,f) 宏来计算字段偏移
因为使用C模拟template，从而没有C++的代码膨胀问题
C接口需要手工打造vtable
vtable指针通过参数传递，而不是将它作为trb_tree的一部分，更节约内存
1. 也许仅仅一个vtable指针用不了多少内存
2. 但是当有若干个【在我的应用中，大约2M个】trb_tree时，节省的内存相当可观
使用C实现核心功能，同时提供更易用的C++接口（trbset/trbmap/trbtab）
1. 类似stl中的相应东西
2. trbset相当于stl::set
3. trbmap相当于stl::map
4. trbtab提供更多的控制
C++接口只是一个语法糖wrapper，将调用转发到C，但是使用C++可以避免几乎一切误用
1. C++将vtable作为模板的static成员，非常合理，非常恰到好处

以前我写过两篇文章：

在 C 语言中实现模板函数的方法

在 C 语言中实现模板函数的方法（续）

对基本类型的key，实现高效search，其核心思想就来源于这两篇文章，但是有许多精化。其间使用了更之前的一些东西：

基本类型enum
类型迭代（使用preprocessor）

基本类型enum，使用enum的目的在于：使用这个enum，查找到相应的处理函数。

enum field_type_t {
	tev_char,
	tev_byte,
	tev_int16,
	tev_uint16,
	tev_int32,
	tev_uint32,
	tev_int64,
	tev_uint64,
	tev_float,
	tev_double,
	tev_int,
	tev_uint,
	tev_long,
	tev_ulong,
	tev_ptr,
	tev_blob,  ///< blob
	tev_cstr,
	tev_std_string, ///< for c++ std::string, only used in c++
	tev_std_wstring, ///< for c++ std::wstring, only used in c++
	tev_app    ///< application defined type
#define	tev_type_count__  tev_int
};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

enum field_type_t {

tev_char,

tev_byte,

tev_int16,

tev_uint16,

tev_int32,

tev_uint32,

tev_int64,

tev_uint64,

tev_float,

tev_double,

tev_int,

tev_uint,

tev_long,

tev_ulong,

tev_ptr,

tev_blob, ///< blob

tev_cstr,

tev_std_string, ///< for c++ std::string, only used in c++

tev_std_wstring, ///< for c++ std::wstring, only used in c++

tev_app ///< application defined type

#define tev_type_count__ tev_int

};

类型迭代：p_field_type_loop.h

// field type loop without judge VALUE_SIZE
// input macro:
//	 FIELD_TYPE_FILE

#  define FIELD_TYPE_TYPE signed char
#  define FIELD_TYPE_PROMOTED int
#  define FIELD_TYPE_NAME tev_char
#  include FIELD_TYPE_FILE
#  undef FIELD_TYPE_PROMOTED

#  define FIELD_TYPE_TYPE unsigned char
#  define FIELD_TYPE_PROMOTED unsigned
#  define FIELD_TYPE_NAME tev_byte
#  include FIELD_TYPE_FILE
#  undef FIELD_TYPE_PROMOTED

// and so on ....
// more types

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

// field type loop without judge VALUE_SIZE

// input macro:

// FIELD_TYPE_FILE

# define FIELD_TYPE_TYPE signed char

# define FIELD_TYPE_PROMOTED int

# define FIELD_TYPE_NAME tev_char

# include FIELD_TYPE_FILE

# undef FIELD_TYPE_PROMOTED

# define FIELD_TYPE_TYPE unsigned char

# define FIELD_TYPE_PROMOTED unsigned

# define FIELD_TYPE_NAME tev_byte

# include FIELD_TYPE_FILE

# undef FIELD_TYPE_PROMOTED

// and so on ....

// more types

在包含该文件之前，需要定义 FIELD_TYPE_FILE ，从而p_field_type_loop.h可以作为一个通用的代码生成器。在FIELD_TYPE_FILE中，实现具体的代码，在需要参数化类型的地方，使用FIELD_TYPE_TYPE来代替。FIELD_TYPE_PROMOTED用来提升相应的FIELD_TYPE_TYPE，例如 signed char 被提升到 int，float 被提升到double，这一点，在使用C的vararg时是绝对必要的。

另外，在包含该文件之前，还要将FIELD_TYPE_FILE中实现的函数名定义成宏，如：

#define trb_compare_kd  CAT_TOKEN2(trb_compare_, FIELD_TYPE_NAME)
#define trb_find_xx CAT_TOKEN2(trb_find_, FIELD_TYPE_NAME)
#define trb_lower_bound_xx CAT_TOKEN2(trb_lower_bound_, FIELD_TYPE_NAME)
#define trb_upper_bound_xx CAT_TOKEN2(trb_upper_bound_, FIELD_TYPE_NAME)
#define trb_equal_range_xx CAT_TOKEN2(trb_equal_range_, FIELD_TYPE_NAME)
#define trb_find_path_xx  CAT_TOKEN2(trb_find_path_, FIELD_TYPE_NAME)

#define FIELD_TYPE_FILE "trb_fun_field_type.h"
#include "p_field_type_loop.h"
#undef FIELD_TYPE_FILE

1

2

3

4

5

6

7

8

9

10

#define trb_compare_kd CAT_TOKEN2(trb_compare_, FIELD_TYPE_NAME)

#define trb_find_xx CAT_TOKEN2(trb_find_, FIELD_TYPE_NAME)

#define trb_lower_bound_xx CAT_TOKEN2(trb_lower_bound_, FIELD_TYPE_NAME)

#define trb_upper_bound_xx CAT_TOKEN2(trb_upper_bound_, FIELD_TYPE_NAME)

#define trb_equal_range_xx CAT_TOKEN2(trb_equal_range_, FIELD_TYPE_NAME)

#define trb_find_path_xx CAT_TOKEN2(trb_find_path_, FIELD_TYPE_NAME)

#define FIELD_TYPE_FILE "trb_fun_field_type.h"

#include "p_field_type_loop.h"

#undef FIELD_TYPE_FILE

以trb_find_xx为例，当trb_find_xx被展开后，变成trb_find_tev_double等等。

为什么要搞这么多呢？因为在这些函数中，对key值的大小比较实际上是个trivial操作，而一般传统的方法是传递一个compare函数指针，通过该指针调用compare函数，来实现灵活性（对任意类型的key）。

但是，通过函数指针调用一个非常trivial的操作，有很多不必要的性能损失（经过测试，对int的key，trb_find_xx会慢约20%~80%，服务器GCC+至强2.29G中慢20%，台式机VC+奔腾2.49G中慢80%）。

使用这种编程范式，可以在不必造成冗余代码的情况下，大幅提升性能。

全部的代码在这里

第一个博弈程序

合并两个有序序列

经典写法

枚举变量扩展-2

枚举变量扩展

将递归转化成迭代的通用技术

服务器超时管理问题

对数复杂度的聚集算法

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

字符串基数排序

Threaded Red-Black Tree 线索红黑树

近期文章

近期评论

文章归档

分类目录

功能