磁盘速度对比

diskSpeed
从上往下:
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。

systemCache

下载链接: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的小朋友这里为了程序稳定就没有删除临时文件。如图所示:

temp2

结果就是:如果调用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核心
这种方法最简便,同样是最优效率的,因为你可以根据当前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核心
还有一个实用的函数来获取当前CPU的核心数量:

SYSTEM_INFO info;
GetSystemInfo(&info);
printf("Number of processors: %d.\n", info.dwNumberOfProcessors);

输出的是逻辑核心数量,比如i3处理器就是双核心四线程,输出4。i5处理器是四核心四线程,输出也是4。
这样就可以方便的知道当前系统一共有多少个CPU了,同时也方便了线程数选择。