Aug 22

windows下的批量重命名 不指定

felix021 @ 2012-8-22 22:23 [IT » 其他] 评论(2) , 引用(0) , 阅读(5025) | Via 本站原创
可能很多同学不知道Windows是自带这个功能的。至少从WinXP开始就有。操作要领:

0. 批量重命名的文件应该在一个文件夹内。

1. 选择所有需要被重命名的文件。全选(CTRL+A),或拖动/用shift选择选择一个区间,或按住CTRL一个一个点,都可以。

2. 使用鼠标右键选择你希望被重命名的第一个文件,输入新的文件名。注意,新的文件名如果不带编号(如a.txt),那么会按顺序改成 a.txt, a (1).txt ... a (5).txt,如果带编号(如 b (3).txt,注意编号只能用圆括号包起来),则编号会按顺序增加:b (3).txt, b (4).txt ... b (11).txt。

3. 回车,OVER。

功能很贴心,但是半残,有时候不满足要求,在没有安装额外的语言的情况下,可以用类似如下的vbs来应急:
Set a= WScript.createObject("WScript.Shell")
WScript.sleep 1000
For i = 1 to 23
  j = i
  If i < 10 Then
    j = "0" & i
  End If
  a.sendkeys "{DOWN}{F2}"    '向下,F2(重命名)
  a.sendkeys "TBBTs02e" & j  '文件名, win7下就不用再  & ".rmvb" 了,但是xp需要
  a.sendkeys "~"            '回车
  WScript.sleep 200
Next
Aug 21

博客迁移记#3 不指定

felix021 @ 2012-8-21 09:59 [杂碎] 评论(1) , 引用(0) , 阅读(4596) | Via 本站原创
去年 czyhd同学 推荐的BurstNet的VPS用了正好一年。到上周一之前,总体来说是很满意的,性价比高,带宽和延迟基本满足要求。但是上周一空间突然无法访问了。我以为是偶然的情况(GFW/公司网络封堵/母鸡整修等),但是却收到一封Reseller发来的邮件,说是BurstNet怀疑我利用VPS乱发垃圾邮件,还附上了一份pstree的输出,其中显示smtpd服务启动了32个,要我对此作出解释。

由于对方是万恶的美帝,还要经过日李万基的reseller,所以往来3封邮件花了三天的时间,仍然没有解决问题,怒了,直接在 Ramhost 另外买了个VPS,基于KVM技术,256M RAM + 7GB HDD,$4.99/Month(可以使用paypal转网银以RMB支付)。看起来参数是不如原先安个OpenVZ的512M+20GB(35元/月,买10送2),但是由于Ramhost承诺不超售,因此实际性能(CPU、内存、网络)应该是要超过BurstNet,而价格上也没有太大的差别。

折腾了两三天,目前装上了Ubuntu 12.04 Server x86_64,nginx + php-fpm + mysql, sshd, pptpd, postfix, denyhosts, 稳定运行了一段时间以后,free的输出大约是
引用
felix021@felix021:~$ free -m
            total      used      free    shared    buffers    cached
Mem:          239        220        19          0        14        133
-/+ buffers/cache:        72        167
Swap:          490        24        466

总体来说还是比较满意的,实际速度也比原先的vps快,尤其是刷网页的时候很明显。

在安全方面,VPS什么都得自己搞,比较头疼。

denyhosts已经往/etc/hosts.deny里面加入了7个ip,都是试图ssh登录失败多次的。

在邮件方面,这次特别注意了,使用iptables限制只能是本地ip才能连上tcp#25。
    iptables -A INPUT -j ACCEPT -p tcp --dport 25 -s 127.0.0.1       
    iptables -A INPUT -j REJECT -p tcp --dport 25

在web方面,大概分析了下头天的nginx log,发现有大量的异常访问,于是根据UA屏蔽了许多抓站请求(不是常见的Spider)。比较特殊的是被GFW屏蔽的那个 /t ,目前仍有少量请求,而且UA为空,看起来像是GFW的回访,所以果断屏蔽之。

大概就是这样。

p.s. 遇到一件很不靠谱的事情:昨晚Ramhost给我换了个IP,居然没有任何通知!折腾了半天,看到管理面板上的IP有异我才发现,果断发TICKET质问他们,看他们如何解释,艹。

p.p.s. 奇葩解释:"You are mistaken. Your IP address was and has always been 199.180.255.30, Seeing as your account is only 4 days old we have absolutely no reason to need to change your IP address. We have not and will not change your IP address like that."  好吧。怪我没有留下证据。
Aug 17
对ssh用得比较多的同学应该知道通过建立信任关系来免除输入密码的麻烦:

在A机器上执行:

$ ssh-keygen -t rsa (各种回车)
$ ssh-copy-id -i ~/.ssh/id_rsa.pub USER@B_ip

然后在A机器上 ssh USER@B_ip 就可以免密码使用USER用户登录B机器了。

实际上第二步操作是将 A 机器该用户的公钥(id_rsa.pub)追加到B机器的 ~/.ssh/authorized_keys 文件末尾中去。

当A机器访问B时,如果B机器的sshd能够在/home/USER/.ssh/authorized_keys中找到对应的公钥,就认为A机器具有B机器的USER用户访问权限,于是就直接让A机器以USER身份登录。

但是上周在线上某台机器进行操作时却发现这一机制失效了。通过该机制,A=>B可登录,但是B=>A失败,甚至A=>A也失败(B=>B却成功)。虽然问题很奇怪,但说明问题出在A机器上。

首先是 diff 了A、B两台机器的 /etc/ssh ,发现完全相同,所以不是配置的问题。

然后查看 ssh -vv localhost
引用
....
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /home/felix021/.ssh/id_rsa
debug2: we sent a publickey packet, wait for reply
debug1: Authentications that can continue: publickey,password
debug1: Trying private key: /home/felix021/.ssh/id_dsa
debug1: Trying private key: /home/felix021/.ssh/id_ecdsa
debug2: we did not send a packet, disable method
debug1: Next authentication method: password

而在B机器上,we sent a public key packet, wait for reply 之后则是紧跟着"debug1: Server accepts key: pkalg ssh-rsa blen 279"。由此可以看出,是A机器的sshd不认可publickey。

至于为什么不认可,在google上查了许多,毫无头绪,直到使用类似“ssh publickey ignore debug diagnose”这样的关键词,发现这个页面,其中的第二条和第六条给出了解答:
引用
2. Debugging on the remote host by running sshd in debug mode: Run ‘/usr/sbin/sshd -d -p 2222′ on the remote host and connect to it. ’2222′ here is the port number of the sshd process you started on the remote host.

6. Check the permissions on your home directory, .ssh directory, and the authorized_keys file: If your ssh server is running with ‘StrictModes on’, it will refuse to use your public keys in the ~/.ssh/authorized_keys file. Your home directory should be writable only by you, ~/.ssh should be 700, and authorized_keys should be 600.


通过执行 /usr/sbin/sshd -d -p 2222 (在2222端口启动一个带debug输出的sshd) ,然后 ssh -vv localhost -p 2222 ,可以看到sshd输出了一行
引用
Authentication refused: bad ownership or modes for directory /home/felix021

正好与那第六条相对应,再检查一下 /home/felix021 ,其权限是其他组可写。

最终解决方案:将用户home目录的权限改为0755,登录成功。
Aug 8
这是第一个支持IBM PS/2和1.44MB 3.5寸软盘的DOS版本,可能是在家用PC上比较容易用虚拟机模拟的最古老的微软系操作系统。隐约记得这里头还有个BASICA解释器,比QBASIC还要老很多的那种,类似于文曲星上面的那个版本。
下载文件 (已下载 1056 次)

以前(大一之前)很喜欢玩这些东西,收集了不少东西,包括3.31, 6.22, win98/me/xp的DOS启动盘, windows 1.0 ~ 3.2(主要来自曾经的“bear5的软件地摊”),还有很多dos下的工具,tw ucdos 之类,甚至还有个VB DOS版。折腾bat、config.sys这些东西,玩得乐此不疲。如今突然想起,却发现它们静静地躺在硬盘的那个角落已经好多年了。

谨以此纪念那些二逼的时光。
Jul 26
如果到Google去搜索,"How to find out which process is listening upon a port"这是第一篇文章。

事实上大部分文章都是告诉你,要么 lsof -i :80 要么 netstat -antulp | grep :80 就能找到httpd。

可是如果就这样的话,这篇BLOG就变成微博了。

事实上我的目的是希望通过编程找出这个PID,而不是调用某个命令。

第一个尝试是去看lsof的源码。找源码容易,apt-get source lsof 就行。但是源码跟大部分linux软件包一样,看起来相当晦涩。

第二个尝试是Google,但是能找到的都是命令版的。

第三个尝试是stackoverflow,没有直接搜到问题,于是准备自己提问,但是在“Questions that may already have your answer”里头找到了一篇“How to get the pid of a process that is listening on a certain port programmatically?” ( http://stackoverflow.com/questions/10996242 )。

Answer给出的步骤非常清晰:与netstat的实现一样,先读取 /proc/net/tcp 这个文件,第二个字段(local_address)冒号后面的是端口号(十六进制),第四个字段st为0A表示TCP_LISTEN,第10个字段是十进制的inode编号;而通过遍历 /proc/PIDs/fd 下面的链接,找到链接到形如 socket:[端口号] 的fd进行对比,就能知道哪些进程与该端口有一腿。

我在机器上监听的是8888端口,换成hex是22B8,但是在 /proc/net/tcp 中却找不到。幸而那篇文章的第二个Answer给了个提示,于是 strace /usr/sbin/lsof -i :8888 ,发现它还打开了 /proc/net/tcp6 (也就是对应IPv6的那个文件了)。过去一查,果然有,再顺着inode,对照lsof的结果一看,的确符合。

于是再去grep一把 lsof 的源码目录,发现在 00FAQ 文件中的 10.2.2 一节就说明了 lsof 的实现机制:
引用
Lsof identifies protocols by matching the node number associated
    with the /proc//fd entry to the node numbers found in
    selected files of the /proc/net sub-directory.  Currently
    /proc-based lsof examines these protocol files:
        /proc/net/ax25      (untested)
        /proc/net/ipx      (needs kernel patch)
        /proc/net/raw        /proc/net/raw6
        /proc/net/tcp        /proc/net/tcp6
        /proc/net/udp        /proc/net/udp6
        /proc/net/unix

看来在 Linux 下的实现方式确实只有这一种。顺便提一下,Stackoverflow上面的另一篇 http://stackoverflow.com/questions/4041003/c-what-process-is-listening-on-a-certain-port-in-windows 提到了,在Windows下可以用GetExtendedTcpTable/GetExtendedUdpTable来实现。

最后附上PHP实现的源码(这个代码用C/C++写确实蛋疼)
<?php

$filelist = array("/proc/net/tcp6", "/proc/net/tcp"); //udp/unix的就先不管了

$port2inode = array();

foreach ($filelist as $file)
{
    $lines = file($file);
    array_shift($lines);
    foreach ($lines as $line)
    {
        $values = split(" +", $line);
        list($addr, $port) = explode(":", $values[2]);
        $port = hexdec($port);
        $port2inode[$port] = $values[10];
    }
}

if ($argc < 2)
    die("usage: php {$argv[0]} PORT\n");
$findport = $argv[1];

if(!isset($port2inode[$findport]))
    die("$findport not listened\n");

$procdir = scandir("/proc");
natcasesort($procdir);

foreach ($procdir as $pid)
{
    $path = "/proc/$pid/fd";
    if (!is_readable($path) || !is_numeric($pid) || !is_dir($path)) continue;
    $dir = scandir($path);
    foreach ($dir as $file)
    {
        $link = "$path/$file";
        if (!is_link($link)) continue;
        $real = readlink($link);
        if (substr($real, 0, 7) == "socket:")
        {
            $port = substr($real, 8, -1);
            if ($port == $port2inode[$findport])
            {
                echo $pid, ": ", readlink("/proc/$pid/exe") . "\n";
                continue;
            }
        }
    }
}
?>
Jun 30

二进制偶矩阵 不指定

felix021 @ 2012-6-30 22:34 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(5330) | Via 本站原创
这是2012年百度实习招聘非技术类的某道笔试题。

给一个5×5的矩阵,每个元素只能是0或者1。

请问,有多少种不同的矩阵,能够满足每一行、每一列都有偶数个1?

==== 分割线 ====

乍看这个题目,觉得是数学题。画了个5*5的矩阵,试图填几个数字进去看看是否可以推出一些结论。果断失败。

然后想了下,这题如果枚举的话,也就是2的25次方,大约3200万这个规模,不是很夸张。于是决定暴力搞一下。

最简单的做法就是
for (i = count = 0; i < 2<<25 - 1; i++) check_even(i) && count++;
这个check_even(i)里头把 i 当成一个25bit的二进制数字,并转换为对应的5*5矩阵,判断其每一行和每一列是否满足要求。(p.s. whusnoopy的做法是直接使用位运算,更简单,不过思路就断了。。)

一个不难想到的优化是,在for之前先把每一行给枚举了,这样就不需要在check_even里面每次进行转换,只需要从 i 中取出对应的bits,就可以直接找到每一行。

更进一步,由于题目要求每一行都是偶数个1,所以可以进行剪枝——在枚举的时候只需要保留有偶数个1的情况就行了,枚举出5行,然后判断每个列。很容易计算,每行5个bit,偶数个1的情况是2^4=16种。于是需要枚举的矩阵数量降至16^5。

再进一步剪枝——题目要求所以列是偶数,那么在已经确定前4行的情况下,第5行是可以直接推出来的,需要枚举的矩阵数量降至16^4。但还需要做的事情是,判断第5行是否有偶数个1。

到了这一步,豁然开朗——因为很容易证明,第5行必然是偶数个1:
  1) 每一列都是偶数个1(ABCDE都是偶数),所以矩阵中必然有偶数个1(F=A+B+C+D+E为偶数)
  2) 前4行都是偶数个1(HIJK都是偶数),所以第5行必然是偶数个1(L=F-H-I-J-K为偶数)
  (p.s. 这个证明是WHUMSTC群里某同学给出的,非常清晰,所以我就不给我自己那个很挫的证明过程了)

于是开头的直觉获胜,问题的答案就是:16^4,也就是(2^4)^4。

==== 分割线 ====

扩展:

1. 如果矩阵的大小是 N×N ,甚至是 M×N 呢?

    根据上述结论,很容易推知,对于M*N的矩阵,结果是2^((M-1) * (N-1))。

2. 如果要求满足每一行、每一列都有奇数个1呢?(whusnoopy提出)

    这个结论就不那么直接了,对M*N有一定的限制。
May 20
从哪儿说起呢?我想了想,从 gets 说起可能最好。

初学C语言的时候,如果要输入一行字符串,该怎么办?看书,或者找老师,或者找学长,通常得到的答案是gets。用法很简单,似乎也很好用,但是很不幸,这个函数很危险。因为 gets 对输入不进行任何的限制。如果对应的字符数组只有100个字符,而面对的输入是1万个字符,那么几乎毫无疑问,这个程序是要崩溃的,除非运气特别好,或者……

或者给出的输入是经过精心设计的,例如一段shell code,及其对应的跳转地址。对于常见的计算机体系来说,函数调用时,返回地址是在栈上的,通过精心设计输入,使得溢出数据中的跳转地址好正好覆盖了该返回地址,于是函数在返回时不是如预期般回到调用者处,而是跳转到攻击者给出的shell code处,使得攻击者获得了额外的权限。

这就是典型的溢出攻击。

为了防止这种情况的出现,在C库函数中,许多对字符串操作的函数都有其"n兄弟"版本,例如strncmp,strncat,snprintf……兄弟版本的基本行为不变,但是通常在参数中需要多给出一个整数n,用于限制操作的最大字符数量(本句不够严谨,详情参见各函数的说明)。

这是技术上的解决方案。只是,代码都是人写出来的,总会有对溢出缺乏概念的人,写出令人蛋疼的代码。于是一些公司,例如(听说)腾讯,建立了一套规则,对提交的代码进行扫描,若发现使用了非“n兄弟”版本,就会给对应的码农一定的惩罚措施,从而在管理上降低此类问题出现的可能性。

加强管理当然是好事,但是也给某些有强迫症的码农带来了不便:因为strlen没有n兄弟版本,坑爹啊!事实上,更坑爹的是strcpy,在c语言标准里,它不但没有n兄弟版本,甚至还有一个“冒充”的"n兄弟"版本——也就是 strncpy 。

strncpy 到底做了什么事情呢?它基本上等同于这样几行代码:
char* strncpy(char *dest, const char *src, size_t n){
    size_t i;
    for (i = 0 ; i < n && src[i] != '\0' ; i++)
        dest[i] = src[i];
    for ( ; i < n ; i++)
        dest[i] = '\0';
    return dest;
}

比较诡异的两件事情是:

1. 如果src的前n个字符里面没有'\0',那么它不会在末尾补上这个结束符

2. 如果拷贝的数据不满n个字符,那么它会用 '\0' 在末尾填充

以 strcpy 的行为来理解它,只会感到很蛋疼:第一点很可能会造成此后代码的数组越界访问,而第二点则是对cpu资源的浪费。

事实上,完全是因为历史的原因,造成了这样的误会。在第七版的UNIX文件系统中,每个inode结构体中包含的每个entry(对应文件或下级目录)只有16个字节,其中前两个用于标识inode,剩下的14个用于保存文件名。由于文件名最长只能有14个字符,所以在设计上,末尾不足的字符用'\0'来填充;如果达到14个字符,则不需要结束标志。

众所皆知,c是为unix而生,所以这就是strncpy的原始目的:定长字符串 的拷贝。对应的代码,很自然地,可以这样写:
strncpy(inode->d_name, filename, 14);

那么如果确实需要一个strcpy的n兄弟版本该怎么办呢?最简单的办法是用snprintf:
snprintf(dest, n, "%s", src);//注意,不能直接用src来替换"%s"

p.s. 其实还有个 strlcpy ,只可惜它是OpenBSD 2.4引入的,并非C标准中的函数,适用范围较窄。

参考资料:
http://www.lysator.liu.se/c/rat/d11.html
http://stackoverflow.com/questions/1453876/why-does-strncpy-not-null-terminate
http://stackoverflow.com/questions/2884874/when-to-use-strncpy-or-memmove
http://blog.liw.fi/posts/strncpy/
http://pubs.opengroup.org/onlinepubs/9699919799/functions/stpncpy.html
May 16

说说机器学习 不指定

felix021 @ 2012-5-16 00:29 [IT » 其他] 评论(0) , 引用(0) , 阅读(4626) | Via 本站原创
为了论文搞了把机器学习的东西,虽然了解得非常肤浅,但是窥探了一下这个领域也还是很有收获。

对于遇到的问题,传统的思路是通过建模,然后使用对应的算法予以解决。但是对于很多问题,建模本身是不实际的,例如语音识别、计算机视觉等等。而机器学习算法的思路则不同,通过对现有的数据进行分析和统计,得到一组参数来逼近真实的模型,从而能够处理未知的数据。

我的论文里主要是使用SVM来解决简单的二分类问题。SVM,Support Vector Machine的简写,也就是“支持向量机”,很早以前有“听说过”,但是之前完全没有概念。这次在yihong妹妹的推荐下,看了faruto大牛写的《SVM入门精品系列讲解》,能大致在原理上明白svm分类的机制。之所以称faruto为大牛,主要是因为这个讲解系列非常地浅显易懂,没有卖弄玄虚,即使是我这样没学好数学的人,也能够非常容易地弄懂。

由我来归纳的话,svm的基本思路应该是,将每个样本x当作一个N维向量(也就是N维空间中的一个点),通过某种方式找到该空间中的一个超平面w * x + b = 0,将样本分成两类。例如二维空间中的点,可以用一条直线分成两类,而三维空间的点,可以用一个平面来分。由于并不是所有问题中,样本在N维空间中都可以被超平面分为两类,因此通过使用引入核函数将样本映射到更高维的空间、并引入松弛变量以忽略噪音数据等方式,达到对数据进行分类的目的。

可能看起来有点抽象?没关系,把那个系列(并不是很长)看完就懂了,其实不难理解。在此基础上,svm方法还有许多扩充,例如对不平衡样本集的处理、One-Class SVM、在线SVM训练等等。

想要使用svm算法的话,非常幸运,台湾大学林智仁(Lin Chih-Jen)副教授主持的 libsvm 项目提供了c/java/python/matlab 的接口,直接拿来就能用了,非常方便。

在学习svm的过程中,也顺便看了一些其他的机器学习算法,这里也大致列一下。

HMM,隐马尔可夫模型。李开复的主要学术成就(之一?),就是使用了HMM开发出世界上第一个大词汇量连续语音识别系统 Sphinx。根据Google研究员吴军的数学之美 系列三 -- 隐含马尔可夫模型在语言处理中的应用,使用HMM来进行语音识别是李开复的师兄提出的。

HMM算法是基于贝叶斯公式的。贝叶斯公式在机器学习中是一个非常基础的理论。关于这个,推荐阅读《数学之美番外篇:平凡而又神奇的贝叶斯方法》

神经网络算法,通过模拟神经元的工作方式来对数据进行学习,使用多个神经元构成一个网络,并适当加入反馈机制。详情参考神经网络编程入门

遗传算法,通过模拟染色体复制、基因变异等机制,使状态不断”进化“,从而尽量逼近最优值。详情参考遗传算法入门

模拟退火,非常简洁、实用的一个算法,基于“爬山算法”(不断逼近离当前点最近的极值,贪心)改进而来,通过引入随机化以获得跳跃到其他极值区域的机会,从而尽可能获得更高的极值点。详情可参考《大白话解析模拟退火算法》

此外还看到了决策树、K-mean聚类等算法,不过没有细看,只是大致扫了一眼,就不扯了。

以上给出的链接大都是讲解得非常浅显易懂的文章,非常推荐阅读。
分页: 14/97 第一页 上页 9 10 11 12 13 14 15 16 17 18 下页 最后页 [ 显示模式: 摘要 | 列表 ]