猫の学术 – 火星猫の窝

百日维新

为了避免被沦为平庸，所以开始百日维新计划
目标：掌握深度学习相关技能
目标2：利用深度学习进行变脸的进一步优化
目标3：利用metal或者coreML去优化神经网络

以上，三个月后来看成果

磁盘速度对比

从上往下：
Maxtor 160G（购于2006年）
影驰GT 64G（购于2013年）
浦科特M5S 128G（购于2013年）
从左往右：
2014年9月27日 2016年8月12日

由图可见，固态硬盘速度显著高于机械硬盘（虽然现在新的机械硬盘也能到200MB/s峰值、150MB/s均速了）
机械硬盘速度与使用寿命相关性不大
固态硬盘随着使用时间的增加，读取性能波动比较大，应该与闪存颗粒当前状态有关（写入位置动态调整算法）。不过平均读取速度还是相当的~
in all：SSD+HDD王道~

uTorrent 占用内存过大的解决方案

uTorrent是一个很小巧的BT/PT下载软件。然而，由于实现的原因，在长时间挂PT站点的情况下，uTorrent会占据大量的内存，严重影响系统性能，同时也降低了上传下载速度。

原因分析：

由于uTorrent需要经常读取多个文件（特别是挂PT站点），所以会产生大量的文件缓存。windows系统对于缓存的管理能力有缺陷，导致内存无休止增长。

解决方法：

1）uTorrent3.2版本及之前：关闭系统缓存

在uTorrent选项-设置-高级-缓存中，勾选禁用系统读取缓存和禁用系统写入缓存

2）uTorrent3.3版本及之后：使用setsystemfilecachesize控制系统缓存

由于uTorrent设置中取消了禁用系统缓存，所以只能手动控制系统的缓存了。

下载setSystemFileCacheSize，解压后双击打开，可以看到系统的文件缓存并没有限制。

打开命令提示符（运行-cmd），通过cd命令指定到文件夹之后，执行：SetSystemFileCacheSize.exe 512 1024

然后再去双击打开SetSystemFileCacheSize.exe，可以看到已经设置过系统文件缓存了~

注意：这里的512 1024代表最小缓存、最大缓存量，单位是MB。

下载链接：setsystemfilecachesize

需要注意的一点是：如果采用SetSystemFileCacheSize的方法，那么每次重新启动计算机后都会失效，需要重新设置，可以放到启动任务里~

cvDFT的性能问题

最近写一个代码的时候，发现cvDFT在32位下比64位下速度还快，觉得很不可思议。于是查看了OpenCV的源代码，发现了如下的说明：

//On Win64 optimized versions of DFT and DCT fail the tests (fixed in VS2010)

看来是VS2008在优化的时候会让OpenCV的DFT和DCT出错，不得已禁用了编译器代码优化，从而速度较慢。

唉~看来毕业的时候得用VS2010了~

OpenCV 2.4.2 imdecode/cvDecodeImage 的 BUG及解决方案

OpenCV是很好用的开源库，不过，还是有一些BUG的~

比如，今天遇到的问题是，imdecode的执行速度很慢。

照理来说，imdecode是从内存解析一幅图像，应该比cvLoadImage还快（或者至少不慢）。

但实际上，执行的时候却是imdecode慢很多（一张图片要1秒以上）。而且很奇怪的是，在某些机器很快，某些机器就很慢。而且调用了不同版本的OpenCV速度也不同。

为什么呢？本着质疑的原则，开始查看OpenCV的源代码。

imdecode的实现在modules\highgui\src\loadsave.cpp中。结果，发现opencv也是先将内存数据写到文件然后再读取的……这不是偷懒么orz

不过，逻辑上没有问题，算法上却犯二了……OpenCV2.4.2及之前版本在实现这个函数的时候，申请了一个临时文件（C:\user\用户名\AppData\Local\Temp\下的ocvXXXX.tmp文件，其中XXXX是0~F的16进制数）。然后写这个文件，然后读。关键是，没有删除！原因是因为临时文件可能不存在（本意是如果形如ocvXXXX.tmp的文件都存在了，那么就不能再新建了，所以返回空不作操作，实际上不会走到这一步），所以最后不一定需要删除文件。于是写OpenCV的小朋友这里为了程序稳定就没有删除临时文件。如图所示：

结果就是：如果调用imdecode次数越多，速度越慢。超过65535次则每次需要枚举65535个临时文件是否存在。。这个时间对系统而言大致是1秒吧~

当然，写OpenCV的小朋友还是意识到了这个问题，至少2.4.5开始这部分代码就改成判断临时文件名是否为空，不为空则删除了。这样就不会产生临时文件堆积的问题了~

anyway，结论就是：

如果想从内存里面直接解析一幅图像，还是乖乖自己写到文件再读取吧~可以模仿opencv去向系统申请临时文件的说~（GetTempPathA和GetTempFileNameA函数）

finding a job

目前找工作的公司及相关进展：

阿里：笔试（因为试卷原因没印出来）->面试*2->offer
微软：笔试->挂
google：机试*2（第一次被判抄袭orz）->面试*1->面试*2->面试*2->挂
腾讯：电面*2->笔试->面试*2->offer
百度：笔试->面试*3->offer
联想：面试（没去面，因为人在上海）
虹软：笔试->面试->等消息
爱奇艺：笔试->面试（两次让去面试都有事情冲突……）
雅虎北研：笔试->面试*3->面试（技术总监）->等消息
网易有道：笔试（因为要先听宣讲会，而宣讲会人满了只能在外面等，于是直接翘了）
hulu：笔试->挂
微策略：笔试->面试*2->终面->offer
创新工厂：笔试->挂

目前已挂：微软、hulu、创新工程、google
目前已翘：联想、爱奇艺、网易有道
目前已拒：阿里、微策略、百度、雅虎北研
目前等消息：虹软（目测皆挂）
目前已签：腾讯
last update：20131220

test for code

class Solution { public: struct info { int id; int step; }; void gen(vector &vstr,vector *c, int id,vector> &res) { vector v; vector> tres; if(c[id].size()==0) { v.push_back(vstr[id]); res.push_back(v); return; } int i,j; for(i=0;i> findLadders(string start, string end, unordered_set &dict) { // Start typing your C/C++ solution below // DO NOT write int main() function vector> res; vector v; if(start==end) //start is end { v.push_back(start); res.push_back(v); return res; } unordered_map mp; unordered_map::iterator iter_m; unordered_set::iterator iter_s; vector vstr; dict.insert(start); dict.insert(end); int id=0,i,j,k; for(iter_s=dict.begin();iter_s!=dict.end();++iter_s) { vstr.push_back(*iter_s); mp.insert(make_pair(*iter_s,id)); id++; } int nStart, nEnd; iter_m = mp.find(start); nStart = iter_m->second; iter_m = mp.find(end); nEnd = iter_m->second;

int len = start.length(); int nTotal = mp.size(); vector *c = new vector [nTotal]; int *step = new int [nTotal]; for(i=0;i q; q.push(temp); while(!q.empty()) { cur=q.front(); q.pop(); if(cur.step>=nMin) continue; string str = vstr[cur.id]; for(i=0;isecond; if(step[id]<=cur.step) continue; if(step[id]!=cur.step+1) { temp.id=id; temp.step=cur.step+1; q.push(temp); step[id]=cur.step+1; if(id==nEnd) nMin = cur.step+1; //find end } c[id].push_back(cur.id); } } } if(c[nEnd].size()==0) //no result { delete[]c; delete[]step; return res; } gen(vstr,c,nEnd,res); delete[]c; delete[]step; return res; } };

汉明距离的快速计算方法

首先，所谓汉明距离，是说两个01串之间不相同的0和1的个数。
比如： 1 1 0 1 1 和 1 0 1 0 1 的汉明距离就是3（中间三位不相同）
那么，怎么快速计算汉明距离呢？
这里给出三个方法，均以两个unsigned __int64的数a和b的汉明距离来做例子：

1）参考文章：http://crane.is-programmer.com/posts/17830.html
unsigned __int64 nHammingDist=a^b;

nHammingDist = (nHammingDist & 0x5555555555555555UI64) + ((nHammingDist>>1) & 0x5555555555555555UI64); nHammingDist = (nHammingDist & 0x3333333333333333UI64) + ((nHammingDist>>2) & 0x3333333333333333UI64); nHammingDist = (nHammingDist & 0x0f0f0f0f0f0f0f0fUI64) + ((nHammingDist>>4) & 0x0f0f0f0f0f0f0f0fUI64); nHammingDist = (nHammingDist & 0x00ff00ff00ff00ffUI64) + ((nHammingDist>>8) & 0x00ff00ff00ff00ffUI64); nHammingDist = (nHammingDist & 0x0000ffff0000ffffUI64) + ((nHammingDist>>16) & 0x0000ffff0000ffffUI64); nHammingDist = (nHammingDist & 0x00000000ffffffffUI64) + ((nHammingDist>>32) & 0x00000000ffffffffUI64);

2）如果上述汉明距离需要频繁计算，那么，打表法不失为一种好方法。考虑到打表的大小要尽可能贴近L1缓存限制，所以考虑8bit计算一次：
static int Ham_count[256]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};

unsigned __int64 temp=a^b; uchar *uch=(uchar*)&temp; int i,nHammingDist=0; for(i=0;i<8;i++) { nHammingDist+=Ham_count[uch[i]]; }

3）如果CPU支持sse4.2指令集的话，可以用sse扩展指令快速计算（intel core 2以上CPU/amd 推土机以上CPU）
#include //需要这个头文件（VS2008及以上的VS。gcc之类的不清楚） int nHammingDist=_mm_popcnt_u64(a^b);

那么，上述三种快速算法的时间代价分别是多少呢？
测试方法：1,000个256bit数，每个在100,0000个256bit数中间找最近的那个数。计算总计花费的时间。（单核2.8GHz intel core i5 460m）
下面是实验结果：
方法1: 56s
方法2: 53s
方法3: 34s

由此可见，打表法比折半计算稍快（实际如果多线程同时处理的话，方法2会比方法1快10%以上，因为方法1需要ALU计算，而方法2基本不需要ALU）
方法3的利用sse4.2指令的方法是最快的，但需要CPU支持（不过按照电脑每5年左右会淘汰一次的角度来看，过几年就都支持了）

总结：算法再快，不如CPU硬件实现快……

acm mm short rejected

第一次投paper，花了一个星期的时间连写作带实验（之前代码基本写完了）
本来还抱有一丝幻想。
结果，还是华丽丽的reject了。。。
4个review，1个给了reject，2个给了weak reject，1个给了weak accept。
大致的问题都是：1）实验结果曲线不符合常理。2）写作里面一些公式没必要，一些公式有问题或者未声明。3）理论部分创新不大。
唉，果然还是太天真了啊。看来实验还是得弄出个看上去“正常”的曲线啊，否则人家一看实验就觉得reject了……

windows下绑定线程（进程）到指定CPU核心

不知各位程序员在测试代码性能的时候有没有注意过，一个程序指定到单独一个CPU上运行会比不指定CPU运行时快。这中间主要有两个原因：
1）CPU切换时损耗的性能。
2）Intel的自动降频技术和windows的机制冲突：windows有一个功能是平衡负载，可以将一个线程在不同时间分配到不同CPU，从而使得每一个CPU不“过累”。然而，Inter又有一个技术叫做SpeedStep，当一个CPU没有满负荷运行时自动降频从而达到节能减排的目的。这两个功能实际是冲突的：一个程序被分配到多个CPU协同工作->每个CPU都不是满载->每个CPU都会降频->windows发现每个CPU性能都降低了，因此程序执行速度也降低了。

因此，将线程（进程）绑定到指定CPU核心，从而不让windows自作主张帮我们分散任务，从而提高单线程效率是很有必要的。有两种方法实现绑定进程到指定CPU：
1）手工调节：在资源管理器的进程里面，设置相关性，可以设置进程到某个或者某些指定的CPU核心。

这种方法最简便，同样是最优效率的，因为你可以根据当前CPU的负载情况进行选择。
2）代码自动调节：
参考：http://www.cnblogs.com/kex1n/archive/2011/05/09/2040924.html
具体函数为：
DWORD_PTR SetThreadAffinityMask(HANDLE hThread, DWORD_PTR dwThreadAffinityMask);
其中，第一个参数为线程句柄，第二个参数为一个mask。
如果要知道当前线程的句柄，可以通过函数：GetCurrentThread()得到。否则，在创建多线程的时候，也同样可以得到创建的线程的句柄。
第二个参数为mask，可取值为0~2^31(32位）和0~2^63（64位），每一位代表每一个CPU是否使用。
比如，你要指定进程到第0个CPU上，则mask=0x01
第1个CPU：mask=0x02
第2个CPU：mask=0x04 （注意不是0x03）
第3个CPU：mask=0x08
以此类推。
如果要指定多个CPU：
比如第0、1个：mask=0x03
第1、2个：mask=0x06
以此类推。
如果CPU个数不足，则会进行取模操作。比如一共4个CPU，则mask=0x0010则和0x01一样。
这种方法的好处是多线程时不用每次都手动选择CPU，缺点是万一选到的CPU负载很高，那么程序执行速度就慢了（英雄所见略同所以大家都抢到同一个CPU去了么~~）
效果如下图所示：

还有一个实用的函数来获取当前CPU的核心数量：
SYSTEM_INFO info; GetSystemInfo(&info); printf("Number of processors: %d.\n", info.dwNumberOfProcessors);
输出的是逻辑核心数量，比如i3处理器就是双核心四线程，输出4。i5处理器是四核心四线程，输出也是4。
这样就可以方便的知道当前系统一共有多少个CPU了，同时也方便了线程数选择。