2014年5月 – 第2页

Python: str

2014/05/212014/05/21 Sword York 评论

string应该算比较常用的类型，特别是处理文本方面。Python 3对字符串的支持是原生的Unicode,不用像Python 2一样, u’我’。

string类型:

Python支持普通字符串，raw字符串和bytes字符串。raw的话不会转义任何字符，但是不能以单数的’\’结尾,特别适合window文件目录（实际上Python会自动处理这个问题）。bytes就是把字符串的编码存下，还有bytearray是可变的。

string操作:

由于string是不可变的，操作一般都会产生新的对象。比如 s[::-1] 会在别的内存产生逆序的字符串。Python函数 len(s) 返回的不是占用的字节数，而是字符数。如 len('我去') 的结果是2。Python有很多string对象的内置方法，不一一举例。要注意的是，Python还有个模块叫string，里面有也不错的内容。

format:

Python有三种格式化字符串的方法。%差不多跟C一样,format比较先进跟php有点像,还有就是string.Template。我只关注format，强大而简单。

[[fill]align][sign][#][0][width][,][.precision][typecode]

1	[[fill]align][sign][#][0][width][,][.precision][typecode]

以上是format的基本格式，看到就傻了。但是用个例子就完全明白了。具体含义可以动手实验得出。我也讲不清。

'My {m[kind]:>10s} runs on {s.platform:<20s} test {f[1]:.3e}'.format(s=sys,m={'kind':'laptop'},f=[1,11111.2222222])

1	'My {m[kind]:>10s} runs on {s.platform:<20s} test {f[1]:.3e}'.format(s=sys,m={'kind':'laptop'},f=[1,11111.2222222])

总之format可以以各种牛X的方式格式化字符串。

意外收获:

在Python中使用dict,tuple什么的类型有时不能直接使用，要先unpack，说白了就是去掉外面的括号。下面分别是dict和tuple的unpack。

D = dict(name='Bob', job='dev')
'{name} {job} {name}'.format(**D)         #unpack

x = Fraction( *(0.25).as_integer_ratio()) #unpack

D = dict(name='Bob', job='dev')

'{name} {job} {name}'.format(**D) #unpack

x = Fraction( *(0.25).as_integer_ratio()) #unpack

[第9天]内存管理

2014/05/212014/05/21 Sword York 评论

今天作者先放下鼠标的问题，因为觉得会让读者感到无聊。确实。。今天作者初步讲了一下怎么测试内存容量以及测试的原理。

测试原理：

往特定位置写入一个特定的数据如0xaa55aa55，进行反转，然后与0x55aa55aa比较是否相等。然后作者还说继续反转再与0xaa55aa55比较。我不是很清楚为什么要比较两次。。先照做。只要两次对比中有一次不一样就认为这个内存位置不是完整的，即到内存结尾了。

禁用缓存：

cache的存在让上面的方法失效。因为CPU可以不访问内存直接在cache里操作。自然结果都是正确的，就无法判断内存大小。作者是先禁用了cache。原理有点蛋疼，主要是对CR0寄存器的某一标志位操作，需要设置第30位和29位为1,又因为x86是小端记法，所以设置 #define CR0_CACHE_DISABLE 0x60000000 。代码见github。

加速处理：

作者原来的做法是每次检测4B。速度自然慢，可以0x1000位（4KB）一起检测，然后看最后一位就行，虽然会损失精度，但相对很小。代码如下：

unsigned int memtest_sub(unsigned int start, unsigned int end){
	unsigned int i, *p, old, pat0 = 0xaa55aa55, pat1 = 0x55aa55aa;

	for(i = start;i<=end;i+= 0x1000){
		p = (unsigned int *) (i + 0xffc);  // test last 4 bytes
		old = *p;
		*p = pat0;
		*p ^= 0xffffffff;
		if( *p != pat1 ){
not_memory:
			*p = old;
			break;
		}
		*p ^= 0xffffffff;

		if (*p != pat0){
			goto not_memory;
		}
		*p = old;
	}
	return i;
}

unsigned int memtest_sub(unsigned int start, unsigned int end){

unsigned int i, *p, old, pat0 = 0xaa55aa55, pat1 = 0x55aa55aa;

for(i = start;i<=end;i+= 0x1000){

p = (unsigned int *) (i + 0xffc); // test last 4 bytes

old = *p;

*p = pat0;

*p ^= 0xffffffff;

if( *p != pat1 ){

not_memory:

*p = old;

break;

}

*p ^= 0xffffffff;

if (*p != pat0){

goto not_memory;

}

*p = old;

}

return i;

}

GCC优化：

作者说他在编译后内存检测完全没有用，看汇编代码后发现判断被去掉了。原因是gcc自动优化了。还能不能好好玩耍了。还好我没有。但我使用-O1选项后也悲剧了。具体原因见书中解释。作者一怒就用了汇编。我不使用-O1没事就算了，直接用C。

内存管理：

内存管理就是指内存的分配和释放。这是所有操作系统的基本职责。否则不知道内存用到哪了，不仅容量是个问题而且可能引起重叠。内存管理的方式大致有Single allocation，Partitioned allocation，Paged memory management，Segmented memory management。作者提供的内存管理我分不清是属于那一类。比较像Partitioned allocation。基本原理是从现有的空闲内存项中找到合适大小的分配。回收的时候看看能不能合并。不能合并的话新建表项。代码有点多。见github。

注意事项：

系统使用区域不能分配。我的系统内存与作者的有点不一样。然后后来被分配出去就死机了。所以要注意。今天没有分配内存，明天就有了。

链接：

Fisher’s linear discriminant

2014/05/172014/05/29 Sword York 2 条评论

Fisher’s linear discriminant通常也被称为Linear discriminant analysis (LDA)。LDA的目标是在保持类别信息的基础上降维。这跟PCA以及Factor analysisi很相似，都是降维。值得注意的是，LDA是完全不同的效果。而且LDA是监督学习。

原理介绍：

先定义两个方差。

$\begin{align*} between-class \quad covariance:\quad\quad & S_b = \sum\limits_{j=1}^c n_j*(m_j - m)*(m_j - m)^T \\ with-in \quad class\quad covariance:\quad\quad &S_w = \sum\limits_{j=1}^c\sum\limits_{i\in V_j} (x_i-m_j )*(x_i-m_j)^T \end{align*}$

看起来很复杂。其实就是求方差。第一个求的是每个分类之间的方差， $m = \sum\limits_{i=1}^n x_i$ 是所有数据的均值。 $m_j =\cfrac{1}{n_j} \sum\limits_{i\in V_j} x_i$ 是某类别内的均值。 $n_j$ 指j类中数据量。

目标是 $y = W^TX$ ，这个W要使得 $J(W) =tr(\cfrac{W^T*S_b*W}{W^T*S_w*W})$ 最大。为什么最大就可以了呢。简单的说就是每个类的内部方差要尽量小，类之间的方差要大。详细推导见链接。

解法：

过程有点麻烦，反正是根据拉格朗日来的。可以见笔记。解为 $S_b*W = S_w*W*\Lambda$ 。这个方程叫Generalized eigenvalue problem。解法有很多。老师提到了一本叫 Matrix Computations的书，据说会让人很爽，里面有详细的说明。最简单的方法，是直接求 $S_t=S_w+S_b$ 伪逆，就算 $S_t$ 不可逆，这也是精确解。原式就变为 $pinv(S_t) * S_b*W = W*\Lambda$ ，这个就熟悉了，直接SVD即可。

实验：

no try no high! 果断来一发。首先假设有两类，这个有助于理解为什么这么做。没有必要两个类别中的数据量一样。写起来方便就设成一样了。可以看到效果如下图。可以看到这两个类还是有明显的界限的。

c = 2;
X1 = [4,1;2,4;2,3;3,6;4,4;];
X2 = [9,10;6,8;9,5;8,7;10,8;];

% mean
m1 = sum(X1) / size(X1,1)
m2 = sum(X2) / size(X2,1)

% with-in class covariance
Sw = (X1 - m1)' * (X1 - m1) + (X2 - m2)' * (X2 - m2);

% between-class covariance
% Sb
m = ( sum(X1) + sum(X2) ) / (size(X1,1) + size(X2,1));
Sb = 0;
Sb = Sb + size(X1,1) * (m1 - m)' * (m1 - m);
Sb = Sb + size(X2,1) * (m2 - m)' * (m2 - m);

% the vector
[u,lambda,v] = svd( pinv(Sw+Sb) * Sb);
w = u(:,1)

c = 2;

X1 = [4,1;2,4;2,3;3,6;4,4;];

X2 = [9,10;6,8;9,5;8,7;10,8;];

% mean

m1 = sum(X1) / size(X1,1)

m2 = sum(X2) / size(X2,1)

% with-in class covariance

Sw = (X1 - m1)' * (X1 - m1) + (X2 - m2)' * (X2 - m2);

% between-class covariance

% Sb

m = ( sum(X1) + sum(X2) ) / (size(X1,1) + size(X2,1));

Sb = 0;

Sb = Sb + size(X1,1) * (m1 - m)' * (m1 - m);

Sb = Sb + size(X2,1) * (m2 - m)' * (m2 - m);

% the vector

[u,lambda,v] = svd( pinv(Sw+Sb) * Sb);

w = u(:,1)

这个2类的不好玩啊。我曾经在2维数据上分5类，后来发现傻逼了。LDA做不了这事。LDA是降维到c-1。所以只能3类个3维数据到2维了。否则没法画啊。具体代码见github。效果如下。

PCA vs LDA:

最直观的解释如下所示:

PCA是抽取主要的特征，要取方差最大的方向，不管类别间的差别。而LDA则是根据类别来降维。有本质上的区别。可以看一下3维数据在PCA和LDA方法下的结果。

Fisher:

Ronald Aylmer Fisher在统计方面贡献很大。他设计了一个随机实验叫Lady Tasting Tea，是在一本名为《The Design of Experiments》书中提到。然后我们上课的老师说Fisher写了一本书叫《The Lady Tasting Tea》，其实不是他写的，但根据评论来看确实是一本好书，介绍了统计学的发展。

链接:

月份：2014年5月