2007百度公司招聘试题--尝试解答

在网上看到百度07年的招聘试题，原文在这里，发现大部分不会做，没有一个题目有把握，利用网络资源吧每一个题，都尽可能详细的找到答案，记录在这里。

一、选择题：15 分 共 10 题 
1. 在排序方法中，关键码比较次数与记录地初始排列无关的是： 
A. Shell 排序 B. 归并排序 C. 直接插入排序 D. 选择排序

解：这一题自己的解答是D，选择排序的比较次数是固定的，要进行(1/2)n*(n-1)次比较。而插入排序，根据原序列的情况不同，比较次数不同，如果远序列是按照从小到大有序的排列，则只需要n此比较就可以；如果最糟的情况下，即逆序排列，则要进行(1/2)n*(n-1)此比较。Shell排序，在本质上可以看成是插入排序，所以也是与数列的初始排列有关的。归并排序，可以设一个这样的例子，一个长度为n的数列，最后一次归并前半部分为和后半部分分别是有序的，若前半部分所有的元素都小于后半部分，这时最后一次归并就只要比较n/2次；另外，最后一次归并前，前部分每个隔一个元素比后半部分的大，这样前后部分的元素交替进入有序数列，这样就要进行n次比较。

2. 以下多线程对 int 型变量x的操作，哪几个需要进行同步： 
A. x=y; B. x++; C. ++x; D. x=1; 

解：下面是反汇编的代码，从汇编代码中就能看出此题肯定要选BC，A的争议比较大。

x = y;
00411A25 mov eax,dword ptr [y]
00411A28 mov dword ptr [x],eax

x ;
00411A2B mov eax,dword ptr [x]
00411A2E add eax,1
00411A31 mov dword ptr [x],eax

x;
00411A34 mov eax,dword ptr [x]
00411A37 add eax,1
00411A3A mov dword ptr [x],eax

x = 1;
00411A3D mov dword ptr [x],1

这个题目，还有非常专业的解释在这里：http://www.parallellabs.com/2010/04/15/atomic-operation-in-multithreaded-application/可以好好看下一

3. 代码 
void func() 
{ 
　　static int val; 
　　… 
} 
中，变量 val 的内存地址位于： 
A. 已初始化数据段 B.未初始化数据段 C.堆 D.栈 

4. 同一进程下的线程可以共享以下： 
A. stack B. data section C. register set D. thread ID 

5. TCP 和 IP 分别对应了 OSI 中的哪几层？ 
A. Application layer B. Data link layer C. Presentation layer D. Physical layer E. Transport layer F. Session layer G. Network layer 

6. short a[100]，sizeof(a) 返回？ 
A. 2 B. 4 C. 100 D. 200 E. 400 

7. 以下哪种不是基于组件的开发技术_____。 
A. XPCOM B. XP C. COM D. CORBA 

8. 以下代码打印的结果是（假设运行在 i386 系列计算机上）：

字串2

struct st_t 

{ 
　　int status; 
　　short *pdata; 
　　char errstr[32]; 
}; 

st_t st[16]; 
char *p = (char *)( st[2].errstr + 32 ); 
printf( "%d", ( p - (char *)(st) ) ); 

A. 32 B. 114 C. 120 D. 1112 

9. STL 中的哪种结构是连续形式的存储： 
A. map B. set C. list D. vector 

10. 一个栈的入栈序列是 A，B，C，D，E，则栈的不可能的输出序列是： 
A. EDCBA B. DECBA C. DCEAB D. ABCDE 

二、简答题：20 分，共 2 题 
1. （5 分）重复多次 fclose 一个打开过一次的 FILE *fp 指针会有什么结果，并请解释。 
考察点：导致文件描述符结构中指针指向的内存被重复释放，进而导致一些不可预期的异常。 

2. （15 分）下面一段代码，想在调用 f2(1) 时打印 err1，调用 f2(2) 时打印 err4，但是代码中有一些问题，请做尽可能少的修改使之正确。 
1 static int f1( const char *errstr, unsigned int flag ) { 
2 　　int copy, index, len; 
3 　　const static char **__err = { "err1", "err2", "err3", "err4" };

字串2

4 
5 　　if( flag & 0x10000 ) 
6 　　　　copy = 1; 
7 　　index = ( flag & 0x300000 ) >> 20; 
8 
9 　　if( copy ) { 
10 　　　　len = flag & 0xF; 
11 　　　　errstr = malloc( len ); 
12 　　　　if( errstr = NULL ) 
13 　　　　　　return -1; 
14 　　　　strncpy( errstr, __err[index], sizeof( errstr ) ); 
15 　　} else 
16 　　　　errstr = __err + index; 
17 }&nbs
p;
18 
19 void f2( int c ) { 
20 　　char *err; 
21 
22 　　swtch( c ) { 
23 　　case 1: 
24 　　　　if( f1( err, 0x110004 ) != -1 ) 
25 　　　　　　printf( err ); 
26 　　case 2: 
27 　　　　if( f2( err, 0x30000D ) != -1 ) 
28 　　　　　　printf( err ); 
29 　　} 
30 } 

三、编程题：30 分 共 1 题 
注意：要求提供完整代码，如果可以编译运行酌情加分。 

1. 求符合指定规则的数。 
给定函数 d(n) = n + n 的各位之和，n 为正整数，如 d(78) = 78+7+8=93。 这样这个函数可以看成一个生成器，如 93 可以看成由 78 生成。 字串3 
定义数 A：数 A 找不到一个数 B 可以由 d(B)=A，即 A 不能由其他数生成。现在要写程序，找出 1 至 10000 里的所有符合数 A 定义的数。 

输出： 
1 
3 
… 

四、设计题：35 分 共 1 题 
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。 

1. 假设一个 mp3 搜索引擎收录了 2^24 首歌曲，并记录了可收听这些歌曲的 2^30 条 URL，但每首歌的 URL 不超过 2^10 个。系统会定期检查这些 URL，如果一个 URL 不可用则不出现在搜索结果中。现在歌曲名和 URL 分别通过整型的 SONG_ID 和 URL_ID 唯一确定。对该系统有如下需求： 
1) 通过 SONG_ID 搜索一首歌的 URL_ID，给出 URL_ID 计数和列表 
2) 给定一个 SONG_ID，为其添加一个新的 URL_ID 
3) 添加一个新的 SONG_ID 
4) 给定一个 URL_ID，将其置为不可用 

限制条件：内存占用不超过 1G，单个文件大小不超过 2G，一个目录下的文件数不超过 128 个。 

为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？ 

关于多线程中操作的原子性

看到百度07年的一个招聘试题：

以下多线程对 int 型变量x的操作，哪几个需要进行同步：
A. x=y; B. x++; C. ++x; D. x=1;

看到这个题目，觉得还是没有什么把握，到网上搜到一个篇非常详细的文章，很忍不住要转过来，原文地址是：http://www.parallellabs.com/2010/04/15/atomic-operation-in-multithreaded-application/，希望作者不要介意，看到这个作者写博文相当认真，他的博客都是关于并行计算的，地址在这里。此博文详细的介绍了原子性操作的机制，详细的分析解答了此题目。

以下是转载，转载来自parallellabs.com

------------------------------------------------------------------------------

 

多线程程序中操作的原子性

0. 背景

 

原子操作就是不可再分的操作。在多线程程序中原子操作是一个非常重要的概念，它常常用来实现一些同步机制，同时也是一些常见的多线程Bug的源头。本文主要讨论了三个问题：1. 多线程程序中对变量的读写操作是否是原子的？2. 多线程程序中对Bit field（位域）的读写操作是否是线程安全的？3. 程序员该如何使用原子操作？

1. 多线程环境下对变量的读写操作是否是原子的？

我们先从一道很热门的百度笔试题讲起。很多人讲不清楚其背后的原理，下面我们就来对它进行一下剖析（其实这个题目有点歧义，后面我们会讲到）：

以下多线程对int型变量x的操作，哪几个需要进行同步：（ ）
A. x=y; B. x++; C. ++x; D. x=1;

要彻底理解这个问题，我们首先需要从硬件讲起。以常见的X86 CPU来说，根据Intel的参考手册，它基于以下三种机制保证了多核中加锁的原子操作（8.1节）：
（1）Guaranteed atomic operations （注：8.1.1节有详细介绍）
（2）Bus locking, using the LOCK# signal and the LOCK instruction prefix
（3）Cache coherency protocols that ensure that atomic operations can be carried out on cached data structures (cache lock); this mechanism is present in the Pentium 4, Intel Xeon, and P6 family processors

这三个机制相互独立，相辅相承。简单的理解起来就是
（1）一些基本的内存读写操作是本身已经被硬件提供了原子性保证（例如读写单个字节的操作）；
（2）一些需要保证原子性但是没有被第（1）条机制提供支持的操作（例如read-modify-write）可以通过使用”LOCK#”来锁定总线，从而保证操作的原子性
（3）因为很多内存数据是已经存放在L1/L2 cache中了，对这些数据的原子操作只需要与本地的cache打交道，而不需要与总线打交道，所以CPU就提供了cache coherency机制来保证其它的那些也cache了这些数据的processor能读到最新的值（关于cache coherency可以参加我的一篇博文）。

那么CPU对哪些（1）中的基本的操作提供了原子性支持呢？根据Intel手册8.1.1节的介绍：

从Intel486 processor开始，以下的基本内存操作是原子的：
• Reading or writing a byte（一个字节的读写）
• Reading or writing a word aligned on a 16-bit boundary（对齐到16位边界的字的读写）
• Reading or writing a doubleword aligned on a 32-bit boundary（对齐到32位边界的双字的读写）

从Pentium processor开始，除了之前支持的原子操作外又新增了以下原子操作：
• Reading or writing a quadword aligned on a 64-bit boundary（对齐到64位边界的四字的读写）
• 16-bit accesses to uncached memory locations that fit within a 32-bit data bus（未缓存且在32位数据总线范围之内的内存地址的访问）

从P6 family processors开始，除了之前支持的原子操作又新增了以下原子操作：
• Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within a cache line（对单个cache line中缓存地址的未对齐的16/32/64位访问）

那么哪些操作是非原子的呢？
Accesses to cacheable memory that are split across bus widths, cache lines, and
page boundaries are not guaranteed to be atomic by the Intel Core 2 Duo, Intel®
Atom™, Intel Core Duo, Pentium M, Pentium 4, Intel Xeon, P6 family, Pentium, and
Intel486 processors.（说点简单点，那些被总线带宽、cache line以及page大小给分隔开了的内存地址的访问不是原子的，你如果想保证这些操作是原子的，你就得求助于机制（2），对总线发出相应的控制信号才行）。

需要注意的是尽管从P6 family开始对一些非对齐的读写操作已经提供了原子性保障，但是非对齐访问是非常影响性能的，需要尽量避免。当然了，对于一般的程序员来说不需要太担心这个，因为大部分编译器会自动帮你完成内存对齐。

回到最开始那个笔试题。我们先反汇编一下看看它们到底执行了什么操作：

01

x = y;

02	mov eax,dword ptr [y]

03	mov dword ptr [x],eax

04

05

x++;

06	mov eax,dword ptr [x]

07

add eax,1

08	mov dword ptr [x],eax

09

10

++x;

11	mov eax,dword ptr [x]

12

add eax,1

13	mov dword ptr [x],eax

14

15

x = 1;

16	mov dword ptr [x],1

（1）很显然，x=1是原子操作。
因为x是int类型，32位CPU上int占32位，在X86上由硬件直接提供了原子性支持。实际上不管有多少个线程同时执行类似x=1这样的赋值语句，x的值最终还是被赋的值（而不会出现例如某个线程只更新了x的低16位然后被阻塞，另一个线程紧接着又更新了x的低24位然后又被阻塞，从而出现x的值被损坏了的情况）。

（2）再来看x++和++x。
其实类似x++, x+=2, ++x这样的操作在多线程环境下是需要同步的。因为X86会按三条指令的形式来处理这种语句：从内存中读x的值到寄存器中，对寄存器加1，再把新值写回x所处的内存地址（见上面的反汇编代码）。

例如有两个线程，它们按照如下顺序执行（注意读x和写回x是原子操作，两个线程不能同时执行）：

time    Thread 1         Thread 2
0      load eax, x
1                            load eax, x
2      add eax, 1        add eax, 1
3      store x, eax
4                            store x, eax

我们会发现最终x的值会是1而不是2，因为Thread 1的结果被覆盖掉了。这种情况下我们就需要对x++这样的操作加锁（例如Pthread中的mutex）以保证同步，或者使用一些提供了atomic operations的库（例如Windows API中的atomic库，Linux内核中的atomic.h，Java concurrent库中的Atomic Integer，C++0x中即将支持的atomic_int等等，这些库会利用CPU提供的硬件机制做一层封装，提供一些保证了原子性的API）。

（3）最后来看看x=y。
在X86上它包含两个操作：读取y至寄存器，再把该值写入x。读y的值这个操作本身是原子的，把值写入x也是原子的，但是两者合起来是不是原子操作呢？我个人认为x=y不是原子操作，因为它不是不可再分的操作。但是它需要不需要同步呢？其实问题的关键在于程序的上下文。

例如有两个线程，线程1要执行{y = 1; x = y;}，线程2要执行{y = 2; y = 3;}，假设它们按如下时间顺序执行：

time    Thread 1        Thread 2
0        store y, 1
1                            store y, 2
2        load eax, y
3                            store y, 3
4        store x, eax

那么最终线程1中x的值为2，而不是它原本想要的1。我们需要加上相应的同步语句确保y = 2不会在线程1的两条语句之间发生。y = 3那条语句尽管在load y和store x之间执行，但是却不影响x=y这条语句本身的语义。所以你可以说x=y需要同步，也可以说x=y不需要同步，看你怎么理解题意了。x=1是否需要同步也是一样的道理，虽然它本身是原子操作，但是如果有另一个线程要读x=1之后的值，那肯定也需要同步，否则另一个线程读到的就是x的旧值而不是1了。

2. 对Bit field（位域）的读写操作是否是线程安全的？

Bit field常用来高效的存储有限位数的变量，多用于内核/底层开发中。一般来说，对同一个结构体内的不同bit成员的多线程访问是无法保证线程安全的。

例如Wikipedia中的如下例子：

01	struct foo {

02	int flag : 1;

03	int counter : 15;

04

};

05

06	struct foo my_foo;

07

08

/* ... */

09

10	/* in thread 1 */

11

12	pthread_mutex_lock(&my_mutex_for_flag);

13	my_foo.flag = !my_foo.flag;

14	pthread_mutex_unlock(&my_mutex_for_flag);

15

16	/* in thread 2 */

17

18	pthread_mutex_lock(&my_mutex_for_counter);

19	++my_foo.counter;

20	pthread_mutex_unlock(&my_mutex_for_counter);

两个线程分别对my_foo.flag和my_foo.counter进行读写操作，但是即使有上面的加锁方式仍然不能保证它是线程安全的。原因在于不同的成员在内存中的具体排列方式“跟Byte Order、Bit Order、对齐等问题都有关，不同的平台和编译器可能会排列得很不一样，要编写可移植的代码就不能假定Bit-field是按某一种固定方式排列的”[3]。而且一般来讲CPU对内存操作的最小单位是word（X86的word是16bits），而不是1bit。这就是说，如果my_foo.flag和my_foo.counter存储在同一个word里，CPU在读写任何一个bit member的时候会同时把两个值一起读进寄存器，从而造成读写冲突。这个例子正确的处理方式是用一个mutex同时保护my_foo.flag和my_foo.counter，这样才能确保读写是线程安全的。

在C++0x草案中对bit field是这样定义的：
连续的多个非0bit的bit fields是属于同一个memory location的；长度为0bit的bit field会把占单独的一个memory location。对同一个memory location的读写不是线程安全的；对不同memory location的读写是线程安全的。
例如在下图的例子中bf1和bf2是同一个memory location，bf3是一个单独的memory location，bf4是一个单独的memory location：


这里有一个因为Bit field不是线程安全所导致的一个Linux内核中的Bug。

引用一下Pongba的总结：

所以，如果你的多个bitfields是连续的，同时又想要无冲突的读取它们，有两种做法，一是在中间用0大小bitfield隔开，但这种做法实际上就消除了bitfield的节省内存的初衷，因为为了使它们不冲突，至少被隔开的两个bitfield肯定不可能共享byte了。另一种做法当然就是用锁了。

3. 程序员该怎么用Atomic操作？

一般情况下程序员不需要跟CPU提供的原子操作直接打交道，所以只需要选择语言或者平台提供的atomic API即可。而且使用封装好了的API还有一个好处是它们常常还提供了诸如compare_and_swap，fetch_and_add这样既有读又有写的较复杂操作的封装。

常见的API如下：

Windows上InterlockedXXXX的API
GNU/Linux上linux kernel中atomic_32.h
GCC中的Atomic Builtins (__sync_fetch_and_add()等)
Java中的java.util.concurrent.atomic
C++0x中的atomic operation
Intel TBB中的atomic operation

4. 参考文献：

[1] 关于变量操作的原子性(atomicity)FAQ
[2] http://en.wikipedia.org/wiki/Atomic_operation
[3] 关于内存对齐、bit field等 –《Linux C编程一站式学习》
[4] Do you need mutex to protect an ‘int’?
[5] C++ Concurrency in Action
[6] Multithreaded simple data type access and atomic variables

-------------------------------------------------------------------------------------------

转载到这里结束

allellabs.com

Windows多线程编程

前面写了一篇Linux多线程编程，由于算法要整合到一个运行在Windows平台下的系统中，所以需要改成Windows下的多线程方式（看我折腾的）。这里简单列一个Windows多线程编程的例子。其实我也想尝试是用一个跨平台的C++库Boost，Boost::Thread类库可以在不同的平台下运行多线程，而且多线程功能非常丰富和强大，使用起来也很容易，但是还需要安装这个库，先暂时放弃这个方案，因为毕竟我现在需要的多线程功能非常简单。

Windows API实现多线程

在上一篇文章中，已经列出了一个表，列出了Linux线程API和Windows下线程API的大致对应关系。根据那个表，和Linux下多线程经验，也能大概知道Windows下实现多线程的方法首先来看一个例子：

/* example.c */
#include <stdfx.h>
#include <stdio.h>
#include <process.h>

const int NLOOP = 100;
int counter = 0;
void thread(void*);
CRITICAL_SECTION beswap ;
int main()
{
HANDLE pnt[2];
InitializeCriticalSection(&beswap);
pnt[0] = (HANDLE)_beginthread(doit,0,NULL);
pnt[1] = (HANDLE)_beginthread(doit,0,NULL);
WaitForMultipleObjects( 2, pnt, TRUE, 1000L);
DeleteCriticalSection(&beswap);
return 0;
}
void doit(void*)
{
    printf("go...\n");
    int i, val = 0;
    for(i = 0; i < NLOOP; ++i)
    {
        EnterCriticalSection(&beswap);
        val = counter;
         printf("%d\n",val+1);
        counter = val + 1;
        LeaveCriticalSection(&beswap);
    }
    printf("end...\n");
    return ;
}

根据这个例子，多线程的过程解释如下：

1、编写线程函数，这里线程函数要遵循如下函数原型:

DWORD WINAPI threadFunc(LPVOID lpvThreadParm);

函数的输入参数是一个DWORD的类型，可以是一个整数，也可以是一个内存指针，具体的意义由编程者自己决定。返回值是一个DWORD型的值。

2、创建一个线程

一个进程的主线程是由操作系统自动生成，如果你要让一个主线程创建额外的线程，你可以调用来CreateThread完成，使用的时候注意包含#include<process.h>头文件。其函数原型如下：

HANDLE CreateThread(LPSECURITY_ATTRIBUTES lpsa,DWORD cbstack,LPTHREAD_START_ROUTINE lpStartAddr,
LPVOID lpvThreadParm, DWORD fdwCreate,LPDWORD lpIDThread);

     其中，lpsa参数为一个指向SECURITY_ATTRIBUTES结构的指针。如果想让对象为缺省安全属性的话，可以传一个NULL，如果想让任一个子进程都可继承一个该线程对象句柄，必须指定一个SECURITY_ATTRIBUTES结构，其中bInheritHandle成员初始化为TRUE。
    参数cbstack表示线程为自己所用堆栈分配的地址空间大小，0表示采用系统缺省值。 
    参数lpStartAddr用来表示新线程开始执行时代码所在函数的地址，即为线程函数。
    lpvThreadParm为传入线程函数的参数，
    fdwCreate参数指定控制线程创建的附加标志，可以取两种值。如果该参数为0，线程就会立即开始执行，如果该参数为CREATE_SUSPENDED，则系统产生线程后，初始化CPU，登记CONTEXT结构的成员，准备好执行该线程函数中的第一条指令，但并不马上执行，而是挂起该线程。
    最后一个参数lpIDThread 是一个DWORD类型地址，返回赋给该新线程的ID值。

此外，还可以使用_beginthread等函数来创建线程,正如本例子中使用的方法：

handle=(HANDLE)_beginthread(threadFunc,0, NULL);

函数_beginthread的函数原型如下：

uintptr_t _beginthread(
　　void( *start_address )( void * ),
　　unsigned stack_size,
　　void *arglist
　　);

start_address新线程的起始地址，指向新线程调用的函数的起始地址；stack_size stack_size 新线程的堆栈大小，可以为0；arglist arglist 传递给线程的参数列表，无参数是为NULL。

3、终止线程，如果某线程调用了ExitThread 函数，就可以终止自己。

VOID ExitThread(UINTfuExitCode );

这个函数为调用该函数的线程设置了退出码fuExitCode后， 就终止该线程。调用TerminateThread函数亦可终止线程。

BOOL TerminateThread(HANDLE hThread, DWORD dwExitCode);

该函数用来结束由hThread参数指定的线程， 并把dwExitCode设成该线程的退出码。当某个线程不在响应时，我们可以用其他线程调用该函数来终止这个不响应的线程。

4、另外还有设置程序的优先级，挂起和恢复线程之类的。这里就不详述，因为还没有用到。

BOOL SetThreadPriority(HANDLE hThread,intnPriority); // 设置线程优先级
DWORD ResumeThread(HANDLEhThread); // 恢复线程
DWORD SuspendThread(HANDLE hThread); // 挂起线程

5、这里还用到了线程的阻塞函数WaitForMultipleObjects，原型：

DWORD WaitForMultipleObjects(
　　DWORD nCount,
　　const HANDLE* lpHandles,
　　BOOL bWaitAll,
　　DWORD dwMilliseconds
　　);

WaitForMultipleObjects是Windows中的一个功能非常强大的函数，几乎可以等待Windows中的所有的内核对象。当WaitForMultipleObjects等到多个内核对象的时候，如果它的bWaitAll 参数设置为false。其返回值减去WAIT_OBJECT_0 就是参数lpHandles数组的序号。如果同时有多个内核对象被触发，这个函数返回的只是其中序号最小的那个。如果为TRUE 则等待所有信号量有效在往下执行。（FALSE 当有其中一个信号量有效时就向下执行）。

对应的还有一个函数WaitForSingleObject，用来等待指定的内核对象。

6、还有互斥锁的使用方法，在例子中也有很清楚的使用方法。单进程的线程可以使用这种临界资源对象来解决同步互斥问题,该对象不能保证哪个个线程能够获得到临界资源对象,因而该系统能公平的对待每一个线程。

MFC实现多线程

MFC对Windows API进行了封装，可以说使用起来更加简单，而且提供了很多多线程的扩张功能。MFC实现多线程有两种，一种是工作者线程，另一种是用户界面线程。前一种是简单的线程，后一种是带有消息队列的线程。

CWinThread* AfxBeginThread(
AFX_THREADPROC pfnThreadProc,
LPVOID pParam,
int nPriority = THREAD_PRIORITY_NORMAL,
UINT nStackSize = 0,
DWORD dwCreateFlags = 0,
LPSECURITY_ATTRIBUTES lpSecurityAttrs = NULL
);

CWinThread* AfxBeginThread(
CRuntimeClass* pThreadClass,
int nPriority = THREAD_PRIORITY_NORMAL,
UINT nStackSize = 0,
DWORD dwCreateFlags = 0,
LPSECURITY_ATTRIBUTES lpSecurityAttrs = NULL
);

这是一个重载函数，前一个用来创建一个工作线程，后一个用来创建界面线程。MFC框架还提供了很多同步类，来实现线程间的同步和通信，具体的使用方法可以参考MSDN，由于还没有用到，等用到了，再详细总结。另外，在编程中，我也是用WaitForMultipleObjects来等待了AfxBeginThread创建的线程，而没有出现问题。

参考地址：

http://wujblog.appspot.com/2010/09/26/linux-multi-thread.html

http://www.wangchao.net.cn/bbsdetail_69676.html

http://blog.csdn.net/zjl_1026_2001/archive/2008/03/18/2193626.aspx

http://msdn.microsoft.com/en-us/library/s3w9x78e(VS.80).aspx

http://msdn.microsoft.com/zh-cn/library/975t8ks0(v=VS.80).aspx

Linux多线程编程

在背景差分算法的实现过程中，由于要达到实时性的要求，就想用多线程来实现，进行并行计算，充分利用CPU的多核。之前并没有写过多线程的程序，在网上搜索关键字“C++多线程编程”，后来才知道，多线程并不是C++语言的特性，而是与平台有关系，每个平台实现的机制也是不一样的，所以说这种“C++多线程编程“提法就是有问题的。闲话少叙，下面言归正传。

线程的基本概念

线程的基本概念，在网上有很多的介绍，我觉得北大BBS上一个精华帖介绍的比较详细，在这里，线程相关的重要概念有：用户级线程、轻进程(LWP, Lightweight Process)， 非绑定线程(Unbound Treads)，绑定线程(Bound Thread)。对于每个线程有相关的属性和状态。有了多线程，就带来相关的数据访问同步的问题，有互斥锁，条件锁，信号量等等。

Linux系统下的多线程遵循POSIX线程接口，称为pthread。编写Linux下的多线程程序，需要使用头文件pthread.h，连接时需要使用库libpthread.a。顺便说一下，Linux下pthread的实现是通过系统调用clone（）来实现的。clone（）是Linux所特有的系统调用，它的使用方式类似fork，关于clone（）的详细情况，有兴趣的读者可以去查看有关文档说明（这段话是抄过来的，clone()还真的不知道是什么，到时候查一下）。

多线程开发在 Linux 平台上已经有成熟的 Pthread 库支持。其涉及的多线程开发的最基本概念主要包含三点：线程，互斥锁，条件。其中，线程操作又分线程的创建，退出，等待 3 种。互斥锁则包括 4 种操作，分别是创建，销毁，加锁和解锁。条件操作有 5 种操作：创建，销毁，触发，广播和等待。其他的一些线程扩展概念，如信号灯等，都可以通过上面的三个基本元素的基本操作封装出来。下面有一个表，转载自这里（这篇文章严谨的介绍了Linux上线程编程的相关经验）

表 1. 线程函数列表

对象	操作	Linux Pthread API	Windows SDK 库对应 API
线程	创建	pthread_create	CreateThread
	退出	pthread_exit	ThreadExit
	等待	pthread_join	WaitForSingleObject
互斥锁	创建	pthread_mutex_init	CreateMutex
	销毁	pthread_mutex_destroy	CloseHandle
	加锁	pthread_mutex_lock	WaitForSingleObject
	解锁	pthread_mutex_unlock	ReleaseMutex
条件	创建	pthread_cond_init	CreateEvent
	销毁	pthread_cond_destroy	CloseHandle
	触发	pthread_cond_signal	SetEvent
	广播	pthread_cond_broadcast	SetEvent / ResetEvent
	等待	pthread_cond_wait / pthread_cond_timedwait	SingleObjectAndWait

简单的多线程例子

这个表列出了Linux多线程API，作为一个多线程编程的入门，我是参考这里，这个文章对上面每个API的使用方法都有详细的介绍，并且配有相关的例子，是入门很好的资料，但是遗憾的是，他的这些例子，我并没有编译通过，有些地方需要改动一下。下面我也摘抄一部分到这里（做了一点点的修改，原文有一些错误），说先看到一个最简单的多线程的例子：

/* example1.c*/
#include <stdio.h>
#include <pthread.h>
void* thread(void* param)
{
    int i;
    for(i=0;i<3;i++)
        printf("This is a pthread.\n");
}

int main(void)
{
    pthread_t id;
    int i,ret;
    ret=pthread_create(&id,NULL, thread,NULL);
    if(ret!=0){
        printf ("Create pthread error!\n");
        exit (1);
    }
    for(i=0;i<3;i++)
        printf("This is the main process.\n");
    pthread_join(id,NULL);
    return (0);
}

编译上面的程序使用如下命令：

g++ example1.c -lpthread -o example1

顺便提一下，原文上是使用gcc命令，但是我在编译的时候得到了一个错误：undefined reference to `__gxx_personality_v0'，网上有人说使用g++编译程序就能解决，原因是gcc不会帮你链接c++的运行库，但g++会。挺有道理的，似懂非懂。

这样，第一个多线程就能运行了，这里用到了pthred_t 类型，用来标示一个线程它在本质上一个无符号的长整型。函数pthread_create用来创建一个线程，注意线程创建完成就立即运行。此函数的原型是：

extern int pthread_create __P ((pthread_t *__thread, __const pthread_attr_t *__attr, void *(*__start_routine) (void *), void *__arg));

第一个参数是指向线程标识符的指针；第二个参数是一个指向线程属性类型(pthread_attr_t)的指针，用来设置线程的相关属性；第三个参数是线程运行函数起始地址，这个函数需要有这样的原型void* (*) (void*)；最后一个参数是运行函数的参数。当创建线程成功时，函数返回0，若不为0则说明创建线程失败，常见的错误返回代码为EAGAIN和EINVAL。前者表示系统限制创建新的线程，例如线程数目过多了；后者表示第二个参数代表的线程属性值非法。创建线程成功后，新创建的线程则运行参数三和参数四确定的函数，原来的线程则继续运行下一行代码。

这个例子中还有一个函数pthread_join，其原型如下：

extern int pthread_join __P ((pthread_t __th, void **__thread_return));

第一个参数为被等待的线程标识符，第二个参数为一个用户定义的指针，它可以用来存储被等待线程的返回值。这个函数是一个线程阻塞的函数，调用它的函数将一直等待到被等待的线程结束为止，当函数返回时，被等待线程的资源被收回。一个线程的结束有两种途径，一种是象我们上面的例子一样，函数结束了，调用它的线程也就结束了；另一种方式是通过函数pthread_exit来实现。其函数的原型如下：

extern void pthread_exit __P ((void *__retval)) __attribute__ ((__noreturn__));

唯一的参数是函数的返回代码，只要pthread_join中的第二个参数thread_return不是NULL，这个值将被传递给thread_return。最后要说明的是，一个线程不能被多个线程等待，否则第一个接收到信号的线程成功返回，其余调用pthread_join的线程则返回错误代码ESRCH。

线程的属性设置

在上一节的例子里，我们用pthread_create函数创建了一个线程，在这个线程中，我们使用了默认参数，即将该函数的第二个参数设为NULL。的确，对大多数程序来说，使用默认属性就够了，但我们还是有必要来了解一下线程的有关属性。

属性结构为pthread_attr_t，它同样在头文件/usr/include/pthread.h中定义。属性值不能直接设置，须使用相关函数进行操作，初始化的函数为pthread_attr_init，这个函数必须在pthread_create函数之前调用。属性对象主要包括是否绑定、是否分离、堆栈地址、堆栈大小、优先级。默认的属性为非绑定、非分离、缺省1M的堆栈、与父进程同样级别的优先级。

关于线程的绑定，牵涉到另外一个概念：轻进程（LWP：Light Weight Process）。轻进程可以理解为内核线程，它位于用户层和系统层之间。系统对线程资源的分配、对线程的控制是通过轻进程来实现的，一个轻进程可以控制一个或多个线程。默认状况下，启动多少轻进程、哪些轻进程来控制哪些线程是由系统来控制的，这种状况即称为非绑定的。绑定状况下，则顾名思义，即某个线程固定的"绑"在一个轻进程之上。被绑定的线程具有较高的响应速度，这是因为CPU时间片的调度是面向轻进程的，绑定的线程可以保证在需要的时候它总有一个轻进程可用。通过设置被绑定的轻进程的优先级和调度级可以使得绑定的线程满足诸如实时反应之类的要求。

设置线程绑定状态的函数为pthread_attr_setscope，它有两个参数，第一个是指向属性结构的指针，第二个是绑定类型，它有两个取值：PTHREAD_SCOPE_SYSTEM（绑定的）和PTHREAD_SCOPE_PROCESS（非绑定的）。例子如下：

#include <pthread.h>
pthread_attr_t attr;
pthread_t tid;

/*初始化属性值，均设为默认值*/
pthread_attr_init(&attr);
pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);

pthread_create(&tid, &attr, my_function, NULL);

线程的分离状态决定一个线程以什么样的方式来终止自己。在上面的例子中，我们采用了线程的默认属性，即为非分离状态，这种情况下，原有的线程等待创建的线程结束。只有当pthread_join（）函数返回时，创建的线程才算终止，才能释放自己占用的系统资源。而分离线程不是这样子的，它没有被其他的线程所等待，自己运行结束了，线程也就终止了，马上释放系统资源。具体怎么用，还是参考这个原文吧，不然就把原文全部抄袭过来了。

参考地址：

http://fanqiang.chinaunix.net/a4/b8/20010811/0905001105.html

http://fanqiang.chinaunix.net/a4/b8/20010811/0905001105.html

http://www.fegensoft.com/fegensoft2002/seeksilence/Linux/10/8/index.htm

http://blog.sina.com.cn/s/blog_6b2757530100l639.html

在OpenCV中，cvCreateFileCapture函数返回NULL

在OpenCV中，这个函数cvCreateFileCapture用来从视频文件(.avi)获取一个Capture，函数的原型如下：

Capture* cvCreateFileCapture(const char* filename)

在调用的时候发现返回值是NULL。在网上找到解决方法，主要原因还是解码器的问题。即使你的电脑能播放avi文件，但是cvCreateFileCapture只是支持有限的几种avi格式。

解决方法：网上下载安装K-Lite Code Pack解码器，一般就能解决问题。如果还是不行，就要把avi文件转换成Opencv支持的avi格式之一。 OpenCV支持的AVI如下：

Container	FourCC	Name	Description
AVI	'DIB '	RGB(A)	Uncompressed RGB, 24 or 32 bit
AVI	'I420'	RAW I420	Uncompressed YUV, 4:2:0 chroma subsampled
AVI	'IYUV'	RAW I420	identical to I420

本文参考了这里：

http://hi.baidu.com/armlinuxhouse/blog/item/94ff83ffe7eeb649d7887d48.html

http://www.opencv.org.cn/forum/viewtopic.php?t=4711

http://hq.huang.blog.163.com/blog/static/1066821912009758958885/

最大类间方差法(Otsu法)

此方法的目的是把一幅图像，通过一个阈值T的方法，分割成前景和背景两部分。通过选定阈值T，是图像的前景部分和背景部分的差别最大。

其中，前景和背景的差别的衡量标准为如下表达式：g=wf*(uf-u)^2+wb*(ub-u)^2=wf*wb*(uf-ub)^2，其中wf和wb分别为前景和背景所占的比例，uf和ub为前景和背景的平均灰度。Otsu方法，就是寻找一个阈值T，把图像分割前前后景两部分，使前面的公式中g取得最大值。

计算阈值T的算法如下：首先统计一下图像的直方图，或者这里可以在做一下直方图平滑，然后设置T=0到最大值，逐次搜索每个值，得到一个最大的g的阈值T。

类间方差法对噪声和目标大小十分敏感，它仅对类间反差为单峰的图像产生较好的分割效果。当目标与背景的大小比例悬殊时，类间方差准则函数可能呈现双峰或者多峰，此时类间方差法效果就不太适用了。

读“W4: Real-Time Surveillance of People and Their Activites”

本文是PAMI 2000年的文章，解决的问题是实时的监控视频的多人的检测、跟踪以及检测他们的行为，所谓W4就是：where, when, what and who。本文是对于静止的单目的灰度摄像机或者红外摄像机获得的数据进行处理。W4结合形状分析和跟踪来定位人和人的各个部分(包括头，手，脚，躯干)。本文说能够处理320x240达到25 fps (400MHz dual-Pentium II PC)。

本文涉及到背景差分、跟踪和行为检测等多个方面，我这里只是关注背景差分部分。背景模型在整体上来说是一个在训练阶段建立起来的统计模型，每个像素用三个值表示：最小值m(x), 最大值n(x), 连续帧的之间的最大差分值d(x)。

1. 学习初始化背景模型

这个使用两个阶段来排除学习阶段的中场景中的运动像素。第一个阶段是使用针对像素的中值滤波器，在时间上对一段数秒的视频进行滤波来区分运动和静止像素。第二个阶段是利用第一阶段得到的静止像素点建立初始化背景模型，具体操作如下:设V为连续的N个图像的集合，delta(x)和lamda(x)分别表示像素点x的标准差和中值，其中m(x)=min{Vz(x)}, n(x)=max{Vz(x)}, d(x)=max{|Vz(x)-Vz-1(x)|},其中|Vz(x)-lamda(x)| < 2*delta(x), 这样Vz(x)就是表示是静止的像素点。

2. 更新背景模型参数 

W4是基于灰度值的背景模型，光照的变化会明显影响检测，另外长期静止的前景可能会造成误检。本文使用两种背景更新方法：

基于像素的更新：周期的更新背景模型来适应光照的变化；
基于对象的跟新：更新背景来适应场景的物理改变，例如，场景中出现或者移除物体，车辆停靠等。

W4使用如下的方法来更新背景：在跟踪过程中，W4动态建立change map来决定使用何种更新方式，其中change map含有如下三个主要的元素：

• detection support map (gS): 代表在前N帧内被分类为背景的次数, 若x是背景像素gS(x,t)=gS(x, t-1)+1;
• motion support map (mS): 代表当前像素是运动像素的次数，判断一个像素是否为运动像素点方法是：连续三帧之差，都大于2*delta;
• change history map (hS): 代表自从上次被分类为前景的消耗的时间，如果是前景，则hS(x, t)=255, 否则hS(x, t)=hS(x, t-1)-255/N。

W4使用gS来决定背景哪些部分使用基于像素的更新，ms、gS和hS来决定哪些部分使用基于对象的更新。当背景模型被根性后这个change map就被重置为0。在跟踪的过程中，背景模型对前景像素和背景像素分别进行运算，背景模型的更新策略如下：

1. 若gS(x)>K*N，则使用基于像素的背景更新策略，设置为[mb(x), nb(x), db(x)]，即背景点;
2. 若gS(x)<K*N且mS(x)<r*N，则使用基于对象目标的更新，设置为[mf(x), nf(x), df(x)]，即前景点;
3. 如果上面都不符合，就保持原样。

3. 前景检测

首先，每个像素使用如下的方法来把每个像素点分类成前景或者背景：若当前像素点It(x)，满足|It(x)-m(x)|<k*du或者|It(x)-n(x)|<k*du，则判定为背景，其中du为整个图像的d(x)的中值。

BGS-KDE算法：读”Non-parametric Model for Background Subtraction“

本文是ECCV 2000年的文章，"Non-parametric Model for Background Subtraction"，作者是Ahmed Elgammal，Rutgers大学副教授（这个大学好似没听过，查了一下排名在150名左右），他的主页在这里，专注于人的行为分析、跟踪等。他这篇文章可以找得到，还有一个在线版在这里。

这篇文章是2000年的，十年前的文章，也是第一个提出使用KDE方法的。所谓KDE方法是指：Kernel Denity Estimation,即使用核函数来估计概率。核心思想就是根据最近N帧图像，建立N个样本作为背景Kernel模型，在检测的时候，使用相应的kernel函数来估计当前像素值出现的概率，如果大于某一个门限，即为背景。

KDE算法是一个General的方法，如果把所有的Kernel函数取为高斯函数，则KDE函数就退化为generalized的混合高斯模型，这里每一个样本就是一个高斯模型。

值得注意的是：整个KDE算法是基于这样的假设，背景是变化很频繁的，不足以用几个高斯模型来表示，但是在很短的时间间隔内，还是符合一定的分布的，也就是本文所谓的local-in-time，例如高斯模型。

1. 基本背景模型

概率密度估计：Density Estimation

KDE方法也是基于像素的，以下描述都是对于每个像素的。设 x1, x2, x3,....xN是像素的最近N个样本，使用这些样本值，来当前像素点的概率密度函数如：

                           Pr(xt)=[K(xt-x1)+K(xt-x2)+ ... +K(xt-xN)]/N  (1) 

其中，K表示Kernel函数，xt表示像素在时刻t的值。如果Pr(xt)<T,这里T是一个全局门限，说明可以概率小，可以判定为前景，反之为背景。

这里，如果K为高斯函数，就很像混合高斯模型了。而且Pr(xt)公式可以使用查找表方法计算，可以极大提高运算速度。相比与混合高斯模型，因为KDE算法只是依赖于最近的N个样本，很容易“forget”以前的状况，所以可以灵活控制其精确度。

核函数宽度估计：Kernel Width Estimation(我把它称为高斯函数的标准差估计) 

      如果使用高斯函数上面的公式1就可以更加具体化，把高斯函数代入公式1，具体公式见原文，公式中有一个关键参数--高斯分布的标准差，此参数反映了当前像素的变化剧烈情况，可以通过如下方式来估计此参数：对每个颜色通道，N个连续的样本，相邻的两个值的差值|xi - x(i+1)|，在这些连续的(xi, x(i+1) )对中，求得中值m。此中值m与标准差有直接对应关系：
                    delta = m/(0.68*1.414)
        è¿™é‡Œä¸ºä»€ä¹ˆä½¿ç”¨è¿™æ ·ä¸­å€¼æ¥ä¼°è®¡æ ‡å‡†å·®å‘¢ï¼Ÿè¿™æ˜¯å› ä¸ºåœ¨N个样本中，连续的两个值 (xi, x(i+1) )很大可能是属于同一个local-in-time的高斯分布。这样的估计是有效的。

2. 抑制误检(False Detection)

本文把误检来源分为两种，一种是噪声，一种是背景的轻微运动，例如树枝晃动、水面等。第一种物件由于是全局散落的，可以通过滤波或者形态学的方法滤除，后一种由于有空间的聚集特性，很难用传统的滤波方法消除。

分析一下第二种误检的来源，就可以知道，虽然在当前像素点的KDE中不能匹配上，因为这个像素点很可能是在领域中移动过来的，所以这里就可以在当前像素点的一个领域中寻找最佳的匹配，还是使用前面的概率估计公式，在领域中寻找最佳的匹配，即概率的最大值。
             Pn(xt)=max{Pr(xt| By)},
其中By表示xt的领域像素点。若Pn(xt)大于某个门限th1，则确定为背景。

通过上述方法，虽然能去掉一些误检，但是，同时会把一些真实的前景给去掉。考虑到真实的前景有这样的有这样的特点，整个被检测出来的前景一定是在从附近的某个地方移动到这里来的，而不是几个像素点。这里定义一个概率Pc，表示整个被检测出来的连续区域是从附近移动过来的概率。定义如下：
            Pc = Pn(xi)的乘积
其中，xi是被检测出来的连续的区域内的像素。对于一个真实的前景目标，整个被检测出来的连续区域，对于上面的公式的计算结果应该是很小的。

所以综合上面的两个方面，如果一个像素点同时满足Pn>th1和Pc>th2，则表示这是一个误检，重新说一下，应该是第二种误检。

3. 背景更新

背景更新的策略有两种：

1. 选择性更新：即只是把新的样本(sample)添加到那些被判定为背景的像素点模型
2. 盲目更新：即把新的样本添加到任何像素点模型

这两个方法各有弊端，例如第一种方法很依赖与判定的结果是不是正确，如果错了，就会一错再错。第二种方法比较盲目，会把静止前景或者运动很慢的前景融入到背景模型中。本文提出了一个结合两个更新策略的方法，使既能很快的适用新的背景改变，又能对前景，又能足够精确的检测出前景，使用两个model来达到这个目的：Short-term mdel 和 Long-term model：

Short-term model: 这是一个最近(very recent)场景N个样本模型，此模型对场景的变化适应很快，而且对前景检测很敏感。使用选择性策略更新背景模型；

Long-term model: 这个模型保存相对稳定的背景模型，而且改变非常的缓慢。这个模型也包含N个样本，但是此N个样本的所取自的时间窗口比short-term model要宽很多。这个模型使用盲目更新策略更新。

这两个模型检测结果的交集，可以消除短期模型的持续错误前景(false positive)，也可消除长期模型结果中的误检。这里也会造成一个问题，就是同时消除了一些正确的前景，例如在短期的模型中检测出来的静止前景。本文的解决方法是，在短期模型中检测出来的前景，如果与前面的合并结果相邻的话，就判定为最后的前景。（这种解决方法，我有待考察，我并不明白为什么这样处理就可以解决此问题）

4. 阴影检测

阴影检测是背景差分中的难点之一，阴影的特点就是颜色相似，而亮度变低。本文使用了色度坐标(Chromaticity Coordinate)来运算，r=R/(R+G+B), g=G/(R+G+B), b=B/(R+G+B)，其中r+g+b=1，所以一个像素的色度坐标就可以表示为(r, g)二元组。这个二元组，只是记录了色度信息，完全丢失了亮度信息，可能会造成很多的漏检。这里就另外引入一个亮度信息s=R+G+B，所以同样用一个三元组<r, g, s>来表示一个像素，这里色度和亮度信息就完全区分开来了。如果满足色度r,g分量相近，而a<st/sb<1的话，就可能判定为阴影。

在本文中，还是使用KDE的方法如下：使用前面的KDE的方法，设A={x1, x2,...,xn}为一像素的样本，xt为当前像素值，在集合A中选取alpha<(xt/xi)<betaçš„xi组成集合B，对B集合中的元素xi使用二维的(r, g)做KDE运算。这里集合B就称为与当前像素“相关的”背景样æœ
¬ï¼Œè¿™æ ·æœ‰åˆ©äºŽæé«˜è¿ç®—效率。

总结：

本文是KDE算法的开山之作，提到的和想努力解决的问题也很多。本文的KDE模型是核心，如第1小节中描述的；误检抑制，通过领域内的方法，抑制背景的小运动误差，如第2小节中的描述；长短期背景模型，企图解决背景更新快慢的问题，如第3小节所示；使用色度加亮度坐标，企图解决阴影的问题，如第4小节所示。这些方法都是值得学习的。本文方法的实时性，文中说是在400MHz的奔腾CPU，处理320x240的图片能达到15-20 fps，这样的速度可观的，有机会要实现一下本算法。

Python学习笔记--表达式

1. 赋值表达式

赋值表达式有如下几个特点：

• * 复制表达式创建一个引用；在Python中，变量中存储的只是对象的引用，赋值其实就是创建一个变量名到实际对象的一个引用
• * 变量名在第一次赋值的时候将会自动创建，无须声明和定义
• * 变量使用前必须被赋值

由于变量名中没有任何数据类型信息（记住，只是对象的引用），所以可以灵活对变量赋值任何类型的数据：eg：

x = 2 x = 'abc' x = [1,2,3] 在python中，有一种特殊的赋值--upacking assignment解包赋值，eg：

X, Y = 'abc', 'cde'        # tuple

[X, Y] = ['abc', 'abc]    # list

X, Y = 'ab'                  # string 可见，对于Sequence类型对象，都可以使用解包赋值，要求左边的变量数和右边的元素一致。  

Python学习笔记--引用vs复制

Python中，变量的都是默认存储对象的引用，而不是对象本身。例如：

>>> X = [1, 2, 3]

>>> L = ['a', X, 'b'] # Embed references to X's object.

>>> D = {'x':X, 'y':2}

这里X,L,D三个变量中的引用都指向了同一个对象[1,2,3]，在其中任意一个修改，都会影响其他的变量。
有时候我们可能并不希望出现这样的情况，我们可能需要每个变量中都有一个对象的单独拷贝。实现方法如下：

• * 使用无限制的slice来拷贝sequence对象，eg：A = L[:]


• * 对于Dictionary，使用copy函数来实现对象拷贝 eg：B = D.copy()


• * 一些函数也会产生对象的拷贝，例如list


• * 标准库copy可以用来完成完全的拷贝, eg：import copy，然后调用X=copy.deepcopy(Y);
  

值得注意的是，前面的第一二种方法得到的拷贝，都是最高层的拷贝，而并部拷贝嵌套的数据结构，如果要彻底的拷贝，就可以使用最后一种方法，他是递归的拷贝所有的嵌套的对象。

Python学习笔记--TUples,Files

1. Tuples 元组

Tuples其实和List基本一致，都是有序的对象集合，与List不同的是，tuples是immutable的。
Tuples在使用小括号()包围起来的一系列对象。Tuples不支持任何函数
Tuples有如下一些特点：

• * 任意对象的有序集合


• * 通过下表offset存取


• * Immutable


• * 定长，异质，任意嵌套</li
  
• * 对象索引的数组，而不是对象本色

Tuples的一些操作:

T = () #空元组

T = (1, ) # 一个元素的元组，后面要加一个逗号

T = (0, 'Hi', 1.2, 3) # 异质

T = ('ab', ('cd', 'ef')) #嵌套

T[i:j] #slicing

for t in T #迭代

T1 + T2 #连接

由于Tuple不支持任何函数，如果想对Tuple排序，应该怎么做呢？方法如下：

>>> T = ('cc', 'aa', 'dd', 'bb')

>>> tmp = list(T)

>>> tmp.sort( )

>>> tmp

['aa', 'bb', 'cc', 'dd']

>>> T = tuple(tmp)

>>> T

('aa', 'bb', 'cc', 'dd')

这里可以看到使用list()和tuple()函数进行相互转换，值得注意的是，这两个函数都是产生新的对象。

另外，tuple的immutable只是适用于tuple的最上层，如下例子可以说明：

>>> T = (1, [2, 3], 4)

>>> T[1][0] = 'spam' # Works

>>> T

(1, ['spam', 3], 4)

>>> T[1] = 'spam' # Fails

TypeError: object doesn't support item assignment

这里T[1]是一个List，list是mutable的。

2. Files 文件

文件是Python中的特殊的数据对象，此对象关联外部文件，相关函数可以直接对文件进行操作。
File的相关操作如下：

output = open('/dir/filename', 'w')

input = open('data','r') # file may be open as 'w' for write
# 'r' for read or 'a' for append

S = input.read() # 读取文件全部数据到一个字符串中

S = input.read(N) #读取N字节

S = input.readline() #读取下一行，以行结束符号=为标志

L = input.readlines() #读取整个文件到一个字符串的行的列表中

output.write(s) #向文件中写字符串s

output.wirtelines(L) #把列表中L中的所有行写入文件中

output.close() #关闭文件

在Python中，一个对象不再被引用的时候会自动回收内存，在回收file对象的时候，会首先关闭文件。手动close一个文件，虽然不是必须的，但是是一个好的习惯.

Python学习笔记--List和Dictionary

1. List列表 概述

List是Python中最灵活的有序集合类型。List中的元素可以是任何类型：number, string甚至list。List有一下特点：

• * List是任意对象的有序集合


• * 使用下标索引其中的元素


• * 可变长度，异质（list中元素可以是不同类型），内嵌（list of list）


• * mutable，序列的操作都适用（index，slice...）


• * list是引用的集合，而不是对象本身

L = [ ] #空list

L = [1, 2, ‘text’ ] #异质

L = [1, 3, [1, 2] ] #嵌套

L[1], L[1:3], L[i][j], len[L] # index, slice

L1+L2, L * 3 # 链接和复制

for x in L   2 in L

L2.append(4) L2.extend([5,6,7]) L2.sort( ) L2.index(1) L2.reverse( ) # 方法

del L2[k]  del L2[i:j] L2.pop( ) L2[i:j] = [ ] # 删除

L2[i] = 1  L2[i:j] = [4,5,6] # 赋值， mutable

range(4)  range(0, 4) # 产生整数列表

L4 = [x**2 for x in range(5)]  #列表推导式，（现在还不知道是什么意思） 

2. Dictionay字典 概述

如果说列表List是有序对象集合的话，字典就是无序对象集合，他们之间最主要的差别就是，字典通过关键字（key）存取值，而不是offset。

字典有如下特点：

• * 通过Key读取，而不是offset


• * 任意对象的无序集合


• * 可变长度，异质，可任意嵌套


• * Mutable映射表


• * 字典是对象引用的hash表，而不是对象本身

可见Dictionary和List基本是一直，除了全面所说的存取方式。

D = {} #空字典，注意是大括号

D1 = {'spam':2, 'egg':'None'} # 字典元素的定义方法

D2 = {'food':{'ham':1,'egg':2}} # 嵌套定义

D1['spam'] D2['food']['ham'] # 存取方法

D1.has_key('egg'), 'egg' in D1, D2.values(), ... # Dictionary相关的方法

D3 = dict(zip(keyslist, valuslist)) #Dictionary的构建（我现在还不清除这种用法）

由于Dictionary不是一个序列，所以不能直接使用迭代，要使用迭代的话，可以如下：
for item in D.keys():

Dictionary使用注意：

• * Dictionary是Mapping，而不是Sequence,在Dictonary中的各元素没有先后的顺序关系，所以对于Sequence的操作对Dictonary都不使用。如：连接，分片索引（slicing）


• * 对Dictionary的新的key赋值，就是增加一个新的元素。对已有的key赋值就是修改此元素


• * Dictionary的key不一定要是字符串string，其实任意不可变（immutable）的对象都可以，例如整数等

Python学习笔记--string 字符串

1. 字符串的定义

可以使用单引号（' '），双引号（" "）：这两个表示的方式完全等价。

还可以使用三引号（单双引号都可以），可以进行多行的字符串的定义。

Raw字符串，即完全原样字符串，不经心转义，eg：r'c:\py\text'

Unicode字符串，多字节字符串， eg：u'text'，u'ab\u0020cd'

Unicode --> normal：str(u"text")

normal --> Unicode：unicode("text")

2. 字符串操作

加法+：字符串的连接，'abc'+'def'

乘法*：字符串重复，'Hi!' * 3

求字符串的长度len()

字符串循环索引：

            ss = 'Hello'

            for c in ss: print c,  # H e l l o

            "H" in ss  # 1 or true

            "z" in ss   # 0 or false

字符串索引和分块：

           ss[0]  # 'H'

           ss[-2] # 'l'

           ss[1:3] #'el'

           ss[:-1]  #'Hell'

           ss[m:n], m和n可以缺省，m缺省为0, n缺省为ss的长度

           ss[start: end: step], eg, ss[1:5:2], ss[ : :-1]

字符串转换工具：

           不能直接把数值和字符串（即使这个字符串很像一个数字）使用加号“+”连接，因为加号“+”可能是表示字符串连接，也可能表示数值加法，所以Python就把这种情况视为语法错误。

           string--> number: eg. int("42"), float("1.23E-10"), string.atoi("42")

           number-->string:  eg. str(42), `42`, 这里的运算符backquotes(`object`),把之间的对象object转换成字符串。

           eval 函数用来执行Python代码。

改变字符串：

          首先要注意，字符串是不可改变的--immutale: can't chang in-place。所以要改变字符串，其实就是要使用相应的上述操作创造一个新的字符串。

          eg. ss='spam' ;  ss[0]='A' 将触发错误。

3. 字符串格式化

Python在string中重载了%运算符，这里类似了C语言中的sprintf函数中%的作用，占位符，eg：

>>> exclamation = "Ni" 

>>> "The knights who say %s!" % exclamation 

'The knights who say Ni!' 

这里使用exclamation变量替换了左边字符串中的%s

 >>> "%d %s %d you" % (1, 'spam', 4) 

'1 spam 4 you' 

如果是多个变量的时候，要使用小括号包围起来，形成一个元组tuple

 >>> "%s -- %s -- %s" % (42, 3.14159, [1, 2, 3]) 

'42 -- 3.14159 -- [1, 2, 3]'

这里把int，float，array类型的数据自动转换成string类型

读“Real-time Background Subtraction in C++”

这篇文章的作者Haotian Wu, Yifan Yu，在Boston大学的技术报告，忘记这篇文章是在哪里下来的了，不知道是否出自什么会议，或者是一个学习总结类型的文章，不过附有源代码，所以认真看了一下。

本文的重点是想实现实时的背景差分，在算法的效率方面的讨论比较多，这不是我所关注的地方，但是他在这篇文章中提到的背景差分模型还是值得借鉴的。

1  单高斯模型 
对每个像素点建立一个高斯模型，是最简单的背景差分模型，此算法的效率很高，运行速度非常快，但是差分效果不太好。

2 Kernel Density Estimation 核密度估计
此方法的核心使用使用统计的方法，估计最近n帧的图像中的像素值，来确定当前像素点是否是前景。

把最近的n帧或者按照一定规律取n帧存入缓存（Buffer）中作为核 (未完成)