CalvinMnakor
- 浏览: 52546 次
- 性别:
- 来自: 上海
-
最新评论
-
evagame：
自己看书的时候为这个问题困惑过，看了楼主的文章，获得了思路，谢 ...
《编程珠玑》 二分查找在大量数据中的使用(查找一个不在文件中的数据) -
CalvinMnakor：
...
《编程珠玑》第十一章 排序 -
CalvinMnakor：
配置老是容易出错！！
Tomcat6.0,eclipse,Oracle 11g配置连接池 -
CalvinMnakor：
？？？？？？？？
SICP 3.5节summary 和部分习题答案
文章列表
下面是我在一个大学bbs上看到的一个小问题，问题不难，可还是有许多要注意的地方，数据抽象这一块，函数抽象这一块，还是要多考虑一下，不然，写出的程序会相当冗杂繁琐，相当不优美。
问题陈述：
游戏公司 ...
今天 下午打开Google的chrome 发现扩展程序不见了，主页按钮也不见了 一时心慌，搜索Google，没了Google.cn 只有了http://www.google.com.hk，打开一看，还好，Google有了新家，没了Google真不知还怎么活下去，搜索一下，结果还好，这下心里平静多了。希望不会有太多改变。
《编程珠玑》第二章提到的问题C，查找一个单词的变位词，如果，直接全排列，然后再各个比对，那效率很低，书中使用了标签来表示同一类单词，而这一标签就是签名。签名的方式很多，不同签名，不同作用方式。由于变位词是指字母相同，但字母顺序不同的单词。故使用全字母签名。由此提出了“三段式”管道结构，三部分分别加签名，排序以及挤压合并。
第一部分，产生带有签名的词典：
void ExtendTheDictionary()
{
//extend the dictionary in the dictionary.txt
char word[WORDMAX],sig[WORD ...
《编程珠玑》第二章提到的问题A：
给定一个包含32位整数的顺序文件，它至多包含40亿个这样的整数，并且次序是随机的。请查找一个此文件不存在的32位整数。
当然，主存足够的话，我们可以使用上章提到的位图法，2^32二进制位，如果用bitset那会超过数组大小范围（即0x7fffffff），使用上章提到的int型数据转换，倒是可以实现。但是，如果内存有限，毕竟你无法一下就开辟536870912个B，太浪费资源了，不是吗？
假设，我们只有上百字节的可用内存空间，我们就要使用书中提到的二分查找法，具体原理这里不论述，下面是关键的部分：
//每次循环将初始文件转化 ...
书中提到了产生大量不重复数据的需要：
产生NUM个N内的32位数字
for (i = 0;i < NUM;++ i)
{
temp = (double)rand()/(RAND_MAX+1)*N;
bits = temp / BITSPERWORD;
n = temp % BITSPERWORD;
while (a[bits] & (1<<n)) //already existing number
{
//就近选择
if (temp >= N)
...
人所处的人生阶段不同，立场或视角就不一样。现在我们都已毕业，再要回顾自己的求学历程，可能会用三言两语就把它打发掉，但这些毕业之前的文字，写的都是自己作为学生感兴趣的东西，是自己作为学生认为重要的东西。这种体验很难再现--所幸我们留下的文字不是事后的点评，而是亲历现场的记录。
在研究用stream产生二元组，或是三元组时（满足一定约束，i<j等等）我们利用流的特性只产生前部分的数据，至于什么数据会排在前头，则有我们的规则，总的来说，有一定的约束性，比如产生序列的顺序问题，后来探讨的权重函数也是我们会遇到的问题。（plt Scheme上对流的支持不好，才有mit Scheme的编译器实现）
;产生三元组的方法可以参照下图：
S0T0U0
S0T0U1 S0T0U2
S0T0U3 …
S0T1U1 S0T1U2
S0T1U3 …
S0T2U2 S0T ...