存档

2012年5月 的存档

二路归并 & 插入归并 & 原地归并

2012年5月31日 4 条评论

---

本节回顾整理归并排序算法常见的几种形式,并实现。一般来讲,我们所说的归并排序都是指二路归并(非多路归并),归并排序很基础,其涉及的分治思想应用也很广泛。这里不赘述基本归并排序的思想。

插入归并

归并排序的时间复杂度为O(nlgn),空间复杂度为O(n);

但是一般来讲,基于从单个记录开始两两归并的排序并不是特别提倡,一种比较常用的改进就是结合插入排序,即先利用插入排序获得较长的有序子序列,然后再两两归并(改进后的归并亦是稳定的,因为插入排序是稳定的)。之所以这样改进是有原因的:尽管插入排序的最坏情况是O(n^2),看起来大于归并的最坏情况O(nlgn),但通常情况下,由于插入排序的常数因子使得它在n比较小的情况下能运行的更快一些,因此,归并时,当子问题足够小时,采用插入排序是比较合适的。

复杂度分析

下面分析下插入归并排序最坏情况下的复杂度:假设整个序列长度为n,当子序列长度为k时,采取插入排序策略,这样一共有n/k个子序列。

子序列完成排序复杂度:最坏情况下,n/k个子序列完成排序的时间复杂度为O(nk)。证明:每个子序列完成插入排序复杂度为O(k^2),一共n/k个子序列,故为O(nk)。

子序列完成合并复杂度:最坏情况下,合并两个子序列的时间复杂度为O(n),一共有n/k个子序列,两两合并,共需要lg(n/k)步的合并,所以这些子序列完成合并的复杂度为O(nlg(n/k))。

所以改进后的插入归并排序的最坏情况的复杂度为O(nk+nlg(n/k)),这里k的最大取值不能超过lgn,显然如果k大于lgn,复杂度就不是与归并一个级别了,也就是说假设一个1000长度的数组,采用插入策略排序子序列时,子序列的最大长度不能超过10。

阅读全文...

虚函数(多态)& 虚继承

2012年5月23日 2 条评论

---

熟悉多态的都知道,虚函数的动态绑定是通过一张虚函数表来实现的,编译器在对象内存中维护一个指向虚函数表(vtable)地址的指针vptr。

对于虚继承,编译器需要在对象内存中维护一个虚拟指针指向父类,虚继承是为了解决多重继承中的二义性问题。

关于虚函数表以及各种情况下对象的内存分布,已经有很好的博客做了分析,相关知识可以参见陈皓博客:

C++虚函数表解析:http://blog.csdn.net/haoel/article/details/1948051

C++对象内存布局(上):http://blog.csdn.net/haoel/article/details/3081328

C++对象内存布局(下):http://blog.csdn.net/haoel/article/details/3081385

本文只是在看了上面几篇博客后写的一道小题来测试验证,以便加深印象。

测试分析了虚函数的单继承和多继承情况、虚继承的单继承和多继承情况、虚函数和虚继承同时出现的情况。代码如下:

阅读全文...

《深入搜索引擎》读书笔记:第一章

2012年5月18日 4 条评论

---

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

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

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

历史回顾

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

工作团队:67人(号称是高效团队)

耗时:7个月

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

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

发展

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

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

个人感悟:

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

全文检索:

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

阅读全文...

成员在类中的偏移量 & 类成员指针

2012年5月18日 没有评论

---

看一道笔试题(引自程序员面试宝典):写出程序输出结果

#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++必知必会》中的一些知识说一下自己的理解。

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

阅读全文...