勇幸|Thinking

---

最近想慢慢整理点关于搜索引擎的资料，主要结合自己实现的简易搜索引擎框架（以后慢慢展开）和《深入搜索引擎》这本书。

为了加深理解吧，也为了理解相关技术诞生的必要性，根据第一章内容简单回顾下历史:-)。

第一章主要讲述了处理海量数据时，索引与压缩技术的必要性。这里交代了在过去制作一个词汇索引是多么的耗时与费劲，从而引入本书的主题。

历史回顾：

早期的词汇索引：1911年，为方便读者在英国诗人威廉.华兹华斯的诗集中找到感兴趣的词汇，对约211000个词汇建立了一个长达1136页的词汇索引。

工作团队：67人（号称是高效团队）

耗时：7个月

所用材料：大量的卡片、剪刀、胶水等

著名词汇索引工作：19世纪和20世纪早期完成，例如《圣经》、莎士比亚著作等。

发展：

20世纪六七十年代，原因是有了计算机的辅助。

那个时候计算机虽不像现在这样智能，但也大量地减少了人们的工作，一个例子：拜伦的诗集，人工编撰的索引耗时25年，使用卡片285000张，1965年使用计算机辅助只需要几天就可以完成这个工作。这的确很震撼。

个人感悟：

早期的词汇索引工作意味着常年的辛勤工作，不知道如果他们知道现在使用计算机建立一个索引的时间后会作何感想，不得不佩服先人们的毅力，更为重要的是他们坚信词汇工作的价值并为之奋斗的那种信念。

全文检索：

随着计算机的发展，词汇编撰工作也越来越轻松和容易了，一个自然的结果就是：需要为任何文本都创建词汇索引，即全文索引。

阅读全文...

---

看一道笔试题（引自程序员面试宝典）：写出程序输出结果

#include <stdio.h>

class A
{
public:
	A() {m_a = 1; m_b = 2;}
	~A() {}
	void fun() {printf("%d %d", m_a, m_b);}
private:
	int m_a;
	int m_b;
};

class B
{
public:
	B() {m_c = 3;}
	~B() {}
	void fun() {printf("%d", m_c);}
private:
	int m_c;
};

void main()
{
	A a;
	B *pb = (B*)(&a);
	pb->fun();
}

程序的输出结果为1。

暂且不讨论该程序设计有多么糟糕，但程序主要考察关于类对象成员调用的机制，关于这方面，据说在《深入理解C++对象模型》中有详解，我没有做深入研究，只是根据看《primer》和《C++必知必会》中的一些知识说一下自己的理解。

这里主要涉及到两方面：一是对象调用成员函数时会将调用对象与函数绑定；二是对象访问成员是根据该成员距离对象的偏移量来访问的，而不是根据成员名来访问，所谓偏移量，就是告诉你一个特定的成员位置距离对象的起点有多少个字节。

阅读全文...

---

四月份还没写，不能这么荒废了呀，赶紧水一篇吧，哈哈。前些日子回顾了DP的一些基础，就做一下整理吧，从0-1背包开始。

本节回顾0-1背包的基本模型，关于它的实现有很多种写法，这里对不同实现做个简单列举，主要是写代码练手了，主要有以下几方面内容：

==0-1背包问题定义 & 基本实现

==0-1背包使用滚动数组压缩空间

==0-1背包使用一维数组

==0-1背包恰好背满

==0-1背包输出最优方案

========================================

0-1背包问题定义 & 基本实现

问题：有个容量为V大小的背包，有很多不同重量weight[i](i=1..n)不同价值value[i](i=1..n)的物品，每种物品只有一个，想计算一下最多能放多少价值的货物。

DP的关键也是难点是找到最优子结构和重叠子问题，进而找到状态转移方程，编码就相对容易些。最优子结构保证每个状态是最优的，重叠子问题也即n状态的求法和n-1状态的求法是一样的；DP在实现上一般是根据状态转移方程自底向上的迭代求得最优解（也可以使用递归自顶向下求解）。

回到0-1背包，每个物体i，对应着两种状态：放入&不放入背包。背包的最优解是在面对每个物体时选择能够最大化背包价值的状态。0-1背包的状态转移方程为

f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] }

阅读全文...

---

读书不是目的，关键在于思考。

很早就在水木上看到有人推荐《The C Programming Language》这本书，一直都没看，开学一个月就专心拜读了一下，并认真做了课后习题。读来收获不少，主要有两点：一是加深了自己对一些基础知识的理解和感悟；二是从中学到了一些不错的编程风格和设计思想，这些东西虽看起来不起眼但细细嚼来还是很值得学习的。下面就从四个方面做一个小总结，水平有限，加之刚读第一遍，难免有疏漏和错误，非常欢迎批评补充。

===读书感悟===

===设计思想===

===编程风格===

===经典例程===

读书感悟

首先，不得不说这不愧为大师之作（网上将其誉为C圣经），一本薄的不能再薄的书，200多页，却涵盖了C语言的大部分精粹；值得一提的是，该书仅仅定价30元，这在计算机类书籍中可以说是很便宜了，与市面上充斥的各种C语言教程在性价比上形成了很大的对比。不过不得不承认，个人感觉这不是一本入门书，读起来是需要一定基础的。

其次，说一下该书的撰写风格和读书建议。书中不是成篇幅地罗列一个个语法和知识点，而是以例程驱动，大部分知识点都是以一个小程序来说明，所以建议读的过程中也将例程当做习题来做，然后与作者给出的程序进行对比，会发现自己的思维是多么的不缜密，考虑问题是多么的欠缺，等你慢慢“上道”了，写出一个和作者类似甚至觉得比他给出的答案要好的时候，兴趣和成就感便会促使你良性循环。

也许有人会说，书中的例子很简单，但我想说尽管很简单，但每个例子都是经典之作，而且能有效地治理眼高手低，在编写代码的过程中，太多的细节让人醍醐灌顶，可谓处处珠玑，书中一些精巧的程序段不禁会让人感觉：啊哈，原来是这样，原来还可以这样写。这样读来能明白之前好多不知所以然的地方。

最后，说一下这一本不到300页的书都包含了什么内容。书中从经典的hello world开始，可以说是手把手编写并讲述了C语言的大部分语法，不仅如此，更实现了二分查找、快排、希尔排序（这个的实现比我们数据结构中学习的要巧妙不少）、链表、二叉树、哈希这些重要的数据结构和算法。书中的大部分例程不仅能让你了解C，不仅能教你如何编写有效率且易读的代码，更能让你了解一些底层的设计思想，例如getchar，strcpy，fopen，printf等众多库函数的实现思想都有体现，帮助你探索源码，追根溯源。另外书中还包含了一些系统调用接口，编译原理（一个递归下降的语法分析，这部分没看懂，还要再读啊）的实现等。

阅读全文...

---

发信人: clarkkevin (过河卒), 信区: job
标  题: 过来人对于在校生找工作的一点看法
发信站: 兵马俑BBS (Sun Mar 18 00:21:10 2012), 本站(bbs.xjtu.edu.cn)

今天看了大家在网上就西邮的学生蔑视交大学生的事情大发感慨，所以想写点东西供大家参考。

本人07年硕士毕业，毕业后去了上海在一个外资公司干了三年时间，10年从公司辞职回到西安自主创业，目前有自己的一个小公司。当然也是刚刚起步。

谈谈我对与工作的一个体会还有我对于人生的一个观点。记得前两天看《钱学森》的时候钱老在病榻之时说过，想作为一个合格的科技工作者不能埋头于技术本身，还要懂得文学与音乐，记不得具体的说法了，大概就是这个样子。

以下是我真实的经历，与诸公分享。

我是07年5月30号到上海报道，这一天股市大跌，所以我记忆深刻，我刚到上海就发现身边的人不是在讨论股票，就是在讨论房子，我一直问自己的一个问题是我怎么能在上海买得起房子，我当时的观点是：社会是不公平的，又是公平的，我不用去关心这些问题，我要做的就是努力学好技术，上海由10000套房子，我就必须排名在10000名以内，我就能有房子，因而我在刚到公司的一年时间里，每天晚上都工作到11点，每天我老婆都睡着了，我还要看很长时间的书，经常一个月30天都在公司里，这样的工作确实起到了一定的效果，我的技术实力很快在公司得到了认可，在第一年我的调薪最后我了解到是我同期去的人的三倍。我说这些不是为了炫耀，是为了给我真正想说的做一个铺垫。

阅读全文...