2014年7月31日星期四

WinDbg符号表设置的基础

  现在正在学windbg,记录一些基本的知识。

每次调试开始都会新开始一个workspace,其实就是跟工程差不多,记录了你这次调试的配置。当然有一个默认workspace,当你没有调试的时候。感觉最重要的就是设置符号表,每次都得弄好,要不然符号看不了的,设置如下.sympath srv*d:\symbols*http://msdl.microsoft.com/download/symbols,如果后面不跟参数,那就是显示整个符号表目录设置。还有就是装载符号(ld 模块名),强制重新装载(.reload)。

STL map使用注意

在一家公司实习,遇到一个任务需要使用到stl的map , 这个容器的实现了字典的功能,由于key 为自定义类型,其实就是有两个元素的数组,这样stl就让你提供一个比较函数,实现<比较。STL的描述是这个运算符必须满足strict weak ordering 。具体的特性用离散数学的说法就是,反自反,反对称,传递的关系,如果不能实现这样的关系,那么存储元素的时候就会产生各种奇怪的错误,最普遍的就是元素重复。发现问题才想起这点的,长了点记性。

python处理文件编码

对于存储自然语言的文件,有可能采用了不同的编码,例如汉字的编码就有多种,UTF-8,GB2312,GB18030,ISO-8859等字符编码格式。当处理各种文件的时候,就需要在各种文件格式之间转换,由于UTF-8字符编码格式兼容于ASCII,且多字节编码,不存在大小端的问题,可以使用已有的C语言库字符串处理函数,处理起来较为方便。现在来看看将其他格式(GB2312,GB18030)转换成UTF-8。

  使用python处理文件格式转换,需要使用codecs模块。使用是,先import codecs 。在codecs可以使用open,lookup函数来打开文件。open(filename,mode,encoding,errors,buffering),需要给出filename,mode和encoding,其余的参数有默认值,不用管的。encoding就是要打开的文件的字符编码方式。当从文件读出的内容使用的就是python的内部标示,即unicode标示法。lookup(encoding),返回一个CodecInfo类的实例,encoding是字符编码名称,('utf-8','gb2312')。

  lookup返回值含有相当多的内容,实例中的encode,decode,用来进行格式转换。encode用于将内部的UCS-4转换成调用lookup是给出的encoding格式。decode用于将调用lookup的encoding格式的字符串转换成UCS-4格式的字符串。

  lookup返回的实例中可以使用streamreader,streamwriter两个类,明显reader,writer都是用于按照encoding来读取和写入相应的文件,参数就是一个file-like的对象了。reader是按照encoding从stream读入数据,返回的是unicode字符串。writer将unicode字符串转换成encoding格式写入stream。必须获取streamreader类得一个实例,例如a= x.streamreader(file-object) ,然后就可以使用a来完成相应的读功能。

  在codecs模块中,还有decode和encode两个函数,decode(obj,encoding),这个函数的作用就是将按照encoding编码的obj转换成unicode。encode(obj,encoding),这个函数的作用就是将按照ucs-4编码的obj转换成encoding格式。

  事实上codecs也提供了一些方便的函数,例如'utf_32_be_decode', 'utf_32_be_encode', 'utf_32_decode', 'utf_32_encode', 'utf_32_ex_decode',等等。可以使用严格的decode,encode来完成相同的功能。

python的命令行解析模块

在命令行模式下每个程序都有输入和输出参数需要指定,可以使用各种方式来完成这点,比如将特定位置的命令行输入解释为特定输入或者输出参数,例如argv[1]为输入文件的名字,argv[2]为输出文件的名字,在这种情况下第几个参数的作用已经被指定,一般来说不利于程序的修改和扩展,如果要增加新的输入或者输出,有可能要对某个位置对应的参数进行重新指定,这是很不方便的。第二种方法就是使用命令行参数来获得相应的输入和输出。如果使用这种方法,在命令行下启动程序时的输入可能如下: ./program build --long-foo t  -short-foo x, 这里使用两个“-”符号的命令行参数成为“长格式”的命令行参数,使用一个"-"符号的成为“短格式“的命令行参数,无论是“长格式”的命令行参数还是“短格式”的命令行参数,都可以归为一类,称之为可选的参数,意思就是可以提供也可以不提供的参数,第一个“build”代表另一类命令行参数,表示那些程序启动时必须的参数,如果忽略则程序不应该启动,这类参数称为位置参数。使用多个这类参数的效果类似于我们初始的想法,即将固定位置的命令行参数解释为特定输入参数。但是差异仍然是有的,如果既有可选参数,也有位置参数,那么可选参数和位置参数的位置以任意的顺序出现,只要位置参数出现即可,但是位置参数的相对顺序是不能改变的,因为位置参数就是靠相对位置来解释对应参数的意义的。python中的argparse库完全实现了这些功能,并且在python2.7中成为内置模块,其他更低版本的python可以使用相应的库文件来安装。

使用的方式如下:1.  import argparse; 2. 创建一个命令行解释器,使用argparse模块中的ArgumentParser函数来创建,例如: parser=argparse.ArgumentParser( ... ) 3. 在解释器中添加相应的命令行选项,例如: parser.add_argument( ... )  4. 调用解释器的函数,获取解析的结果。例如: ret = parser.parse_args( ... )。 下面重点解释第三步的操作。( "..."表示需要相应的参数 )

ArgumentParser.add_argumentname or flags... [, action][, nargs][, const][, default][, type][, choices][, required][, help][, metavar][, dest]),这个函数用于添加相应需要解析的命令选项。name or falgs必须为一个字符串,它的格式即决定了是使用”长格式“参数,”短格式“参数还是位置参数。假如创建一个长格式的参数,可以使用如下方式调用 parser.add_argument("--foo");如果是短格式,则调用方式为 parser.add_argument("-foo");可以看到唯一的差异在于”-“符号的个数,但是一般来说”长格式“的参数较长,而”短格式“则只有一个字符。创建位置参数可以使用如下方式: parser.add_argument("foo")。有这样一个规则:所有不以”-“开头的参数都假定为位置参数,不同的位置参数如何解析取决于他们在整个位置参数序列中的相对位置,而整个位置参数的相对顺序是由添加位置参数时确定的。action参数表明当解析到这个命令行参数时需要进行何种操作。有”store“:存储命令行参数的值;”store_const":存储[const]选项的值,“store_true” or “store_false”:存储True或者False;“append”:将这个参数值添加到一个列表中,适用于适用于多次出现的命令行参数;“append_const”:将一个固定值存储到列表中。[nargs]用于指定这个命令行参数有多少个值,可以是1,3,100等确定的值,也可以是“*”,“+”,“?”等字符串。“*”,“+”,“?”跟他们在正则表达式中的含义是一样的,“*”,“?”表示这个命令行参数可以不指定值,如果没有值,但是这个选项出现在命令行中,那么这个选项的值有[const]参数决定,如果连这个命令行选项都没有出现,那么这个选项的值有[default]参数决定。[type]表示参数的类型,可以是float,int,file等中的任一个。[choice]表示这个命令行参数的取值只能为[choice]给定集合中的一个。[required]如果为True则表示这个命令行选项必须出现,这样可以要求一个可选参数必须指定一个值。[help]是帮助信息,[metavar]指定在显示帮助时,指代这个选项的名称。[dest]表示如何从结果中引用一个值。

字符串匹配的kmp算法

        字符串匹配有很多算法,最简单的算法就是从模式P的开头(j=0)和主串S的某个位置开始进行比较(i),如果相等(p[j] == s[i]),则比较模式串的下一个位置和主串的下一个位置(++j;++i), 如果不相等(p[j] != s[i]),则要发生回溯,从主串的位置i-j重新开始匹配,这样速度会收到影响( i = i-j+1; j=0 )。

        KMP算法的优势即在于避免了回溯,当模式串j和主串i位置的字符不匹配时,查询一个数组next,从模式串位置p[ next[j] ]开始和主串的i位置开始匹配,这样主串就没有回溯,速度也就加快了,那么如何计算next数组呢?

        首先对next数组的功能进行介绍,next数组的目的是对模式串的每一个位置i存储一个值j当模式串中位置j的字符和主串位置i字符不匹配时,应该从模式串中的另一个位置next[j]重新和主串的当前位置i开始比较,next数组的计算方法可以保证,next[j] < j, 所以从另外一个意义解释就是寻找一个模式前缀p[0, ..., next[j]-1 ]和模式后缀p[ i-next[j], ..., i -1 ]相匹配。因为模式p[j]和主串s[i]不匹配,意味着模式串p[0, .., j-1]和主串s[i-j, ..., i-1]是匹配的,改变j,使得j=next[j], 并从p[next[j]]这个位置和主串i开始匹配,必然有上面的要求。而且可以看到next数据的计算只跟模式串有关。那么,为什么这样做是可以的呢?会不会漏掉可能的匹配呢?答案当然是不会的。

        下面开始解释这个问题,当模式串位置j和主串的当前位置i不匹配时,很明显模式串j之前的字符串(即p[0 ... i-1])和主串的当前位置之前的字符串(即m[ i-j ... i-1)是匹配的,假如在某个情况下,存在一个模式子串p[ k, .., t] ( k > j-i+1 )和主串p[ u, .., i]匹配,那么这就是相当于模式串p[ 0 ... i-1 ]存在一个前缀和模式串的一个后缀匹配,这跟计算next数组的初始想法完全是一样的,可见不会丢掉任何可能的字符串匹配。

        那么如何计算next数组呢?next数组的内容可以递推的求解,如果我们已经知道next[i]数组的值,那么就可以求得next[i+1]的值。因为求解next[i+1]就是求解一个前缀p[0, ..., next[i+1]-1],使得p[0, ..., next[i+1]-1]p[i+1-next[i+1], ..., i]匹配。而且我们现在已经知道p[0, ..., next[i]-1]p[i+1-next[i], ..., i]匹配。如果此时p[i] == p[next[i]],那么next[i+1]=next[i]+1,此时即可满足条件。如果p[i] != p[next[i]],问题即变成求解next[next[i]]。

有如下代码变量i:用于指示模式串需要计算的位置,j:用于存储前一个的next值。代码如下: 

int i = 0, j = -1;

while( i < n ){
    if( -1 == j || t[i] == t[j] ){
        ++i; ++j;
        next[i] = j;
    } else 
        j = next[j];

}

字符编码小结

首先需要记住一件事情,那就是计算机中存储的一定是二进制数,是浮点,有符号数,还是无符号数或者是代码完全取决于你如何处理这些二进制,即运算规则。这里只是关心这些二进制数跟文字之间的关系,也就是不同的二进制数如何映射到文字的,或者反过来。

有一个术语用来表示不同的文字和二进制数之间的关系:字符编码。简单的来说字符编码就是把一堆文字映射到一堆数字的标准。这也就是说同样一个二进制数在不同的字符编码中就表示不同的数字。例如对于汉字就有GB2312,GBK,GB18030,GB13000,BIG5等等,所有这些编码方法都是用于在计算机中存储汉字,如果文件使用的编码和计算机解释用的编码不一样,那就形成了“乱码”现象。 在汉字的编码中GB2312最先出现,然后依次出现GBK,GB18030,GB13000,后面的编码对前面的编码兼容,也就是说同一个汉字的二进制数是一样的。BIG5是台湾、香港等地使用的字符编码,和其他的字符编码是不兼容的,同时GB18030兼容GBK、GB2312编码,但是GB13000好像就是Unicode的标准,和其他的其他的字符编码是不兼容的。现在考虑另外一个事情:windows和linux的locale。简单的来说locale就是用本地的方式来显示一些信息,一般来说是时间和货币单位等等,当然也包括文字,这是很大的不同。所以locale中的字符编码决定了默认使用什么字符编码来对文件中的信息进行解码,如果相同或者兼容还好,不同的话肯定就乱码了。

但是随着Unicode的出现,这个问题以另一种方式被解决了:使用同一个字符集,这个字符集包含了所有语言的所有文字,所以大家就不同担心了。但是新的问题又出现了。Unicode为每个字符分配了一个码位,可以认为是逻辑上的一个二进制数,但是如何在现实中表示则有不同的方法。明显一个字节只有8位,所有当二进制数的位数大于8时,必然要使用超过一个字节来表示,这些不同的字节之间存在什么关系呢?这就是UTF-8,UTF-16,UTF-32。UTF-8兼容ASCII,使用变长编码,这就意味着可以使用C的库函数来处理UTF-8。UTF-8对于C语言来说不过是一堆比较怪异的ASCII而已。UTF-16使用双字节,不同表示全部的Unicode字符,而且还有大端、小端的区别。在文件的前两个字节中(0xEE,0xFF)的不同排列所显示出来。 UTF-32,使用四个字节,可以完全表示UCS,但是用的很少。如果现在所有的文件都使用UTF-8或者UTF-16,那么世界上很多问题就没了(很明显不是)。所以经常需要做字符编码之间的转码,可以使用iconv来完成这个操作,使用file命令获取文件的原始编码。如果从小的字符集向大的字符集转,没有任何问题,如果从大的字符集向小的字符集转,有些字符无法表示,就转换失败了。对于汉字还有另外一个特殊的情况。使用file对使用GB2312,GBK,GB18030编码的汉字文件进行探测时,返回的是ISO-8859这个编码,这个时候可以直接按照GB18030解码(对于其他编码是兼容的),可 以获得正确的结果!

emacs键盘映射

在emacs中我们可以将一个交互式的命令绑定到一个按键序列中。比如C-x C-f就绑定了命令find-file,而一般的字母和数字则绑定到了self-insert命令。使用这一个方式我们就可以做很灵活的绑定,让那些我们经常使用的命令绑定到非常方便的key sequence上面。这种命令绑定是通过key-map数据结构实现的。但是我们知道在emacs之中存在不同的major mode和minor mode,而且不同key-sequence的长度也不相同,那么这些因素对键盘绑定有什么影响呢?

1. 存在不同major mode和minor mode对命令绑定的影响 

 一个很明显的需求就是同样的key sequence在不同的major mode和minor mode中绑定不同的命令。这样就产生了一个全局key-map和局部key-map的需求,全局key-map只有一个,但是不同的major mode 和 minor mode都有一个自己的key-map。当你编辑的文件处于某个major-mode,并启用了一些minor-mode时,只有相关的minor-mode key-map,major-mode key-map和global key-map是可以影响到key-sequence的解释的。当需要给出一个key-sequence所绑定的命令时,首先搜索minor-mode的key-map,然后是major-mode的key-map,最后是global-key-map;当在前一个key-map中找不到时,才会到后一个key-map中寻找。当需要定义全局的key-map时可以使用global-set-key这个函数,如果需要定义局部key-map,使用local-set-key。

2. key-sequence长度对键盘映射的影响

 有些键盘操作只需一次即可完成某个命令,比如C-f,C-b;但是另外一些则需要多次的按键,比如打开文件的命令C-x C-f就需要两个键盘操作。一个key-map数据结构只能对一个按键操作映射,因此需要多个键盘操作的命令需要多个key-map,而且第一个键盘操作绑定的不是一个命令,而是另外一个key-map,后面的按键就是根据这个key-map来找到要绑定对象。对于C-x C-f操作,定义了一个global key-map,将C-x绑定到ctl-x-map中,注意这个ctl-x-map并不是一个可执行的emacs函数,而是一个key-map,在这个key-map里面,C-f绑定到了命令find-file,因此按下C-x C-f这个key-sequence时,有两个key-map,而且涉及到了两个绑定。这里C-x就被叫做prefix-key,这里的意思就是这个key只是命令的前缀,但是具体的是那个命令还需要继续给出其他的key才可以。

在emacs中定义了很多这样的prefix-key,比如C-x,Esc,C-x 4,C-x 5,M-g,C-c等等,每一个prefix-key都绑定到一个key-map上面。在相应的key-map用于解释紧接着prefix-key的绑定,这样一直循环下去,直到最后一个key-map将一个key绑定到一个命令上,输入完成之后就执行。

那么global key-map,local key-map跟这些prefix-key绑定到的key-map有什么区别和联系吗?首先这些都是key-map数据结构,作用都是为了完成键的映射。不同的major mode和minor mode都有自己的local key-map,global key-map则只有一个。可以在local key-map里创建prefix-key,也可以在global key-map里创建prefix-key。(note!prefix-key所绑定的是一个key-map,但是prefix-key同样也是一个key,也必须在某个local key-map或者global key-map里创建才行)。

3. 如何创建prefix-key

简单一个函数(define-prefix-command 'key-map-name),然后绑定键值到新建的key-map就可以了。加入我们想把C-r C-t C-z a绑定到find-file命令。a. (define-prefix-command 'ctl-r-map); (local-set-key (kbd "C-r") 'ctl-r-map); (local-set-key (kbd "C-r C-t C-z a") 'find-file);这样就可以使用C-r C-t C-z a来打开文件了。但是在这里需要说明几点a. 如果已经存在相应的prefix-key定义,不需要重新重新创建,如果不存在,那么必须首先创建prefix-key  b. 可以看到C-r C-t也是一个prefix-key,C-r C-t C-z也是prefix-key,这些都是emacs自动创建的,当我们也可以自己动手。所以对于一连串的key sequence,只需要对第一个key创建prefix-key就可以了。

英语拼写检查

英语单词拼写检查是word提供的一个功能,使用google的时候也可以看到,当你打错字了,会给你提供一个备选。也就是给定一个词c,你应该提供一个候选的词w,这个词w应该是c因为打错一个字而产生的。即表述为 argmax p(w|c). 利用贝叶斯定理即转换为 argmax p(c|w)p(w)/p(c) = argmax p(c|w)p(w). 挑选出词w由两个公式来描述,一个是p(w):这是词w的概率,可以称之为语言模型,一个是p(c|w):是词w产生词c的概率,可以称之为错误模型。

p(w):语言模型,用于描述一个词w在整个语言中的分布概率,如果出现多个词则可以称之为n-gram语言模型,即一定长度的多个词在语言中的分布概率。可以通过统计一个大型语料获取,但是语言模型存在的一个问题是一个单一的语料库中词语的分布个实际的词语分布之间可能存在差异,因此这样的概率不一定可靠,而且对于OOV还需要进行平滑。

p(c|w):错误模型,即词语w转换成词语c的概率,对于一个大小为N的词表中的每个词,都存在这样的一个条件概率。但是一般来说只是对特定的词才有大于0的值,其他的词全部为0.如果有一个专业的统计信息,那么可以直接计算一个词转换成另一个词的概率,也可以通过其他方法来衡量,比如两个词的编辑距离,两个词中字母交集的大小,甚至是两个词的最长公共子串等等。 

有了上面两个概率分布,就一个进行错误纠正了,但是要对词表中的每个词都进行这样的操作,这样速度就很慢。一个改进就是先根据编辑距离由c找出一些候选词,再从候选词之中挑选出最后可能的词,提高了效率,也有可能直接排除了正确的答案。比如直接根据编辑距离,挑选出所有跟c的编辑距离小于等于2的词w,然后再用贝叶斯的方法从这些候选词之中挑选出最有可能的词Wopt。

 

ps:一个词跟另个一个词的编辑距离定义为使用不同编辑操作的次数,编辑操作包括插入,删除,替换,交换四种。 

1 def edits1(word):

2    splits     = [(word[:i], word[i:]) for i in range(len(word) + 1)]
3    deletes    = [a + b[1:] for a, b in splits if b]
4    transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1]
5    replaces   = [a + c + b[1:] for a, b in splits for c in alphabet if b]
6    inserts    = [a + c + b     for a, b in splits for c in alphabet]

7    return set(deletes + transposes + replaces + inserts) 

这是一段很神奇的代码,我很喜欢,想法太神了!!!

产生编辑距离为2的代码:

1 def known_edits2(word):

2     return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS) 

在这里NWORDS代表当前已经出现的词,除此之外的词都是未登录词。

 

上述内容可以在:http://norvig.com/spell-correct.html 中发现!

下面又出现另外一个问题,对有些语言来说不存在这种拼写检查,比如汉语。这里所需要的不是一个词拼写检查,而是类似于词组的拼写检查,比如我输入“搜索殷勤”,这个时候谷歌给出的提示是“搜索引擎” 这个词,明显的在一般情况下这样的提示是很友好的。在这里也可以引入贝叶斯公式的方法来处理,对于一个可能的候选词组w,挑选出最大概率的一个,既 argmax p(w|c),可以直接转换为 argmax p(w)p(w|c),但是这里p(w)用的应该是n-gram文法模型, p(w|c)可以考虑使用编辑距离来作为度量,即计算w和c之间的编辑距离。这里产生候选词组w的方法可以直接使用单个词的操作,对于“搜索引擎”这个词语来说,可以产生“搜引擎”,“索引擎”,等等,但是这样的候选在一般情况是没有意义的,对于“搜索引擎”这样的词,在分词的角度来看是一个combination,即可以划分成两个词“搜索”和“引擎”也可以直接当做一个词来用,在候选词w时,可以考虑划分成更细的力度,然后替换其中的一个词,产生新的候选词,但是这样会形成很多的候选,毫无效率。。。。。。

对上面方法的一个改进就是直接使用n-gram语言模型, 挑选出“搜索”这个词之后,长度为2的候选中,最后可能的两个即 argmax p(w1 w2|搜索) = argmax p(搜索w1 w2)/p(搜索)。但是这样需要挑选的词来说并没有多少变化。所以最后这个问题就演化成计算不同长度串中,最有可能的一个!

面试题总结

1. 求一个矩阵中最大的二维矩阵(元素和最大) (solved)

思路类似于一维数据中求最大和的问题。。。。 


2.无向图中挂接点的计算 (solved)

使用dfs算法,关键在于low(w)是以w为根的子树中所有定点的最小值,或者是反向边的最小值。

http://www.ibluemojo.com/school/articul_algorithm.html

附加的还有强连通子图,无向图中桥的计算,使用的都是基于DFS的方法。 


3.     微软的链表系列题目(solved)

  a. 判断一个链表是否有环?用两个指针,一个步进为1,一个步进为2,若有环,必相交!

  b. 判断链表是否相交?

  c. 找到链表相交的节点



4.     写出第1500个丑数~ (solved)



5.     求两个串中的第一个最长子串(suffix tree, solved)

 

6.     1024!的末尾有多少0?(solved)

  2*5=10,所以取决于2,5因子的个数



7.  有6种不同颜色的球,分别记为1,2,3,4,5,6,每种球有无数个。现在取5个球,求在以下的条件下:

     1、5种不同颜色

     2、4种不同颜色的球

     3、3种不同颜色的球

     4、2种不同颜色的球

它们的概率。


8.      题目大意如下:

一排N(最大1M)个正整数+1递增,乱序排列,第一个不是最小的,把它换成-1,
最小数为a且未知求第一个被-1替换掉的数原来的值,并分析算法复杂度。(solved)

9.  歌德巴赫猜想说任何一个不小于6的偶数都可以分解为两个奇素数之和。

对此问题扩展,如果一个整数能够表示成两个或多个素数之和,则得到一个素数和分解式。

对于一个给定的整数,输出所有这种素数和分解式。
注意,对于同构的分解只输出一次(比如5只有一个分解2 + 3,而3 + 2是2 + 3的同构分解式

)。

例如,对于整数8,可以作为如下三种分解:
(1) 8 = 2 + 2 + 2 + 2
(2) 8 = 2 + 3 + 3
(3) 8 = 3 + 5

注意,素数属于集合(i,end)


10.   输入a1,a2,...,an,b1,b2,...,bn, 
  在O(n)的时间,O(1)的空间将这个序列顺序改为a1,b1,a2,b2,a3,b3,...,an,bn,
  且不需要移动,通过交换完成,只需一个交换空间。 

解法:交叉换位,以2的次幂增加移动块的大小 


11.     创新工场面试题:abcde五人打渔,打完睡觉,a先醒来,扔掉1条鱼,把剩下的分成5分,拿一份走了;b再醒来,也扔掉1条,把剩下的分成5份,拿一份走了;然后cde都按上面的方法取鱼。问他们一共打了多少条鱼(solved)

 

12.     搜狗笔试题:一个长度为n的数组a[0],a[1],...,a[n-1]。现在更新数组的名个元素,即a[0]变为a[1]到a[n-1]的积,a[1]变为a[0]和a[2]到a[n-1]的积,...,a[n-1]为a[0]到a[n-2]的积(就是除掉当前元素,其他所有元素的积)。程序要求:具有线性复杂度,且不能使用除法运算符 (solved)

解法是用两个数组,分别存储两个方向的乘积!

 

13.     腾讯面试题:给你5个球,每个球被抽到的可能性为30、50、20、40、10,设计一个随机算法,该算法的输出结果为本次执行的结果。输出A,B,C,D,E即可。(solved)


14.     有无序的实数列V[N],要求求里面大小相邻的实数的差的最大值,关键是要求线性空间和线性时间 (solved)

 线性时间排序:要不计数,要么桶!

 其实这个问题要求线性时间条件下,通常会让我们想到桶排序;接着关键是考虑怎么减少桶排序中对桶中各数的排序即可想到解决方法。我的算法如下:

  1. 主要是先找出最大的数与最小的数,然后构造一个n个桶,桶的下标与数的关系为: index = (v[i]-min)/(max-min/n).
  2. 遍历数列,将数值插入到对应的桶中。每个桶最多保留最小和最大的两个元素,不需要多余的数。
  3. 遍历所有的桶,记录每个桶之间有多少个空桶到数据flags中,并求出最大连续空桶数 maxGap。
  4. 最后遍历flags数组,对于空桶数 >= maxGap -1 的元素,计算从前面的最近的不为空的桶中的大元素与当前桶中的最小元素的差,最终找出最大差

 


15.     25匹赛马,5个跑道,也就是说每次有5匹马可以同时比赛。问最少比赛多少次可以知道跑得最快的5匹马 (solved)


16.     Alibaba笔试题:给定一段产品的英文描述,包含M个英文字母,每个英文单词以空格分隔,无其他标点符号;再给定N个英文单词关键字,请说明思路并编程实现方法

    String extractSummary(String description,String[] key words)

目标是找出此产品描述中包含N个关键字(每个关键词至少出现一次)的长度最短的子串,作为产品简介输出。(不限编程语言)20分。(扫描过程始终保持一个[left,right]的range,初始化确保[left,right]的range里包含所有关键字则停止。然后每次迭代:

     a.     试图右移动left,停止条件为再移动将导致无法包含所有关键字。

     b.     比较当前range's length和best length,更新最优值。

     c.     右移right,停止条件为使任意一个关键字的计数+1。

     d.     重复迭代。 (solved) 

 

 17.     阿里云笔试题:一个HTTP服务器处理一次请求需要500毫秒,请问这个服务器如何每秒处理100个请求


18.     输入两个整数A和B,输出所有A和B之间满足指定条件的数的个数。指定条件:假设C=8675在A跟B之间,若(8+6+7+5)/ 4 > 7,则计一个,否则不计。要求时间复杂度:log(A)+log(B)  <unsolved>


19.     旅行商问题 <unsolved>


20.如何利用一个能够返回[0,1]平均随机点的函数,等概率地生成一个单位圆中的点,使得生成地点在圆内的分布概率尽量平均,即在面积上平均分布。

  1. 随机产生[0, 360]上的一个角度θ
  2. 随机产生 [0, r^2] 上的一个半径的平方 r^2,

这个点(θ, r)就是一个随机的圆上的点

21.     为分析用户行为,系统常需存储用户的一些query,但因query非常多,故系统不能全存,设系统每天只存m个query,现设计一个算法,对用户请求的query进行随机选择m个,请给一个方案,使得每个query被抽中的概率相等,并分析之,注意:不到最后一刻,并不知用户的总请求量。( solved)

 

22.     四个线程t1,t2,t3,t4,向4个文件中写入数据,t1只能写入1,t2只能写入2,t3只能写入3,t4只能写入4,对4个文件A,B,C,D写入如下内容
A:123412341234.....
B:234123412341....
C:341234123412....
D:412341234123....
怎么实现同步可以让线程并行工作?

23.     12个工厂分布在一条东西向高速公路的两侧,工厂距离公路最西端的距离分别是0、4、5、10、12、18、27、30、31、38、39、47.在这12个工厂中选取3个原料供应厂,使得剩余工厂到最近的原料供应厂距离之和最短,问应该选哪三个厂 ? 


24.     平均要取多少个(0,1)中的随机数才能让和超过1(e)<solved>


25.     用两个栈实现一个队列!

 


class List{

  private:

  Stack a,b;

  List::push(_a){

    b.push(_a);

  }


  List::pop(){

    if(a.empty()){

      while(!b.empty()){

        a.push(b.pop())

      }

    }

  }

  return a.pop()

};

因此最好是让一个栈用来压入,另一个用来弹出!!! 

 

26.     假设你有一个用1001个整数组成的数组,这些整数是任意排列的,但是你知道所有的整数都在1到1000(包括1000)之间。此外,除一个数字出现两次外,其他所有数字只出现一次。假设你只能对这个数组做一次处理,用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式,那么你能找到不用这种方式的算法吗? <solved>

a. 对数组求和,再减去(1+1000)*1000/2,即为多出来的数。

b.  使用异或方法!!!

// a ^ a ^ b = b


//1001个介于1、1000之间的整数,再加上下标,正好有一个数字出现三次,其余出现两次,妙

int find( int a[], int size){

        int k=a[0];

        for(int i=1; i<=1000; ++i){

                k ~= a[i] ~ i;

        }

        return k;

}



27.     (solved)写一个函数,交换两个参数,要求不使用临时变量

这是一个老题目了,大概有三种解法:

  • 异或(比较完美)?
  • void exchange(int &a, int &b) {    a = a ^ b;    b = a ^ b;    a = a ^ b;}

  • 加减(容易溢出)?
  • void exchange(int &a, int &b) {    a = a + b;    b = a - b;    a = a - b;}

  • 乘除(超级容易溢出)?
  • void exchange(int &a, int &b) {    a = a * b;    b = a / b;    a = a / b;}
    2、不用判断,不用循环,不用乘除法,不用?:,不用switch,求1+2+…+n(n为参数)

不能用乘法,所以就不能用等差数列的公式n*(n+1)/2了,不能用循环,那么迭代的算法就不能用了。那么我就想到了递归,但是递归要有判断条件,而我们的题目不让永判断语句(包括?:),那怎么办呢?

  • &&(考虑到&&的截断性,隐式的判断)?
  • int sum(int n) {    int r = 0;    n && (r = n + sum(n - 1));    return r;}

  • ||(考虑到||的阶段性,隐式判断)?
  • int sum(int n) {    int r = 0;    !n || (r = n + sum(n - 1));    return r;}

  • 利用类的构造函数(缺点:浪费空间)?
  • 1
    2
    3
    4
  • class sum_helper {private:    static int s;    static int n;public:    sum_helper() {        s += n++;    }    static int get_sum() {        return s;    }    static void reset() {        s = 0;        n = 1;    }};
     
    int sum_helper::s = 0;int sum_helper::n = 1;
     
    int sum2(int n) {    sum_helper::reset();    delete[] (new sum_helper[n]);    return sum_helper::get_sum();}

  • n写成二进制的形式,101010....0,那么n ^ 2, 则可以写成n( ai * 2^i + ... + aj * 2 ^ j + ... ), 1 + 2 + ... + n = n(n+1)/2 = (n^2 + n)/2; #define T(X, Y, i) ( ( Y & 1 << i) && (X += Y << i)) ;  r= n; T(r, n, 0); T(r, n,1); .... T(r, n, 31);

3、不用循环判断一个数是否是2的整数冪

考虑2^k与2^k-1的二进制特点,2^k的二进制中只有第k(从0开始)位是1,其余是0,那么2^k-1呢?0…k-1为1,其余位为0,所以判断方法很简单了:

判断n&(n-1)是否为0,为0说明是2的整数冪,否则不是

问题扩展:判断一个数是否是4的整数冪,扩展的问题可以分成判断这个数是不是2的整数冪+判断这个数是不是完全平方数

判断一个数是否是是完全平方数,考虑1+3+…+(2n-1)=n^2,所以我们就可以将这个数减去1,3…知道小于或等于0,如果最终结果是0,那么就是完全平方数,否则不是

 4、求1^2+2^3+…+n^2,要求不用循环,不用判断

记得以前学过一个公式吧:1^2+2^3+…+n^2=n(n+1)(2n+1)/6

 5、找出两个数种较大的一个,要求不用比较运算

int getMax(int a, int b) {

?

1

2

3

4

5

    int c = a - b;

    int k = (c >> 31) & 0x1;

    int max = a - k * c;

    return max;

}

28.     约瑟夫环问题

我们知道第一个人编号一定是(m - 1)%n, 出列之后,剩下的n-1个人组成了一个新的约瑟夫环(以编号为k=m%n的人开始):    

k   k+1   k+2   ... n-2, n-1, 0, 1, 2, ... k-2 并且从k开始报0。 现在我们把他们的编号做一下转换: k      --> 0 k+1    --> 1 k+2    --> 2 ... ... k-2    --> n-2 k-1    --> n-1 变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:例如x是最终的胜利者,那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗?!!变回去的公式很简单,相信大家都可以推出来:x'=(x+k)%n (x' 为n个人报数的解) 如何知道(n-1)个人报数的问题的解?对,只要知道(n-2)个人的解就行了。(n-2)个人的解呢?当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题!好了,思路出来了,下面写递推公式: 令f[i]表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n] 递推公式 f[1]=0; f[i]=(f[i-1]+m)%i;   (i>1) 有了这个公式,我们要做的就是从1-n顺序算出f[i]的数值,最后结果是f[n]。因为实际生活中编号总是从1开始,我们输出f[n]+1 

 

 29.     题目:输入一个正数n,输出所有和为n连续正数序列。(直接计算出i和j, <solved> )

( i + ... +j = (j-i+1)*(i+j)/2 == n )



30.     平面上N个点,每两个点都确定一条直线,求出斜率最大的那条直线所通过的两个点(斜率不存在的情况不考虑)。时间效率越高越好。


31.     有5个海盗,按照等级从5到1排列,最大的海盗有权提议他们如何分享100枚金币。但其他人要对此表决,如果多数反对,那他就会被杀死。他应该提出怎样的方案,既让自己拿到尽可能多的金币又不会被杀死?


32.  请定义一个宏,比较两个数a、b的大小,不能使用大于、小于、if语句

答案如下: #define Max(a,b) (a==b)?e:(((a-b)|1<<31)==(a-b)?b:a)  

1<<31   : 00000000000001左移31位至最高位,变为1000000000000000000000,而(a-b)可能是正数或者负数或者0,规定:有符号型数据储存在内存中时,最高一位用来储存符号,剩下的位用来储存数据,如果是负数,最高位就是1,如果是正数,最高位就是0。那么:如果(a-b)为负数,则最高位是1 它们按位与的结果是(a-b) 恒等,输出b。

#define max(a,b) (((a-b)>>31)|0)?b:a

比较简洁和完全的定义是: #define Max(a,b) (a==b)?e:((((a-b)>>31)|0)?b:a)



33.  题目:10个房间里放着随机数量的金币。每个房间只能进入一次,并只能在一个房间中拿金币。一个人采取如下策略:前四个房间只看不拿。随后的房间只要看到比前四个房间都多的金币数,就拿。否则就拿最后一个房间的金币。计算成功的概率!!!(solved)

<分为两部分,一部分是在i的概率,一部分是前i-1个最大的,在k个的概率>

 

34.  一个含n个元素的整数数组至少存在一个重复数,请编程实现,在O(n)时间内找出其中任意一个重复数。

<耗费空间>

<使用类似于计数排序的方法>

<solved>


35.  求最大重叠区间大小,(可以考虑求最大重叠区间的个数)<solved>

题目描述:请编写程序,找出下面“输入数据及格式”中所描述的输入数据文件中最大重叠区间的大小。 对一个正整数 n ,如果n在数据文件中某行的两个正整数(假设为A和B)之间,即A<=n<=B或A>=n>=B ,则 n 属于该行;如果 n 同时属于行i和j ,则i和j有重叠区间;重叠区间的大小是同时属于行i和j的整数个数。例如,行(10 20)和(12 25)的重叠区间为 [12 20] ,其大小为9,行(20 10)和( 20 30 )的重叠区间大小为 1 。

ans:首先按照起点排序,一个区间跟前面所有区间交集的最大值

 

36.  假设有一颗二叉树,已知这棵树的节点上不均匀的分布了若干石头,石头数跟这棵二叉树的节点数相同,石头只可以在子节点和父节点之间进行搬运,每次只能搬运一颗石头。请问如何以最少的步骤将石头搬运均匀,使得每个节点上的石头上刚好为1。



37.  N个鸡蛋放到M个篮子中,篮子不能为空,要满足:对任意不大于N的数量,能用若干个篮子中鸡蛋的和表示。



38.  有一台机器,上面有m个储存空间。然后有n个请求,第i个请求计算时需要占 R[i]个空间,储存计算结果则需要占据O[i]个空间(据O[i]个空间(其中O[i]<R[i])。问怎么安排这n个请求的顺序,使得所有请求都能完成。你的算法也应该能够判断出无论如何都不能处理完的情况。比方说,m=14,n=2,R[1]=10,O[1]=5,R[2]=8,O[2]=6。在这个例子中,我们可以先运行第一个任务,剩余9个单位的空间足够执行第二个任务;但如果先走第二个任务,第一个任务执行时空间就不够了,因为10>14-6。<银行家算法!!!>


39.  字典序排列!!!

字典序列算法是一种非递归算法。而它正是STL中Next_permutation的实现算法。我们来看看他的思路吧:
它的整体思想是让排列成为可递推的数列,也就是说从前一状态的排列,可以推出一种新的状态,直到最终状态。比如说,最初状态是12345,最终状态是54321。其实我觉得这跟我们手动做全排列是一样的。首先是12345,然后12354,然后12435,12453....逐渐地从后往前递增。

看看算法描述:
    首先,将待排序列变成有序(升序)序列。然后,从后向前寻找,找到相邻的两个元素,Ti<Tj,(j=i+1)。如果没有找到,则说明整个序列已经是降序排列了,也就是说到达最终状态54321了。此时,全排列结束。

    接着,如果没有结束,从后向前找到第一个元素Tk,使得Tk>Ti(很多时候k=j),找到它,交换Ti跟Tk,并且将Tj到Tn(Tn是最后一个元素)的子序列进行倒置操作。输出此序列。并回到第二步继续寻找ij.

例如839647521是数字1~9的一个排列。从它生成下一个排列的步骤如下:
  自右至左找出排列中第一个比右边数字小的数字4    839647521
  在该数字后的数字中找出比4大的数中最小的一个5    839647521
  将5与4交换 839657421
  将7421倒转 839651247
  所以839647521的下一个排列是839651247。
  839651247的下一个排列是839651274。


40.  如何求根号2的值,并且按照我的需要列出指定小数位<二分法>


41.  1分2分5分的硬币,组成1角,共有多少种组合

<如果求最少的硬币数,可以使用动态规划>

<也可以使用动态规划的方法>

<x + 2*y + 5*z = 10 ==>  5*z = 10 - x - 2*y ;对于z的不同取值,只要给出剩下的钱,可以用多少1,2分的钱表示>

<solved>


42.  在人人好友里,A和B是好友,B和C是好友,如果A 和C不是好友,那么C是A的二度好友,在一个有10万人的数据库里,如何在时间0(n)里,找到某个人的十度好友<BFS><solved>


43.  有一个函数int getNum(),每运行一次可以从一个数组V[N]里面取出一个数,N未知,当数取完的时候,函数返回NULL。现在要求写一个函数int get(),这个函数运行一次可以从V[N]里随机取出一个数,而这个数必须是符合1/N平均分布的,也就是说V[N]里面任意一个数都有1/N的机会被取出,要求空间复杂度为O(1)<hard>


44.  有N个正实数(注意是实数,大小升序排列) x1 , x2 ... xN,另有一个实数M。 需要选出若干个x,使这几个x的和与 M 最接近。 请描述实现算法,并指出算法复杂度<如果是正整数,那么可以用背包问题动态规划解>

<现在,可以使用背包问题递归解,排序用于做趋势判断而已>


45.  五笔的编码范围是a ~ y的25个字母,从1位到4位的编码,如果我们把五笔的编码按字典序排序,形成一个数组如下:

a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, baab, baac … …, yyyw, yyyx, yyyy

其中a的Index为0,aa的Index为1,aaa的Index为2,以此类推。

1)编写一个函数,输入是任意一个编码,比如baca,输出这个编码对应的Index;

2)编写一个函数,输入是任意一个Index,比如12345,输出这个Index对应的编码。

(注意编码的变化范围a-y, aa-ay, aaa-aay, aaaa-aaay!!!)

(solved)


46.  Q:有这样一种编码:如,N=134,M=f(N)=143,N=020,M=fun(N)=101,其中N和M的位数一样,N,M可以均可以以0开头,N,M的各位数之和要相等,即1+3+4=1+4+3,且M是大于N中最小的一个,现在求这样的序列S,N为一个定值,其中S(0)=N,(1)=fun(N),S(2)=fun(S(1)) 

<注意,如果是299怎么办?从右向左,找到第一个正数,再往下找到第一个小于9的数组,然后考虑加1,选择用剩下的数组成最小的数>


47.  对已排好序的数组A,一般来说可用二分查找可以很快找到。现有一特殊数组A[],它是循环递增的,如A[]={ 17 19 20 25 1 4 7 9},试在这样的数组中找一元素x,看看是否存在。这个问题需要判断在那个区间之中!(solved , 如果a[m] > a[l],则数组前半部分有序,否则后半部分有序 )


48.  一个大小为N的数组,里面是N个整数,怎样去除重复,要求时间复杂度为O(n),空间复杂度为O(1) (solved)


49.  将一个较大的钱,不超过1000000(10^6)的人民币,兑换成数量不限的100、50、10、5、2、1的组合,请问共有多少种组合呢?

(背包?)


50.  今天完美10.16笔试题:2D平面上有一个三角形ABC,如何从这个三角形内部随机取一个点,且使得在三角形内部任何点被选取的概率相同。(考虑一边AB的高h,产生0-1的随机数r, 然后 r*(h^2),则选中垂线上的一点,通过这一点做平行于底边的直线,随机选择一点)


57.      How will you implement a stack using a priority queue. Push and pop should be in O(1).

python中的正则表达式与unicode

正则表达式作为一种最常用的工具,在平常的工作中使用的非常普遍,在python中是由re库提供这个功能,除此之外还有regex库提供额外的功能。
在一般的正则表达式介绍中都是以ascii为代表来介绍的,但是作为一个中国的程序员,所遇到的一个最基本的问题就是字符编码了。所以这里说下如何在python中匹配
非ascii字符。

正则表达式是使用一个模式串来找出所有可以用模式串描述的字符串,模式串由普通字符跟元字符组成,这就是正则表达式最核心的想法。在一个模式串中,
普通字符是用于匹配,而元字符则可以看成是在普通字符上的施加的一种操作或者是函数。既然如此,非ascii字符对正则表达式的影响就集中在普通字符这一块而不是
元字符。而普通字符是由整数值表示的,匹配则意味着在模式串中的整数值跟在目标串中的整数值相等,如果在目标串跟模式串中使用了不同的字符编码,很明显,他
们是不能匹配的。因此在使用正则表达式用于匹配非ascii字符时,需要保持模式串跟目标串的编码一致。如下所示:

Snip20121230 2
当模式串的字符编码跟目标串一致的时候就能够成功的匹配。如果你的模式串中只有普通字符,那么这样就可以满足你的要求了。但是问题没有这么简单,当你试图用元字符的时候就会出现问题,示例如下:
Snip20130129 2
这里我们的模式串是'人生{2,}',想要匹配的字符串是有一个“人”和至少两个“生”,但是从匹配的结果来看,这个正则表达式并没有达到我们的目的。问题还是在于编码,'人生{2,}'的GB18030编码是'\xc8\xcb\xc9\xfa{2,}',因此这个正则表达式的意思就是匹配至少一个'\xc8\xcb\xc9'和至少两个'\xfa',和我们表达的意思完全按不同,原因在于一个汉字字符使用了多个字节的表示,而元字符+只作用在最后一个字节上。对于这种问题的解决方案也很简单,就是寻找一个能够将汉字字符表示为数字的编码,而不是使用多个数字来组合表示,也就是一种内部统一的表示。但是我现在又想到了一个问题,任何一个字符编码最终都是一个字节一个字节的,因为计算机最基本的存储单位就是字节,所以这个问题在于字符串比较函数的问题,没有办法将多个相关的字节识别成一个整体,才导致这个问题的。然后我们看到如果使用python内部的字符表示,那么就没有什么问题!

在这里使用Unicode能够解决问题,但是Unicode带来的编码却不止于此,因为如果把可以识别的字符从ASCII扩大到Unicode,那么有些表示就需要重新定义了,比如\d,\w,\s等等。这里就以\w为例来演示Unicode的影响。
Snip20130129 3
这里(?u)就是启用Unicode dependent特性,可以看到在未启用这个特性之前,使用正则表达式\w+不能匹配到任何的字符串,但是使用这个特性,那么就可以匹配到全部的汉字。其实在Unicode中,每个字符除了对应一个码点(也就是一个数字),还有对应的属性,可以在正则表达式中使用属性来进行匹配,比如属性为汉字什么的,还是很方便的。

Monte Carolo Method---Generating Random Variable

最近在阅读一本书Introducing Monte Carlo Methods with R,这本书主要的目的就是使用R这个语言来介绍蒙特卡洛方法,希望能借这个机会彻底弄懂蒙特卡洛法。
现在看到第二章,主要的内容就是如何使用均匀分布来生成所有其他我们想要的分布,其实类似的内容我已经在Pattern Recognition and Machine Learning中看到过的,
方法如下:

  • Inverse Transform Method
  • General Transformation Method
  • Accept-Reject Method

Inverse Transform Method: 对于一个具有概率密度ƒ的分布来说,它的cdf函数F(X)是一个0~1区间的均匀分布,然后一个定理就是:对某个概率分布的cdf函数F求
逆,所获得的结果符合原来随机变量的概率密度。下面来定义一个cdf函数F(X)的求逆操作:
Daum equation 1359880144861

因此如果我们能获得显式的cdf函数,那么就可以从均匀分布获得这个cdf函数所对应的概率密度函数。

General Transformation Method: 有些概率分布之间存在一定的简单关系,比如n个a概率分布的相加,所获得结果符合概率密度b分布,这样我们就可以使用这种特性
来使用简单的概率分布获得复杂的概率分布。

Accept-Reject Method: 上面的方法都是有自己的局限的,对于Inverse Transform Method来说,并不是所有的概率分布的cdf都能显式表示成函数形式的。对于General
Transformation Method来说,有些非标准的概率分布不能用这种方法获得,但是Accept-Reject Method就可以克服以上方法的局限性,模拟任意概率分布(前提是存在
一个简单的概率分布g)。需要满足的条件包括以下几个:

  1. 当f(x)大于0的时候,g(x)也必须大于0
  2. 对于所有的x,{f(x)/g(x)} 小于等于 M 恒成立。

因此Accept-Reject方法如下,首先产生一个y,符合概率分布g,然后再产生一个u,属于0~1区间的均匀分布,如果满足如下关系,则接受y,否则重新开始。
Daum equation 1359881576126
对于这个方法来说有以下几点需要注意:
  • 这个方法需要ƒ和M,对于归一化常量则没有要求
  • 这个方法不需要M非常的精确,可以稍微大一点,或者很多。但是问题是任意一个y被接受的概率是1/M,因此在可能的情况下,M越小越好。

代码阅读方法

最近一段时间由于毕业设计的关系,需要修改某一个开源项目的源代码,添加新的功能,这个时候需要通读整个项目的代码。其实这个项目的代码
已经读了很长的时间了,但是一直没有进展。但是到今年这个时候,如果不能搞定这个东西就不能毕业,所以:), deadline果然是生产力!下面就将阅读过
程中的一些经验讲述出来,如果需要更详细的内容请参见

第一个经验就是让程序运行起来,了解整个程序的输入和输出。了解程序的输入输出和命令行选项等,就可以帮助你对整个程序建立直观的印象,同
时,有些程序运行的过程中会打印一些log和状态,从这个也可以对程序的整体简历直观的印象!个人感觉这样的做法对那些不借助框架的程序有作用,比如linux
下的一些程序运行的时候打印输出一些东西。但是对于Windows平台上的程序,则毫无作用,比如MFC,以我当年阅读MFC源代码的经验,运行一个MFC程序
不能让你获得任何关于这个程序本身的信息。

第二个有益的经验是发现整个程序的高层逻辑!程序的高层逻辑可以理解成程序是如何展开运行的,从入口函数开始,如何使用输入数据初始化程序
内部的数据结构,这是第一个阅读阶段。第二个阶段是以发现程序的主循环,在这个循环中不停的构建运行时需要的数据,并和输入数据一起发送给实际的处理
函数或者类。然后就可以看到程序的结束条件,这就是说观察程序是如何结束的,有什么条件,这是第三个阶段。其实在一个函数内部或者类的内部也是这样的
一个过程,初始化,处理和返回。

第三个有益的经验就是发现整个程序的关键字。程序中的关键字可以理解成整个项目中不断出现的字符串,这样的字符串出现频率很高,如果能够了解
这些字符串背后所代表的程序员的意图,那么对于了解整个程序是很有帮助的。同时也可以利用编辑器中字符串搜索功能可以很好的跟踪整个运行过程,用一个
函数不停的找到调用者,然后看下一个函数。在这个方面cscope可以起到很好的作用。

第四个经验就是要分析程序中不同数据结构的关系。一般来说现在很多的程序是面向对象设计的(或者是面向结构体)。利用不同数据结构或者类的关系,
比如继承、包含等关系,可以从数据上理解整个程序的运行!

在总结了上面的经验后,我突然发现相关的经验包括两个方面:一是动作方面的,比如函数调用等等;二是数据流动方面,数据流动本身就能一定程度上
反映整个程序的逻辑流程。

Numerical Methods with MATLAB(1)

目前正在阅读MATLAB相关的书籍:Numerical Methods with MATLAB,现在感觉这本书写的还行,
细致基础,而且写的比较清楚,同时把malab和数值算法结合在一起。

目前刚看完第一章,下面是相关的命令跟工具tips
1. 保存和加载数据的语句
save or load
2. 画图相关的命令
subplot:并不是用于画图,感觉是获得窗口句柄的。
plot、hist:2d作图的函数
title、label、label、axis:用于控制显示的语句,根据字面理解就可以了。
meshgrid/mesh,surf,contour:用于3D的作图,也仅用于3D,感觉surf比mesh好看,contour画出的是大量的等高线!!!
3. 矩阵操作相关的命令
pinv:求逆,也可以求伪逆
sum,prod:求和和求积的函数
max、min:注意第二个参数
reshape、ones、zeros、eye、diag:有用的小函数
4. 随机数相关的函数
rand:uniform分布
randn:高斯分布
5. 特殊变量
nargin、varargin:用于函数传递参数的。
6. 多项式相关的函数
polyval:多项式求值
roots:求根
poly:不知道干什么的
conv:多项式相乘
deconv:多项式相除
polyder:多项式微分
polyint:多项式积分
mkpp、ppval:分段式多项式,很有趣
还有强调了计算时因为有限位的表示而产生的各种错误:
a. 截断错误
b. Round-off Error
c. Overflow/Underflow
d. Negliable Addition:产生的原因是因为浮点数在计算时先对阶(即先确保阶数相同),然后计算
e. Lost of Significance:产生的原因是两个数非常相近,然后坐减法
以后接触过这些概念,但是没怎么具体的实例,其实这些就是使用计算机参与数值计算时需要考虑的问题。
还强调使用迭代法计算,而不是直接计算,这样可以提高计算的精度。 其他命令
ezplot:对于断点的处理比较好
find
fprintf,sprintf:格式化输出
format:默认输出格式控制
hold on,hold off:画图的时候比较有用,可以在一个图上画上好几条线
view:3D图视角的调整
meshc、meshz:对mesh函数的扩展
quad:求积分
\,/:left division和right division,与least-squre还是有点区别的

统计机器学习

机器学习是一个交叉学科,相关的知识包括:数值优化,数值线性代数,统计和概率论。个人感觉最容易与机器学习的方法相似的恐怕就是统计,
两个不同的学科有着相同的目的:从大量的数据之中学习到有价值的信息,而且现在流行的机器学习方法都是基于统计的。

从任务来看:对统计来说主要的任务包括估计(Estimation),假设检验(Hypothesis Testing),预测(Prediction)。估计包括点估计和区间估计两种不同的任务。
假设检验的目的是为了对参数做出判断,即参数是否属于某个特定的集合。预测是根据已有的数据建立统计模型,然后对未知的情况做出预测,当然对于做出的预测
同样可以给出置信区间。

最基本的机器学习任务包括有监督学习、无监督学习。另外根据Murphy的说法,另外还包括一类Reinforcement Learning。有监督学习根据输出的不同,可以分为
分类(Classification)、回归(Regression)和排序(Ordinal Regression)三种,明显的和统计的预测产生了交集。无监督学习的主要目的机器学习也包含CRF这种序列模型,在统计
中称之为图模型(Graphical Model)。

从方法上来看:机器学习的主要功能就是根据数据确定目标模型的参数,在获得参数后即可使用这些统计模型。为了获得这些参数,机器学习使用数值优化方法对
目标函数进行优化,而这些目标函数有可能就是似然函数(比如最大熵方法)。同样贝叶斯方法在统计学习中也被大量的使用。


伪逆

伪逆(pseudo inverse)是对于矩阵逆的一种推广,满足一定性质的矩阵都可以成为矩阵A的伪逆。伪逆具有存在且唯一的良好性质,可以用于解决最小二乘和最小范数问题。
最小二乘问题是对于一个超定矩阵而言的,最小二乘问题的解是能够最小化残差的解。而最小范数问题是针对欠定矩阵矩阵而言,对这类线性方程组不存在唯一解,伪逆给出的是所有的解
2范数最小的。

对于超定的线性方程组,伪逆可以给出最小二乘问题的解,用其他的方法同样能够完成,而且二者给出的解是相同的(因为唯一),通常可以使用QR或者SVD分解完成。但是对于
欠定方程组而言,使用伪逆可以给出最小范数解,使用QR方法则只是给出无数个可行解中的一个。

数值线性代数小结

对于数值线性代数(Numerical Linear Algebra,简称NLA)来说有三个最重要的问题:线性方程组,线性拟合和特征值计算。从这个观点来看,NLA的问题
也不是特别的多。但是NLA的复杂性存在于两个方面,一个存在于计算工具上,另一个存在于要处理的问题本身。对于第一个问题,由于使用计算机进行数值运算,不可避免
的会产生精度的问题,所以为了避免精度问题和合理的量化精度产生的影响,NLA会变得非常复杂,对于每一个算法,都会存在对这个算法的分析,现在我个人理解就是扰动
分析。对于每个问题本身,由于矩阵会存在不同的结构,为了利用这些结构的特性,针对每一个结构都会有特定的算法来提高解决问题的速度,这样就会使得同一个问题存在
多个可用的算法,需要使用者针对问题本身做出选择。

对于NLA来说,可以利用的结果包括对称,带状,对角和三角(包括上三角和下三角)。另外一个常用的处理方式就是矩阵分块,使用矩阵分块,利用程序的局部性提升
计算的性能。

对于如何解决这个问题,有一个paper可以很好的说明这一点(The Decompositional Approach to Matrix Computation)。
在这篇文章中作者之处为了解决现在的问题,我们是先通过矩阵分解(Matrix Decomposition),然后利用分解后的矩阵来解决这些问题的。现在最广泛流传的矩阵分解包括LU,
Pivoted LU,LDL,Cholsky,QR,Schur,SVD,Spectral等分解。学习NLA,很大一部分就是在学习如何进行矩阵分解以及如何使用分解来解决问题。

从另外一个角度来看,使用矩阵分解解决问题属于直接方法(Direct Method)。与之相对应的存在另外一种解决问题的方法,称之为迭代式方法(Iterative Method)。
两种方法各有利弊,在不用的场景下有不同的用途。对于迭代式方法,比较出名的有Keylov subspace mehtod, 共轭梯度法(Conjugate Gradient)。

将会在接下来的blog中详细解释主要的矩阵分解方法和迭代式方法。

LU分解

1/6 LU 分解

LU 分解可以写成A = LU,这里的L代表下三角矩阵,U代表上三角矩阵。对应的matlab代码如下:

function[L, U] =zlu(A)

% ZLU - LU decomposition for matrix A

% work as gauss elimination

[m, n] = size(A);

if m ~= n

error('Error, current time only support square matrix');

end

L = zeros(n);

U = zeros(n);

for k = 1:n-1

gauss_vector = A(:,k);

gauss_vector(k+1:end) = gauss_vector(k+1:end) ./ gauss_vector(k);

gauss_vector(1:k) = zeros(k,1);

L(:,k) = gauss_vector;

L(k,k) = 1;

for l=k+1:n

A(l,:) = A(l,:) - gauss_vector(l)*A(k,:);

end

end

U = A;

这段代码的目的非常简单,就是使用高斯消元法给出L,U。但是计算的稳定性非常不好,这点可以通过这段代码的分解结果和matlab自带lu的分解结果相比较得出。比较的方法非常简单:就是计算l*u与原始矩阵想减之后的Frobinus范数大小,使用如下的代码做出两个结果的比较:

n = 1000;

my_error = zeros(1, 1000);

sys_error = zeros(1, 1000);

for i = 1:n

test = randn(5);

[zl, zu] = zlu(test);

[l, u] = lu(test);

my_error(i) = norm(zl*zu - test, 'fro');

sys_error(i) = norm(l*u - test, 'fro');

end

disp(mean(my_error));

disp(var(my_error));

disp(mean(sys_error));

disp(var(sys_error));

在这段代码里面,随机的生成一个5x5的符合高斯分布的矩阵,然后使用自己写的lu分解和matlab自带的lu分解分别给出L和U,再计算norm(L*U - test),从这里就可以看出我们自己计算出来的结果精度和matlab自带的lu真实的差异了。这个差异就体现为这些值的均值和方差。结果如下:

mean of my lu : 13.313846
variance of my lu : 43622.114147
mean of matlab lu : 0.000000
variance of matlab lu : 0.000000

从这个结果可以看出,我们自己写的lu分解的结果在均值和方差上比matlab自带的差了很多。个人认为原因有两点:第一个方法的原因,matlab给出的结果是pivoted LU,第二个是因为实现的原因,matlab基于成熟的LAPACK,肯定会比自己写的更好了。

这一步使用PA = LU来完成LU分解。代码如下:

function [P, L, U] = zplu(A)

% pivoted LU decompositon P*A = L*U

[m, n] = size(A);

if m ~= n

error('zplu:test', 'current time only support square matrix');

end

P = eye(n);

L = zeros(n, n);

for k = 1:n-1

%find the largest element in k column of A from row k to n

[max_value, max_index] = max(A(k:end, k));

max_index = max_index + k - 1;

if max_index ~= k

A([k max_index], :) = A([max_index k], :);

P([k max_index], :) = P([max_index k], :);

L([k max_index], :) = L([max_index k], :);

end

if A(k,k) ~= 0

gauss_vector = A(:,k);

gauss_vector(k+1:end) = gauss_vector(k+1:end) ./ gauss_vector(k);

gauss_vector(1:k) = zeros(k,1);

L(:,k) = gauss_vector;

L(k, k) = 1;

for l=k+1:n

A(l,:) = A(l,:) - gauss_vector(l)*A(k,:);

end

end

end

U = triu(A);

下面是运行前面检测程序的输出:

mean of my lu : 7.803258
variance of my lu : 1450.332510
mean of matlab lu : 0.000000
variance of matlab lu : 0.000000

两个结果相比较可以看到,Matlab的lu一样的稳定,但是使用pivot来调整矩阵A的次序可以极大的提高LU分解的稳定度,这个可以从下降了非常多的方差可以看出。

pivot LU是从k列的k+1到n个元素种选择最大的一个,调换到第k个位置。从我个人的角度理解,除以最大的元素使得高斯变换矩阵中非对角元素全部小于1。由于计算机种存储浮点数的机制,绝对值越靠近0,其精度越高。所以使用pivot这种方法可以极大的提高LU分解的稳定程度。但是也需要指出,使用pivot并不一定能提高LU分解的精度,对于特定的矩阵,不使用pivot说不定可以获得更好的性能。

为了进一步提高提高LU分解的稳定性,可以使用full pivoted LU。分解公式:P*A*Q = L * U; 对应的Matlab代码如下:

function [P, Q, L, U] = zflu(A)

%full pivoted LU decomposition

%

% full pivoted LU decomposition

[m, n] = size(A);

if m ~= n

error('current only support square matrix')

end

P = eye(n);

Q = eye(n);

for k=1:n-1

%find the larget element in A(k:n,k:n)

[max_value, row_index] = max(A(k:n, k:n));

[max_value, col_index] = max(max_value);

real_row = k-1 + row_index(col_index);

real_col = k-1 + col_index;

%exchange the row and column of matrix A

if real_row ~= k

A([k real_row],:) = A([real_row k], :);

P([k real_row],:) = P([real_row k], :);

end

if real_col ~= k

A(:, [k real_col]) = A(:, [real_col k]);

Q(:, [k real_col]) = Q(:, [real_col k]);

end

if A(k, k) ~= 0

rows = k+1:n;

A(rows, k) = A(rows, k) ./ A(k, k);

A(rows, rows) = A(rows, rows) - A(rows, k)*A(k, rows);

end

end

L = tril(A);

for k=1:n

L(k, k) = 1;

end

U = triu(A);

跑完test之后的结果如下:

mean of my lu : 7.77222e-16
variance of my lu : 4.3478e-29
mean of matlab lu : 3.69764e-16
variance of matlab lu : 2.03659e-32

可以看到使用full pivoted LU 分解可以在很大程度上保证分解的稳定性,即便是使用我们自己写的代码。但是即便如此,仍然推荐使用LAPACK中的代码,因为那里面的代码是经过严格的测试和分析的,在各种一场情况下应该都有很好的表现。

这里所介绍的LU分解可以使用另外一种基于GaxPy形式的运行,将在下面介绍。

LU分解

接着上次LU分解的讲解,这次给出使用不同的计算LU分解的方法,这种方法称为基于GaxPy的计算方法。这里需要了解lapapck中的一些函数。lapack中有一个函数名为gaxpy,所对应的矩阵计算公式是:x = Gx + y; 对应的Matlab代码如下:

function[L, U] =zgaxpylu(A)

%calculate LU decomposition based on Gaxpy operation

%the same way as zlu.m but differnt approach

[m, n] = size(A);

if m ~= n

error('current support square matrix only')

end

L = eye(n);

U = eye(n);

for k = 1:n

v = zeros(n, 1);

if k == 1

v(k:end) = A(k:end, k);

else

U(1:k-1,k) = L(1:k-1,1:k-1)\A(1:k-1,k);

v(k:end) = A(k:end, k) - L(k:end, 1:k-1)*U(1:k-1,k);

end

if k < n

L(k+1:end,k) = v(k+1:end)/v(k);

L(k, k) = 1;

end

U(k, k) = v(k);

end

将这段代码运行1500次,每次使用随机生成的高斯矩阵并和Matlab的lu分解结果对比,统计数据如下:

mean of my lu : 1.7676e-14

variance of my lu : 3.07075e-25

mean of matlab lu : 3.70416e-16

variance of matlab lu : 2.14989e-32

和前一种方法不同,目前的这个方法显式的计算出L和U,而在前面的方法是计算出L,然后就可以拿到U。

使用部分选主元的方法进行LU分解,对应如下代码:

function [P, L, U] = zgaxpyplu(A)

%compute LU decomposition based on Gaxpy operation with pivoting

%aimed at improve the stability of LU decomposition

[m, n] = size(A);

if m ~= n

error('current support square matrix only')

end

P = eye(n);

L = eye(n);

U = zeros(n);

for k = 1:n

v = zeros(n, 1);

if k == 1

v(k:end) = A(k:end, 1);

else

U(1:k-1, k) = L(1:k-1, 1:k-1) \ A(1:k-1, k);

v(k:n) = A(k:n, k) - L(k:n, 1:k-1)*U(1:k-1, k);

end

%find the largest element in v(k:end)

[max_value, max_index] = max(v(k:end));

max_index = max_index + k - 1;

if max_index ~= k

%exchange the max_index-th row and k-th row

A([k max_index], k+1:n) = A([max_index k], k+1:n);

%exchange the max_index-th row and k-th row in L

if k > 1

L([k max_index], 1:k-1) = L([max_index k], 1:k-1);

end

P([k max_index], :) = P([max_index k], :);

v([k max_index]) = v([max_index k]);

end

if (abs(v(k)) > 1e-6) && (k < n)

v(k+1:end) = v(k+1:end) / v(k);

L(k+1:end, k) = v(k+1:end);

end

U(k, k) = v(k);

end

运行这段代码1500次,每次都使用随机生成的矩阵和Matlab的LU分解做对比,结果如下:

mean of my lu : 2.02547e-15
variance of my lu : 9.06349e-29
mean of matlab lu : 3.65765e-16
variance of matlab lu : 1.98304e-32

将每个算法和同类型的算法相比,使用gaxpy的算法都比之前的方法要好。但是现在有一个问题是使用pivot的算法居然比不使用pivot的算法没有足够显著的改进,当然这也证明了使用基于gaxpy运算可以提高LU分解的稳定性。

总结:LU分解是用于求解线性方程组最基本的矩阵分解方法,对于LU分解可以使用高斯消元法,也可以使用基于gaxpy的运算方法。但是从目前的结果来看,使用gaxpy运算可以极大的提高LU分解的稳定性。但是作为成熟的方法,使用lapack中对应的方法是最好的选择。

cholesky分解

接着LU分解继续往下,就会发展出很多相关但是并不完全一样的矩阵分解,最后对于对称正定矩阵,我们则可以给出非常有用的cholesky分解。这些分解的来源就在于矩阵本身存在的特殊的

结构。对于矩阵A,如果没有任何的特殊结构,那么可以给出A=L*U分解,其中L是下三角矩阵且对角线全部为1,U是上三角矩阵但是对角线的值任意,将U正规化成对角线为1的矩阵,产生分解A = L*D*U, D为对角矩阵。如果A为对称矩阵,那么会产生A=L*D*L分解。如果A为正定对称矩阵,那么就会产生A=G*G,可以这么理解G=L*sqrt(D)。

A=L*D*U分解对应的Matlab代码如下:

function[L, D, U] =zldu(A)

%LDU decomposition of square matrix A. The first step for Cholesky

%decomposition

[m, n] = size(A);

if m ~= n

error('support square matrix only')

end

L = eye(n);

U = eye(n);

d = zeros(n,1);

for k=1:n

v = zeros(n, 1);

if k == 1

v(k:end) = A(k:end, k);

else

m = L(1:k-1, 1:k-1) \ A(1:k-1, k);

for j = 1:k-1

U(j, k) = m(j) / d(j);

end

v(k:end) = A(k:end, k) - L(k:end, 1:k-1)*m(:);

end

d(k) = v(k);

if k < n

L(k+1:end, k) = v(k+1:end)/v(k);

end

end

D = diag(d);

分解的稳定性和精度结果如下:

mean of my lu : 9.0307e-15

variance of my lu : 4.17441e-27

mean of matlab lu : 3.70519e-16

variance of matlab lu : 2.07393e-32

这里的计算是基于Gaxpy,所以稳定性和精确度相当之好。

A=L*D*L分解对应代码如下,这里要求A必须为对称矩阵:

function[D, L] =zldl(A)

%A = L*D*L' another version of LU decomposition for matrix A

[m, n] = size(A);

if m ~= n

error('support square matrix only')

end

L = eye(n);

d = zeros(n,1);

for k=1:n

v = zeros(n,1);

for j=1:k-1

v(j) = L(k, j)*d(j);

end

v(k) = A(k,k) - L(k, 1:k-1)*v(1:k-1);

d(k) = v(k);

L(k+1:end, k) = (A(k+1:end,k) - A(k+1:end, 1:k-1)*v(1:k-1)) / v(k);

end

D = diag(d);

对应分解的精确度和稳定度如下:

mean of my lu : 35.264
variance of my lu : 29011.2
mean of matlab lu : 5.88824e-16
variance of matlab lu : 8.40037e-32

使用如下的代码做测试:

n = 1500;

my_error = zeros(1, n);

sys_error = zeros(1, n);

for i = 1:n

test = gensys(5);

[zd, zl] = zldl(test);

[l, d] = ldl(test);

my_error(i) = norm(zl*zd*(zl') - test, 'fro');

sys_error(i) = norm(l*d*(l') - test, 'fro');

end

fprintf('mean of my lu : %g\n', mean(my_error));

fprintf('variance of my lu : %g\n', var(my_error));

fprintf('mean of matlab lu : %g\n', mean(sys_error));

fprintf('variance of matlab lu : %g\n', var(sys_error));


对于运算的精度如此之低的原因并不清楚

A=G*G’; cholesky分解对应的代码如下:

function[G] =zgaxpychol(A)

%cholesky decomposition for symmetric positive definite matrix

%the only requirement is matrix A: symmetric positive definite

[m, n] = size(A);

if m ~= n

error('support square matrix only')

end

G = eye(n);

for k=1:n

v = A(:,k);

if k > 1

v(:) = v(:) - G(:,1:k-1)*G(k,1:k-1)';

end

G(k:end, k) = v(k:end) / sqrt(v(k));

end

对应的测试结果如下

mean of my lu : 1.10711e-15
variance of my lu : 3.04741e-31
mean of matlab lu : 5.5205e-16
variance of matlab lu : 9.64928e-32

自己代码的精确度和稳定性可以媲美Matlab的代码,产生这种结果的原因应该是positive sysmetric definite matrix的原因,这段代码基于gaxpy的结果,下面给出另外一种基于外积的运算结果。

function[G] =zopchol(A)

%cholesky decomposition based on rank-1 matrix update

[m, n] = size(A);

if m ~= n

error('support square matrix only')

end

G = zeros(n);

for k=1:n

G(k,k) = sqrt(A(k,k));

G(k+1:end, k) = A(k+1:end, k) / G(k,k);

%update matrix A

for j = (k+1):n

A(k+1:end,j) = A(k+1:end,j) - G(j,k)*G(k+1:end,k);

end

end

对应的测试结果如下:

mean of my lu : 9.33114e-16
variance of my lu : 1.71179e-31
mean of matlab lu : 9.92241e-16
variance of matlab lu : 1.60667e-31

对应的测试程序如下,这里使用系统自带的chol函数完成cholesky分解。

n = 1500;

my_error = zeros(1, n);

sys_error = zeros(1, n);

for i = 1:n

test = genpd(5);

[zg] = zopchol(test);

l = chol(test, 'lower');

my_error(i) = norm(zg*(zg') - test, 'fro');

sys_error(i) = norm(l*(l') - test, 'fro');

end

fprintf('mean of my lu : %g\n', mean(my_error));

fprintf('variance of my lu : %g\n', var(my_error));

fprintf('mean of matlab lu : %g\n', mean(sys_error));

fprintf('variance of matlab lu : %g\n', var(sys_error));


将两个结果想比较,可以发现两个版本的cholesky分解的精确度和稳定度差不多。

Cholesky分解的核心在于矩阵对称正定的结构,基于LU分解的再次扩展。