Archive: Posts Tagged ‘adsense’

记下最近二三事

5 comments November 16th, 2010 xiaoe

从后往前说吧。
刚刚发现.subversion/config中~是不能被解析成/home/xxx/的，原来配置svn好使总是有警告说xxx文件找不到，没在意；现在才知道确实是找不到啊，原来能连接是因为我的private key都放在.ssh/下，ssh自己会搜索这个路径下的key，所以说呢，我又犯了一次2。
也是刚才，发现我的adsense中Page impressions总共才4000多，收入$2.5…曾几何时我还梦想着收回成本呢。
再之前的这两天，断断续续的改程序，跑程序，体会就是无论多么小的系统，设计都是很重要的；
我的程序功能很简单，弄一堆候选词，抓网页，看这些词是不是在网络词典里出现；
最开始设计成了碎文件的存储，总是担心要是文件系统的node用光了怎么办，没实际算过。。。所以又改成数据库方式存储，这么干缺点是太慢了，数据规模变大了，数据库存取很慢；最后又改成了碎文件存储。。。而且我还要寄希望于这些个“词典”不要“屏蔽”我，毕竟慢慢的用代理偷偷摸摸抓也是抓，明目张胆赤裸裸的疯狂抓也是抓。
另外一点，我的感悟就是代码与数据的分离也是很重要的；
版本控制也是重要的，一个好的习惯是：checkout -> commit…checkout -> commit. 而我的做法是copy -> edit…copy -> edit。
最往前几天，帮助锋哥写了些hash函数，测试这些函数的优劣。

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

u_int elfHash(const char *str) {
	u_int code = 0;
	u_int ans = 0;
 
	while(*str) {
		code = (code<<4) + (*str++);
		if((ans = (code & 0xf0000000)) != 0) {
			code ^= (ans >> 24);
			code ^= ans;
		}
	}
	return code & 0x7fffffff;
}
u_int nrHash(const char *str) {
	u_int code = 0;
	while(*str) {
		code *= 16777619;
		code ^= (u_int) *(unsigned char*)str;
		++str;
	}
	return code;
}
u_int stlHash(const char *str) {
	/*
	inline size_t __stl_hash_string(const char* __s)
	{
	  unsigned long __h = 0; 
	  for ( ; *__s; ++__s)
		__h = 5*__h + *__s;
 
	  return size_t(__h);
	}
	*/
	return __stl_hash_string(str);
}

实际上这些hash函数都差不多，其思想也是相似的；我的实践经验发现：模数底M对结果影响很大，M取得很大与很小hash效果都不好；最后比较好的结果是M取8-10w之间的素数。我猜测sgi的hash_set有可能也是这么干的。
再往前几天，hbx同学某天晚上说我怎么变高了，我倒是希望变高，不过这是不可能的，我都什么岁数的人了，要是还能长，那么500w也离我不远了。
再之前几天，我实在想不起来具体都干什么了，就记着写程序了。有一天随便看了看一本什么数据存储查询的书，书上介绍了huffman编码压缩，算术编码压缩方法；就想起来曾经在acmClub时候，最开始就是学的这个，呵呵，真怀念啊。然后，花了点时间写了个压缩解压缩的程序，虽然压缩比很差，但是思路还是很清晰的；btw: wordpress添加downloads真麻烦，而且中文编码也有问题。
回想这些天，除了写写代码，配置这个那个，还真没干什么了。也许，所谓的什么个性化推荐才是我们应该走的道路，毕竟我们还是所谓的研究生。

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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <queue>
#include <cassert>
#include <cstring>
 
using namespace std;
typedef unsigned int u_int;
struct Node {
	char key;
	u_int freq;
	Node *self;
	Node *left, *right;
	Node() { left = right = 0; key = 0; self = this;}
	bool operator<(const Node & _n) const {
		return freq > _n.freq ? true : freq < _n.freq ? false : key < _n.key ? true : false;
	}
};
const u_int BLOCK_SIZE = 1024;
class Huffman {
	public:
		Node *buildTree() {
			priority_queue<Node> Q;
			u_int num = 0;
			for(u_int i = 0; i < 256; ++i) {
				if(counter[i] == 0) continue;
				Node *ans = new Node();
				ans->key = i, ans->freq = counter[i], ans->self = ans;
				//fprintf(stderr, "%d - %d\n", ans->key, ans->freq);
				Q.push(*ans);
				++num;
			}
			for(int i = 1; i < num; ++i) {
				assert(!Q.empty());
				Node first = Q.top(); Q.pop();
				assert(!Q.empty());
				Node second = Q.top(); Q.pop();
				//fprintf(stderr, "(%d - %d)\n", first.freq, second.freq);
				Node *ans = new Node();
				ans->left = first.self, ans->right = second.self;
				ans->freq = first.freq + second.freq;
				Q.push(*ans);
			}
			assert(!Q.empty());
			return Q.top().self;
		}
		void trace(char *_code, u_int depth, const Node * _node) {
			if(_node->left == NULL && _node->right == NULL) {
				fprintf(stderr, "key: %d\tdepth: %d\tcode: ", _node->key, depth);
				for(int i = 0; i < depth; i++)
					fprintf(stderr, "%d", *(_code - depth + i));
				fprintf(stderr, "\n");
				return;
			}
			if(_node->left) {
				//fprintf(stderr, "(");
				*_code = 0;
				trace(_code+1, depth + 1, _node->left);
				*_code = 2;
			}
			if(_node->right) {
				*_code = 1;
				trace(_code+1, depth+1, _node->right);
				*_code = 2;
				//fprintf(stderr, ")");
			}
		}
		void readFile(const char *file) {
			FILE *fin = fopen(file, "rb");
			if(fin== NULL) {
				fprintf(stderr, "fopen fail.\n");
				exit(-1);
			}
			char str[BLOCK_SIZE];
			u_int n;
			memset(counter, 0, sizeof(counter));
			while((n = fread(str, sizeof(char), BLOCK_SIZE, fin)) > 0) 
				for(u_int i = 0; i < n; ++i) counter[(int)str[i]]++;
			//for(int i = 0; i < 256; ++i) fprintf(stderr, "counter[%d]: %d\n", i, counter[i]);
			fclose(fin);
		}
		void compress(const char *file, const char *outFile) {
			readFile(file);
			Node *root = buildTree();
			char _code[256];
			//trace(_code, 0, root);
			encode(_code, 0, root);
			writeFile(file, outFile);
		}
		void i2ch(u_int n, char *str) {
 
			for(int i = 0; i < 4; ++i) {
				*(str+i) = 0xff & (n >> ((3-i)*8));
			}
		}
		void writeFile(const char *file, const char *com) {
			FILE *fin = fopen(file, "rb");
			FILE *fout = fopen(com, "wb");
			if(fin== NULL || fout == NULL) {
				fprintf(stderr, "fopen fail.\n");
				exit(-1);
			}
			u_int num = 0;
			for(int i = 0; i < 256; ++i) if(counter[i] > 0) num++;
			char ntr[8] = {0};
			i2ch(num, ntr);
			//fprintf(stderr, "num : %d-%d-%d-%d  - %u \n", ntr[0], ntr[1], ntr[2], ntr[3], num);
			if(fwrite(ntr, sizeof(char), 4, fout) < 4) {
					fprintf(stderr, "fwrite 4 error.\n");
					exit(-1);
				}
 
			for(int i = 0; i < 256; ++i) {
				if(counter[i] == 0) continue;
				char ttr[8] = {0};
				ttr[0] = i; 
				i2ch(counter[i], ttr+1);
				if(fwrite(ttr, sizeof(char), 5, fout) < 5) {
					fprintf(stderr, "fwrite 5 error.\n");
					exit(-1);
				}
			}
			char str[BLOCK_SIZE];
			char ctr[BLOCK_SIZE];
			memset(ctr, 0, sizeof(ctr));
			u_int n, ex = 0;
			int ix = 7;
			while((n = fread(str, sizeof(char), BLOCK_SIZE, fin)) > 0) {
				for(u_int i = 0; i < n; ++i) {
					for(int j = 0; j < mask[str[i]]; ++j) {
						if(code[str[i]][j] == 1)
						ctr[ex] = ctr[ex] | (1<<ix);
						ix--;
						if(ix < 0) ex++, ix = 7;
						if(ex == BLOCK_SIZE) {
							//写入文件
							if(fwrite(ctr, sizeof(char), ex, fout) < ex) {
								fprintf(stderr, "fwrite error.\n");
								exit(-1);
							}
							memset(ctr, 0, sizeof(ctr));
							ex = 0, ix = 7;
						}
 
					}
				}
			}
			//fprintf(stderr, "write in to compress ex %d\n", ex);
			if(fwrite(ctr, sizeof(char), ex, fout) < ex) {
				fprintf(stderr, "fwrite error.\n");
				exit(-1);
			}
			fclose(fin);
			fclose(fout);
		}
		void binaryPrint(char n) {
		 	for(int i = 7; i >= 0; --i)
				fprintf(stderr, "%d", ((1<<i) & (0x000000ff & n)) ? 1 : 0);
		}
		//_code : 0, _mask : 0
		void encode(char *_code, char _mask, const Node *node) {
			if(node->left == NULL && node->right == NULL) {
				for(int i = 0; i < _mask; ++i) {
					code[node->key][i] = *(_code-_mask+i);
				}
				mask[node->key] = _mask;
				return ;
			}
			if(node->left) {
				*_code = 0;
				encode(_code+1, _mask+1, node->left);
			}
			if(node->right) {
				*_code = 1;
				encode(_code+1, _mask+1, node->right);
			}
		}
 
		void decompress(const char *file, const char *outFile) {
			FILE *fin = fopen(file, "rb");
			FILE *fout = fopen(outFile, "wb");
			if(fin == NULL || fout == NULL) {
				fprintf(stderr, "fopen fail.\n");
				exit(-1);
			}
			char str[BLOCK_SIZE] = {0};
			memset(counter, 0, sizeof(counter));
			if(fread(str, sizeof(char), 4, fin) < 4) {
				fprintf(stderr, "fread first 4 char fail.\n");
				exit(-1);
			}
			u_int n = ch2i(str);
			//fprintf(stderr, "n : %d-%d-%d-%d  - %u \n", str[0], str[1], str[2], str[3], n);
			for(u_int i = 0; i < n; ++i) {
				if(fread(str, sizeof(char), 5, fin) < 5) {
					fprintf(stderr, "fread 5-group fail.\n");
					exit(-1);
				}
				counter[(int)str[0]] = ch2i(str+1);
			}
			Node *root = buildTree();
			Node *ans = root;
			char _code[256];
			//trace(_code, 0, ans);
			u_int ix = 0;
			char ctr[BLOCK_SIZE];
 
			while((n = fread(str, sizeof(char), BLOCK_SIZE, fin)) > 0) {
				for(u_int i = 0; i < n; ++i) {
					for(int j = 7; j >= 0; --j) {
						//fprintf(stderr, "%d",((1<<j) & (0x000000ff & str[i])) ? 1 : 0); 
						if(((1<<j) & (0x000000ff & str[i]))) {
							assert(ans->right != NULL);
							ans = ans->right;
						}
						else {
							assert(ans->left != NULL);
							ans = ans->left;
						}
						if(ans->left == NULL && ans->right == NULL) {
							//fprintf(stderr, "\n");
							ctr[ix++] = ans->key;
							if(ix == BLOCK_SIZE) {
								//写入文件
								fwrite(ctr, sizeof(char), ix, fout);		
								ix = 0;
							}
							ans = root;
						}
					}
				}
			}
			fwrite(ctr, sizeof(char), ix, fout);		
			fclose(fin);
			fclose(fout);
		}
		u_int ch2i(const char *str) {
			u_int res = 0;
			for(int i = 0; i < 4; ++i) res = (res<<8) | (0x000000ff & str[i]);
			return res;
		}
	private:
		char mask[256];
		char code[256][256];
		u_int counter[256];
};
int
main(int argc, char **argv) {
	Huffman huff;
	// huffman -c compress compressed
	// huffman -d decompress decompressed
	if(argc < 4) {
		fprintf(stderr, "usage: huffman -cd file.in file.out\n");
		exit(-1);
	}
	if(strcmp(argv[1], "-c") == 0) {
		huff.compress(argv[2], argv[3]);
	}
	else if(strcmp(argv[1], "-d") == 0) {
		huff.decompress(argv[2], argv[3]);
	}
	else {
		fprintf(stderr, "usage: option -c or -d.\n");
		exit(-1);
	}
 
	return 0;
}
journal, programming , , ,