上一篇博客里提到了一个简单的聚类算法kmeans。这里是用C语言写的一个命令行的版本,它似乎可以运行,也能产生结果,不过我也没有仔细验证过是否正确 :-)    这里是在GitHub上托管的源代码。

使用方法以Linux环境为例,首先make一下,生成可执行文件kmeans

然后 ./kmeans  input.csv  ouput.csv  3   random  means

input.csv和ouput.csv是输入数据和输出数据文件,CSV文件不神秘,用文本编辑器打开看就是几行点坐标数据。
3是指定要把点集分成几个类。
中心点Center计算有两种方式:1.mean(均值); 2.median(中位数)
初始化方法有以下两种方式:1.random partition(随机初始化); 2.k-means++(Knuth的弟子想出的方法) (more…)

19,806 views

K-means Clustering Algorithm 中文名也许叫“K均值聚类算法”,是统计学和数据挖掘领域中常用的一种算法。维基百科上是这样介绍的:k-means clustering is a method of cluster analysis which aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean (more…)

16,667 views

时间倒回到2011年5月的一天,大学的最后一门课《计算机信息安全技术》,讲到《缓冲区溢出》这一章,并且给出了一段示例代码来演示缓冲区溢出,回到宿舍后出于好奇我运行了一下这段代码,发现结果并不是书上所说的那样,当时在人人网也发过一篇吐槽的日志,但是一直拖到现在都没有仔细的去研究过,正好现在十一放假没事,就花点时间搞搞啦。

书第136页-137页。代码如下,出于简单考虑(其实书上的C++代码格式也是错的),我除去了头文件和cout函数,这样就跟纯C语言代码是一样了。

01 void function(int a)
02 {
03     char buffer[5];
04     char *ret;
05     ret=buffer+12;
06     *ret+=8;
07 }
08 int main()
09 {
10     int x;
11     x=10;
12     function(7);
13     x=1;
14     return 0;
15 }

书上说最后x的值是10,不是1,而我的结果恰恰相反。

接着用gcc产生汇编代码,在这里用 gcc -O0 -S 命令告诉编译器不采用任何优化措施,产生最原始的汇编代码,这样有利于我们分析,即使是采用-O1级优化的时候,汇编代码已经很难读了,大家可以试一试。

01 function:
02     pushl %ebp
03     movl %esp, %ebp
04     subl $16, %esp
05     leal -9(%ebp), %eax
06     addl $12, %eax
07     movl %eax, -4(%ebp)
08     movl -4(%ebp), %eax
09     movzbl (%eax), %eax
10     addl $8, %eax
11     movl %eax, %edx
12     movl -4(%ebp), %eax
13     movb %dl, (%eax)
14     leave
15 
16 main:
17     pushl %ebp
18     movl %esp, %ebp
19     subl $20, %esp
20     movl $10, -4(%ebp)
21     movl $7, (%esp)
22     call function
23     movl $1, -4(%ebp)
24     leave
25     ret

书上详细的解释了为什么结果是10,下面我来逐条分析。首先画一张内存图,同样处于简洁考虑,只画function函数附近的内存分布,不影响分析。

1、书上说:“为char buffer[5]分配内存时,由于32位存储器需要4字节对齐,因此一共为buffer分配了8个字节”。

由 leal -9(%ebp), %eax 代码可以看出,编译器实际上没有为buffer分配8个字节,而是只分配了5个字节,还有4个字节给了 char *ret,因此正好是9个字节,见图中0xEB – 0xE3部分。

2、书上说:“执行 ret=buffer+12后,ret指向返回地址”
实际上,从图上看出加12后指向的是%ebp的最高字节0xEF。

3、书上说:“执行 ret+=8后,返回地址的值加上了8个字节,而x=1这条语句占有8个字节,因此正好跳过,执行下一条语句 cout<<x ”。

实际上是把%ebp=0x00000108 的最高有效位 0x00加8了,因此运行时会产生“段错误”(是这个原因吗?求指教)

因此,书上长篇大论的分析在我的机器上是行不通的,不过还要注意2点:

1、现代的编译器通常都引入了“栈随机化”、“破坏检测”等多种手段来阻止缓冲区溢出的攻击,像书中所说的那样通过把某个指针+8,程序就从某条特定语句开始执行并不是那么简单就能实现的。

2、即使是相同的OS和gcc版本,在不同的CPU上生成的汇编代码是不一样的,运行的结果也不一样。例如,Core i5和 奔腾双核,在Core i5上运行结果是1,甚至都不会产生“Segmentation fault”的错误,而在奔腾CPU上结果为1,产生“段错误”提示。

总之,书上的代码也许在某个特定的、老版本的编译器环境下会发生,但是结果是不可重复的,而且,在不同机器上也会表现出不同结果。

最后,这篇文章的分析过程是我根据实际运行结果结合汇编代码猜测出来的,我对这方面也不是很懂,所以,如果哪位读者看出了其中有什么错误,非常诚恳的欢迎你指出,我也很想知道错误的原因,Thanks~

Tags: ,. 9,906 views
暑假终究是要过完的,再次感叹一下时间过得飞快!
翻一翻毕业照片,感觉好像也就是前几天发生的事情一样,熟悉的笑容,熟悉的校园,只是再也回不到那个计科07班了;
翻一翻暑假买的书,感觉好像也就是昨天才送来的一样,依旧没翻几页。
回想这个暑假,甚至都没写几行代码。
坐在书桌前的时间倒是不少,但真正好像也没看进去多少书,不然现在怎么回想不起来呢。
为毛会这个样子呢?(好像一直都这个样子的吧,囧) (more…)
Tags: . 10,405 views

Python 新旧版本之间的语法不兼容,导致iBus图标不显示,候选词框也不显示;导致Wicd无法启动。如下图所示。

问题产生:

由于Ubuntu默认安装了python2.6 ,后来我自己又装了python3.1,但是在终端里面输入python启动的是2.6版本的,这个是系统的默认,我们可以查看/usr/bin/目录,如图:

 

可以看到,python实际上是一个软链接,指向了python2.6 。我把它修改指向python3.1,这样输入python直接启动3.1了,方便我在终端下启动python3.1的交互界面。

这样做带来了文章开头所说的问题,一开始我没想到跟python有关,以为是什么配置文件出错了,于是网上google之,用了不少方法都没有解决问题,后来想:在终端下启动,应该会有一些出错信息吧。于是我输入wicd ,果然出现了错误提示:

File “/usr/share/wicd/daemon/wicd-daemon.py”,line 122
print “–no-autoconnect detected,not autoconnecting…”
SyntaxError: invalid syntax

看到这句话第一反应是:程序的源码出现语法错误了?不可能啊,以前还正常运行过。
于是打开源代码。

看到print 这一句我恍然大悟了,因为在python3.X中是不允许这样的语法的,这个是2.X的语法,于是知道肯定是修改python链接的指向导致了这个问题,解决办法就是修改回去喽。之后这两个程序都正常显示图标,也能正常使用了。

写这篇文章的意义在于:
1、blog很久没更新了,发一篇充数。
2、发现了另外一种导致iBus 和wicd 等依赖python的程序无法正常启动的原因。网上很多iBus的错误都集中在配置文件和环境变量方面,像我这样的python版本之间语法不兼容导致的错误倒是没看到,所以记录之。

Tags: . 5,218 views

学习python已经有2个月了,当然,是那种断断续续式的学习,囫囵吞枣的把《A byte of Python》看完了,大概知道了python的几个数据类型,了解了一些语法,然后又开始看《Dive into Python3》。

忘了提一句,我学的是Python3.X 而不是2.X。当初也是为了追求“最新”而选的,3.x和2.x的差别还是比较大的,很多时候遇到问题google一下发现网上的解决方法是2.x的,并不适用于3.x,无奈之下只好去翻官方手册。但是3.x的规范毕竟是以后Python语言的发展趋势,唯一的遗憾是目前很多第三方库还不支持3.x,比如图形库wxPython只支持2.x。

由于经常泡在豆瓣上,突然想起玩玩豆瓣的api,也顺便拿python练练手,学了这么长时间的python还没写过什么程序呢。于是就有了本文。

程序原理很简单,无非是通过api获取一些数据,然后在豆瓣返回的数据中提取有用的信息。输入豆瓣ID,然后显示昵称、个人简介等等。代码和截图如下。
Python老手以及熟悉网络开发的同学请无视~

 

 

 

 

 

 

import httplib2
import xml.etree.ElementTree as etree

h=httplib2.Http()
name=input('Douban ID:')

response,content=h.request('http://api.douban.com/people/'+name)
string=bytes.decode(content)

root=etree.fromstring(string)

title=root.find('{http://www.w3.org/2005/Atom}title')
bio=root.find('{http://www.w3.org/2005/Atom}content')
links=root.findall('{http://www.w3.org/2005/Atom}link')

for child in links:
   if child.attrib['rel']=='homepage':
       hp=child.attrib['href']
print('[江湖人称]: {0}'.format(title.text))
print('[自我简介]: {0}'.format(bio.text))
print('[个人主页]: {0}'.format(hp))

Tags: . 12,821 views

问题:有一个数组 31,-41,59,26,-53,58,97,-93,-23,84 。现在要求出它的连续子串的最大值。
比如,31,-41,59,26是它的一个连续的子串,他们的和为75。但是75并不是最大值,有一个子串 59,26,-53,58,97它们的和187才是最大的。

求解:《Programming Pearls》第77页开始一共给出了4种解法,前两种非常简单,是大多数人思考几分钟就能想出的方法,但是复杂度却很高,分别为O(n^3)和O(n^2)。后两种解法则非常巧妙,更神奇的是第四种方法居然只有线性复杂度O(n)!

解法1、解法2略。
解法3:分治法,复杂度为O(nlogn)。
分治法在结构上是递归的,在保证不改变原问题的条件下,将问题的规模减小,生成多个子问题,并多次递归调用自身来解决子问题,之后再将子问题的求解结果合并成原问题的解。

(more…)

10,790 views

第501页,Figure 15.6

在程序的第46行有dup2(fd[0], STDIN_FILENO),由于忘记了这个函数,于是翻到前面76页,有这样一段话:

dup2(fildes, fildes2);

If fildes is equal to fildes2, the dup2() function returns fildes2 without closing it. (more…)

Tags: . 6,307 views

大约是在2011年3月12号开始看这本APUE的,本来是想一边看一边写读书笔记,但是3月、4月都有很多的琐事要办,加上自己本身非常懒惰,写笔记的事就一直耽搁下来了。今天,书看到第15章了,一大半已经看过,加上现在比较闲,于是下决心一定要写读书笔记了,一方面是让自己把书细细的读,而不是囫囵吞枣式的看书;另一方面,博客要更新啊!不是放在那儿做摆设的啊!要有内容啊! (more…)

Tags: . 4,093 views
        锐捷和H3C这两家公司几乎垄断了国内所有高校的校园网系统,却至今不提供(或者不及时更新)类Unix系统下的客户端,使得为数不少的Linux用户因为不能上网而被禁锢在盗版Windows系统下。不过,幸好有民间的*nix爱好者开发出了多种客户端,但是因为各个学校的校园网配置情况不一样,导致这些客户端的通用性都不高,而且配置比较麻烦,其中我觉得比较好的一款是mentohust 。
(more…)
Tags: . 7,881 views

函数指针,顾名思义就是指向函数的指针,它与一般的指针有什么不同呢?我觉得,函数指针只是在定义的时候有一点不同,使用的时候,它就是一个指针该怎么用就怎么用。
int (*f)(int,double);
类似于上面的定义式就是函数指针的定义了。
从前往后分析,最前面的int 说明了这个所指向的函数的返回值,显然,这个被指向的函数会返回一个整型的值;(*f)()结构说明了这是一个函数指针,(int,double)说明了这个指针指向的函数的参数形式,即第一个参数是int型,第二个参数是double型,这时,我们脑海里可以想象有一个这样的函数 int function(int a,double b),并且有一个叫 f 的指针指向了这个函数(其实是指向了这个函数段的起始地址)。
有了前面的分析,就不难理解这个定义了 char * (*f)(double,double);

下面再来一个难一点的,int (*g[])(int ,int);首先这肯定是一个指针,但是[]怎么理解呢?按照数组的理解方法,例如int array[9]定义了一个9个元素的数组,每个元素都是int型,以此类推,这是一个函数指针数组,每一个数组元素的类型都是一个函数指针,他们都各自指向一个类似于 int func(int,int)的函数。

如何使用函数指针呢?我们知道,函数名其实就是指向函数代码段的一个指针,因此,f和function都可以看成是一个指针,都指向了内存中同一块代码段,所以,调用f(3,4.5)与function(3,4.5)是一样的,相当于是给原来的函数一个别名吧。当然,f是一个指针,理所当然可以对他进行“间接访问”,即 (*f)(3,4.5)

一般情况下对于函数指针的常见情况也就是以上这些了,那么函数指针到底有什么用呢?
>说实话,我自己写代码到目前为止还没用过函数指针,一方面是我对这个不熟悉,在coding的过程中不能灵活运用;另一方面函数指针可能确实不如其他语法常用,因此,我举一个《C和指针》中类似的例子。

例子一:不用函数指针的实现。

swith(op){

case ‘+’:add(x,y);break;

case ‘-‘:sub(x,y);break;

case ‘*’:mul(x,y);break;

case ‘/’:div(x,y);break;
}

上面的代码实现了模拟一个计算器对于x,y做加减乘除,那么用函数指针如何实现呢?

例子二:用函数指针实现。

首先我们需要声明函数,并对函数指针数组初始化。
double add(double,double);
double sub(double,double);
double mul(double,double);
double div(double,double);

/*声明函数指针数组*/

 

double (*op_fun[4])(double,double)={add,sub,mul,div};
现在我们可以这样使用:
result=op_fun[op](x,y);

OK,以上就是鄙人学习函数指针的一点点心得。

Tags: ,,. 6,405 views

现在家庭用的一般是中国电信或者中国移动等运营商的宽带业务,一般采用PPP协议,所以我们上网的时候都要先点“宽带链接”,只要填上用户名和密码,链接成功了就可以上网了。这是在Windows下的PPPoE拨号方式,微软把这个功能做的如此简单,不得不赞一个~
而到了Linux下,事情就没有这么简单了,

以我使用的Fedora Linux为例,除了填写用户名和密码,其关键之处是必须填写DNS地址!当然,不同地方的运营商设置可能不一样,但是以我的经历,分别在江苏和安徽两地的中国移动宽带上试过,都有这个问题。下面简单介绍一下设置方法,虽然Fedora有NetworkManager,但我一直都很讨厌这个工具,也没有试过,何况是在Linux下还是尽量多用命令行吧。

首先我们需要知道你所使用的ISP服务商的DNS号,如何得到呢?你可以打电话问,也可以找一台可以成功拨号上网的安装了Windows系统的电脑,在开始-运行-cmd进入命令行模式,打入ipconfig /all 这样就可以查看DNS地址了,把它记下来,一般有两个。

之后进入Fedora Linux的Terminal(命令行终端),用root权限输入:pppoe-setup,接着你就看到了如下图的界面,有很多选项需要你填,但是你只需要填上用户名和密码就行了,其他的全部写提示语里面的“默认”内容就行了,在这个过程中它也会让你填写DNS,可以先跳过,因为我们要填2个,而这里只能填一个。

等全部填完了会有一个你填写信息的“摘要”出现,然后输入“yes”,就会出现下图的一些内容。

这时,只差最后一步就完成了,我们再输入命令(同样需要root权限):vim /etc/resolv.conf ,然后把nameserver后面填上你自己的2个DNS地址,然后保存退出。

这时就大功告成了,再在命令行下输入(root权限):pppoe-connnect,就可以成功拨号了。

Tags: ,. 12,813 views

Programming Pearls Second Edition
Page 11

Problem C : Given a dictionary of english words,find all sets of anagrams,For instance, “posts”,”stop”and ”tops” are all anagrams of one another because each can be formed by permuting the letters of the others.

按照书上给出的解法,先对每一个单词生成相应的“签名”(“signature”),即把单词中的字母按照字母表的顺序重新排列,例如stop 重新排列成opst , 然后把有相同signature的单词归为一组输出。基本过程如下:

其中sign()函数用于生成每一个单词的”签名“,如何生成呢?由于每个单词的长度一般都很短(不超过10个字母)于是可选择用直接插入排序法。其他的数据结构和函数很简单,直接看代码吧!

(more…)

Tags: . 6,449 views

(博客又挂了,倒档以后这篇日志不在,就再发一遍吧…..)今天换了Windows7系统(以后还要折腾把Ubuntu的启动项引导弄出来),装了Chrome后无法同步书签,查了一下,发现是拜“墙”所赐,于是更改hosts文件,解决问题了。

(more…)

4,179 views

很久很久以前,动物们决定创办一所学校以应付日益变化的世界的需要。在这所学校里,教授一组由跑、跳、爬、游泳、飞行等科目组成的活动课程。为了便于管理,所有的动物学习所有的科目。 (more…)

8,114 views