Python 基础入门笔记(2)——函数、模块和包

函数、模块和包对于代码的复用都有非常重要的意义,当然面向对象中的类其实在代码的复用性上也有举足轻重的地位。前天睡前看了《a byte of python》中关于函数、模块和包的这个部分,今天又查了查官网文档以及网上的其它一些资料,把一些疑惑给解决。现在写一下关于这部分的笔记,用以加强记忆同时以备后用。

Read More

都废

《废都》,便是迷醉于欲望之中,却又无法抽身自救的那么一群人组成。即便是尼姑庵的慧明亦脱不出肉欲 、权欲的高墙。大概世道如此,现实并不是人们掉进了欲望的天坑,反而是,欲望便如已然合围的高墙,人生而就在墙内。不是陷入了,而是逃不出。

Read More

Python 基础入门笔记(1)

内建类型

python 中提供的内建类型大概与C++中提供的相仿,却更简洁。

数值方面的内建类型有整型、浮点型、和复数类型三种。在C++中虽然也有复数类型,但却是由标准库提供的。另外,python中整数的表示就是整形,没有如C++中的长整型短整形之说。浮点数的表示也没有浮点型和双精度型的区分。

Read More

B-树的C++实现

与之前实现哈希表、红黑树…这些数据结构和算法不同,B-trees的实现不再追求模仿STL,因此没有实现b-trees自己的迭代器。这些天温习之前的笔记的过程中意识到了一个问题,所有这些的数据结构毕竟只是作为练习之用,而不是出于作为以后使用的库的目的。故应当以逻辑清晰为第一要务。B-trees的实现是转变的一个开始,以后关于算法导论中的算法和数据结构的实现力求立足与算法本身而不是C++的淫技。

Read More

算法导论——B-trees

B-trees(叫“B树”还是“B-树”?我还是用它的英文名吧),是一种为磁盘或
其它辅存设备而设计的平衡树。它与红黑树有些类似,但是在节省IO操作
上比红黑树表现的更好。很多数据库系统会用B-trees或它的变形来存储
信息。

B-trees的特点是,一个结点可以有n个关键字,这些关键字把一段数据划
分成n+1段,对应n+1个孩子,如下图所示:

Read More

算法导论——平摊分析

平摊分析(Amortized Analysis)将数据结构的不同操作放到一起来考虑,而不是仅对某种操作的单一考虑。在平摊分析中,不会涉及概率问题。平摊分析可以用来证明,在一系列操作中,即使某个操作代价很大,但平均代价仍是很小的。本文记录三种平摊分析最常用的技术。

聚集分析(Aggregate analysis)

在聚集分析中,要证明n个操作(可以是不同种类的操作)构成的操作序列在最坏情况下用时T (n),因此每个操作的平均时间为T(n)/n,在平摊分析中,平均代价被指派为平摊代价。看下面一个栈操作的实例。

Read More

赫夫曼编码

赫夫曼编码(huffman codes)是一种非常有用的数据压缩方法,通常能将数据压
缩20%~90%。从具体问题出发,假设我们有一包含10000个字符的文件,这些字
符仅由6个不同的字符组成,就设这6个字符分别为“abcdef”,下面的表给出了
这6个字符在整个文件中的占比,和两种不同的编码方式。

Read More

贪心算法

与动态规划相同贪心算法通过做出一系列选择来构建出问题的最优解,不同的是贪心算法
并不会全局考虑各种选择,它只做当前看起来最佳的选择。如君所见,贪心算法企图用每
一步的最优解来构建出整个问题的最优解。这并不能保证总能构建出最优解,但它通常能
做到。我们可以先看一个具体的问题——活动安排问题。

Read More

最优二叉查找树

假如我们要设计一个简单的程序将一段英文翻译成法语,那么就需要为每个
英语单词找到对应的法语单词,简单的做法是在单词库中对每个单词进行遍
历查找。更快一点的做法是,我们可以将单词库建成一颗平衡二叉搜索树
——用英文单词做Key,对应的法语单词做附属信息。第二种方法,虽然可以保
证每个单词的查询时间控制在O(lgn),不过却也有不合理之处。由于单词出现
的频率有高有低,于是一些常用单词离根节点很远,而一些很生僻的单词却
在根节点附近。可见用一颗平衡二叉搜索树来做这个问题并不是非常高效,在
这儿就引出了另一种二叉查找树——最优二叉查找树。

Read More

最长单调子序列问题

Exercises 15.4-5

Give an \(O(n^2)\)-time algorithm to find the longest
monotonically increasing subsequence of a sequence of n
numbers。

Read More