流水帐 - 行者无疆 始于足下 - 行走,思考,在路上

流水帐

xiaohanyu posted @ Sat, 18 Sep 2010 09:33:38 +0800 in Life with tags XML python google , 2563 readers

4、5号从上海回来后,我自己的cpu就一直在以100%的负载在运行,每天平均睡不到7个小时,两周不到经历了各种事情,需要做个总结,否则下次再做总结恐怕写不下了。总结的风格依然是流水帐,技术加生活。

6号上班做了一个30+页的ppt,对自己两个月的实习成果做一个总结,系统描述了整个视频生产系统的设计、编程实现、工具使用细节等等,晚上部门会议做了报告,效果还不错。7、8两天写出了自己人生的第一个Python脚本,脚本的功能是分析nginx访问日志,提取用户信息,判断某个用户是否完整看完了某个视频等等,形象化一点,就是把类似于下面的log:

172.24.106.236 - - [01/Sep/2010:17:57:54 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:17:57:56 +0800] "-" 400 0 "-" "-" "-"
116.247.116.238 - - [01/Sep/2010:17:58:11 +0800] "GET /video/super_mpg_video/demo/taohua.f4v HTTP/1.1" 200 867480 "http://110.75.2.195/player/thvp/thVideoPlayer.swf?video=http://110.75.2.195/video/super_mpg_video/demo/taohua.f4v" "Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.1; Trident/4.0; SLCC2; .NET CLR 2.0.50727; .NET CLR 3.5.30729; .NET CLR 3.0.30729; Media Center PC 6.0; Tablet PC 2.0)" "-"
172.24.106.236 - - [01/Sep/2010:17:58:24 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:17:58:26 +0800] "-" 400 0 "-" "-" "-"
116.247.116.238 - - [01/Sep/2010:17:58:53 +0800] "GET /video/super_mpg_video/demo/taohua.f4v HTTP/1.1" 200 2097152 "http://110.75.2.195/player/thvp/thVideoPlayer.swf?video=http://110.75.2.195/video/super_mpg_video/demo/taohua.f4v" "Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.1; Trident/4.0; SLCC2; .NET CLR 2.0.50727; .NET CLR 3.5.30729; .NET CLR 3.0.30729; Media Center PC 6.0; Tablet PC 2.0)" "-"
172.24.106.236 - - [01/Sep/2010:17:58:55 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:17:58:56 +0800] "-" 400 0 "-" "-" "-"
172.24.106.236 - - [01/Sep/2010:17:59:25 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:17:59:26 +0800] "-" 400 0 "-" "-" "-"
172.24.106.236 - - [01/Sep/2010:17:59:55 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:17:59:56 +0800] "-" 400 0 "-" "-" "-"
172.24.106.236 - - [01/Sep/2010:18:00:25 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:18:00:26 +0800] "-" 400 0 "-" "-" "-"
59.42.126.48 - - [01/Sep/2010:18:00:51 +0800] "GET /video/super_mpg_video/20100826/moribingdu/moribingdu.f4v?th_key=4c7e3d82;1a7b6ebe;8292192f571cb7bbed3024e3998b5631&start=46582231&end=67158965 HTTP/1.1" 200 771638 "http://110.75.2.195/player/thvp/thVideoPlayer.swf?video=http://110.75.2.195/video/super_mpg_video/20100826/moribingdu/moribingdu.f4v&th_key=" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 1.1.4322)" "-"
172.24.106.236 - - [01/Sep/2010:18:00:55 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:18:00:56 +0800] "-" 400 0 "-" "-" "-"
172.24.106.236 - - [01/Sep/2010:18:01:25 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:18:01:26 +0800] "-" 400 0 "-" "-" "-"
116.247.116.238 - - [01/Sep/2010:18:01:43 +0800] "GET /video/super_mpg_video/demo/taohua.f4v?start=20998492&end=41622742 HTTP/1.1" 200 20624263 "http://110.75.2.195/player/thvp/thVideoPlayer.swf?video=http://110.75.2.195/video/super_mpg_video/demo/taohua.f4v" "Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.1; Trident/4.0; SLCC2; .NET CLR 2.0.50727; .NET CLR 3.5.30729; .NET CLR 3.0.30729; Media Center PC 6.0; Tablet PC 2.0)" "-"
172.24.106.236 - - [01/Sep/2010:18:01:55 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:18:01:56 +0800] "-" 400 0 "-" "-" "-"

转换成相应形象化的显示:



整个Python Script大概170多行,同时封装了几十行的Shell Script,算法是自己拍脑袋想出来的,具体描述可以另外写一篇技术文章了。脚本成形的过程渐渐体会到了Python的方便,结合了脚本语言的便捷性和高级语言的强大性,实乃居家旅行打家劫舍养家糊口之利器也。

9、10两天请假。9号睡了个小懒觉,然后去了趟校医院又开了一个星期的药,花掉100大洋左右,午饭后和同学会首,三人打车去西溪北园,准备CUMCM 2010。到了那边也没什么事情,下午3点半左右又走回玉泉,拿了实习记录本,去找导师签字。到了导师公司又等了半个小时,跟导师汇报下暑假实习的情况和自己要找工作的打算,简单谈了谈,骗了个90分回来。晚饭在西溪北园食堂吃的,饭后想到布袋也住在北园,约好去看她,巧的是碰到了哈哈、小包、破船一行,他们前脚刚要走,我后脚就跟过来了。由于布袋还要导尿,不太方便,我就一个人在北园里面转了几圈,买了个大西瓜和几桶泡面——西瓜给布袋,泡面是自己的。与布袋聊了有两个小时吧,听了她在千岛湖训练的很多故事,以及体制内运动员训练的一些内幕,加上他们从千岛湖逃窜的惊险一幕,走之前和布袋掰了手腕——当然我是不会输的,不过布袋的力气已经非常出色了,我敢说一般的男生不是她的对手;享受了阿姨自制的酸奶,一袋乳酸菌,放入保温瓶,自然发酵,有点西藏酸奶的味道,赞的。

11号早晨8点多拿到了CUMCM 2010的题目,A题是一道看似简单但非常复杂的几何计算题,B题就一句话——让你评估一下上海世博会的影响力。我倾向于选B题,因为看起来A题不太难——事实证明这个看起来不太难的结论是错误的,而且发挥余地有限;而B题的话只要找准一个切入点,成功的概率非常的大,即便不济,结果也总能忽悠出来的,不会太差。但是另外两名队友经过深思熟虑还是倾向于A题,于是少数服从多数,开始搞A题。第一天还是比较顺利的,我们顺利地解决了第一问,而第二问显然也是基于第一问的,这让我们每个人都面带笑容进入了梦乡——如此下去,第二天晚上就可以搞定第二问,第三天就有一整天的时间来写论文。

三人的分工基本上是这样,解题思路由三人共同商讨,然后lyf负责算积分表达式,ly负责matlab编程和主要的数据拟合,我对LaTeX比较熟,所以除了解题思路和简单的数据处理,主要是看文档、写文档。

第一天的乐观到了第二天的傍晚就变成了焦虑——第二问的积分表达式由于过于复杂以致无法积出来,ly和lyf用matlab算这个符号积分会卡住,我说matlab的符号计算比较弱,于是我在linux平台上找到了著名的符号运算软件maxima,简单配置了Emacs+imaxima,来算这个积分,maxima比较智能,会给你一些提示,比如提示你某个变量是positive, negative or zero? 因为这个变量值不同积分结果也不同。总之积分表达式很复杂,我用maxima算,不同的条件算出来也不一样,有时候算出来竟然是个复数!探索良久,符号积分的方法宣告失败,于是我们转而研究能否用数值积分的方法来算出一部分数据,打表拟合,然后根据拟合的结果判定拟合曲线和实际数据的相似性,确定最后的方程参数。但数值积分是一个比较棘手的东西,除了调用已有数学软件的方法,我们没有能力自己去写。ly和lyf研究matlab,我则找到了maxima的数值积分方法romberg,但是最后也宣告失败,至此,已经是第二天晚上10点多了……士气开始变的低落,ly躺在床上,lyf上网看看别的东西,我也在打酱油般地继续着一些无谓的探索——对于A题,我们已经黔驴技穷,换B题,还剩一天一夜,但是也有些来不及了——更重要的是大家都不太想做下去了。

12号早晨大家都睡到自然醒,心情也不是太好——毕竟没有做出题目是件挺没面子的事情。我提议我们上午再按照打表的方法重新计算一下,然后大家随便算算,到中午基本上就彻底放弃了……于是乎我们就解脱了——ly开始玩一些网页小游戏,lyf上网或者单机游戏,我呢,看完了《当幸福来窍门》,修改了一下午自己的简历,找Ouka帮忙挑了挑刺,投了华为、网易等四五家公司。

13号早晨老师打来电话,问我们论文咋么还不交,我们就坦白交代了说自己没有做出来,论文也没有写,于是我们的CUMCM 2010打酱油之旅就这样结束了。顺便提下这里提供的盒饭还是很不错的,虽然题目没有做出来,但还是赚了三天的伙食——太邪恶了……

离开西溪后冒着小雨骑车到了公司,刚好赶上早会。然后就开始了工作——看,角色转换如此之快。晚上google的宣讲会加现场笔试,七点半到达现场,果然人山人海。8点挤到了位子,开始笔试。笔试总共10道选择和3道编程算法题目,时间是90分钟。选择题大概记得的几道:

  1. 以下各种排序种哪几种是稳定排序?
  2. 二叉树的前序、中序和后序遍历中,已知哪两种可以唯一却确定一棵二叉树?
  3. {1, 2, 3, ..., 20}集合中,挑选出3个数字,使得这3个数字不完全相邻,如{1, 2, 3}, {4, 5, 6},有多少种挑法?
  4. 32位机器表示的有符号数最小值是多少?
  5. Unix文件的一道题目?
  6. 1024!的结尾有多少个零?
  7. c语言指针的一道题?
  8. 数组中寻找中位数的算法复杂度是多少?
  9. 访问内存性能的一道题目。
  10. 忘了……

剩下的3道编程题目,第一道题目是编程求两个数组集合A[m], B[n]的交集;第二道是离散事件模拟,内容和严老那本经典的《数据结构——c语言版》第3章栈和队列的最后一节一样;第三道应该是桶排序,就是给定n个数,大小均在[1, n^2-1],在保证时间最优的前提下尽可能地优化空间。

google笔试的结果就是我理所当然的被bs了,虽然我觉得答得还算凑合吧,不过连面试的机会都不给,这个招聘也显得有点酱油的味道了——当然,比如像今年的百度之星冠军hh,据说连google的面试官都称之为大牛了,这是另类。

剩下的时间主要是借工作的时间学习,修炼秘密武器,看完了w3c school上的大部分教程,重点是关于XML的,XSL、XPath、XQuery、DTD、Schema等等,研究了Unicode编码的基本知识(UTF-8、UTF-16、UTF-32,Big-Endian,Little-Endian等),研究了python读写excel文件的几个模块(xlrd, xlwt, xlutils, pyexcelerator)和python有关xml的一些模块(lxml, jaxml等),基本完成了《Learning Python》,除了Class看得比较少,剩下的就是熟悉一些常用的mobule,多写写Python脚本,有时间再了解了解Python知名的开发框架,差不多了,剩下的按需学习。

14号是好友Ouka同志的22岁生日,四年前的今日我拿到了化学竞赛的一等奖,收到Ouka祝福短信和亲切指导若干,四年后的今日,我在公司实习,趁午休时间简单改了个小程序,一程序员间独特的方式送出我的生日祝福。Happy Ouka, Fight Ouka。

17号中午回到玉泉,参加了网易有道搜索的机试,两道题,两个小时,zoj平台,20个测试点,总分270,有点类似于NOI,是按照score排名的。结果还是不错的,许久为碰c++,还是拿下了260分,整场50人排名15%左右吧。两道题目如下:

 
奇偶矩阵

Time Limit: 1 Second      Memory Limit: 32768 KB



给定一个N行,M列的正整数组成的矩阵,求其中的一个子矩阵,使得奇数的个数与偶数的个数差值的绝对值最大

Input

每个文件包含一个测试数据。第一行是两个整数,N,M 表示矩阵的大小 1<=N,M<=100。 接下来N行,每行M个正整数,对应为矩阵中的元素,所有的数不超过2^30。

Output

输出包含一行,为子矩阵中奇数个数与偶数个数差值绝对值的最大值。

Sample Input
				3 3
1 2 3
3 2 1
1 1 1
Sample Output
				5
最大和

Time Limit: 5 Seconds      Memory Limit: 32768 KB



给定两个整数数组分别为A,B。你可以从A,B中分别挑选一个数,将他们的乘积作为你的得分。你可以挑选任意次,但是每个数只能被挑选一次。 求你最后所能得到的分值和的最大值,你的初始分数为0

Input

每个文件包含一个测试数据。 第一行是一个正整数N,为数组A的长度。 第二行为N个整数,分别为A中的元素。 第三行是一个正整数M,为数组B的长度。 第四行为M个整数,分别为B中的元素。 1<=M,N<=10^6

Output

输出结果包含一行,为你所能得到的最大的分之和。A,B中的数及最后的结果均不超过2^30

Sample Input
				4
3 2 6 1
3 
2 6 3
Sample Output
				49

第一提看上去比较悬,但仔细一想其实是个最大子段和的问题,核心算法可以参考ZOJ 1074——我就是这么干的……应用之前需要预处理,就是扫描下整个矩阵,然后用1表示奇数而用-1表示偶数,最后算“矩阵的最大子段和”,这样做下来基本上可以通过4-5个测试点,弥补的方法就是对称性,考虑到奇数和偶数的平等性,用-1表示奇数而用1表示偶数再算一下。整个程序如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define size 102

int DP(int a[],int n);

int main(void)
{
    int m, n;
	int i, j, k;
	int he;
	int max1, max2;

    int a[size][size];
	int b[size][size];
    int sum1[size];
	int sum2[size];

    scanf("%d%d",&m, &n);

    for(i = 1; i <= m; i++)
        for(j = 1; j <= n; j++)
		{
            scanf("%d",&a[i][j]);
    		
			if (a[i][j] % 2 == 0)
			{
				a[i][j] = -1;
				b[i][j] = 1;
			}
			else
			{
				a[i][j] = 1;
				b[i][j] = -1;
			}
		}

    max1 = max2 = -200000000;

    for(i = 1; i <= m; i++)
    {
        memset(sum1, 0, sizeof(sum1));

        for(j = i; j <= m; j++)
        {
            for(k = 1 ; k <= n ; k++)
                sum1[k] += a[j][k];

            he = DP(sum1, n);

            if(he > max1) 
				max1 = he;
        }
    }
    
	for(i = 1; i <= m; i++)
    {
        memset(sum2, 0, sizeof(sum2));

        for(j = i; j <= m; j++)
        {
            for(k = 1 ; k <= n ; k++)
                sum2[k] += b[j][k];

            he = DP(sum2, n);

            if(he > max2) 
				max2 = he;
        }
    }

	if (max1 > max2)
		printf("%d\n",max1);
	else
		printf("%d\n", max2);
    return 0;
}

int DP(int a[],int n)               
{
    int i, f[101];
    int max = -200000000; 
	
    for(i = 2, f[1] = a[1]; i <= n; i++)
    {
        if (f[i - 1] > 0)         
            f[i] = f[i - 1] + a[i];         
        else
            f[i] = a[i];              
    
        if (f[i] > max)               
            max = f[i];
    }

    return max;
}

第二题的思路比较清晰了,需要注意的是负数的情况,考虑四个正数a \leq b, c \leq d,显然ac + bd \geq ad + bc,就是要得到最大值,大大相乘优先。如果遇到负数,负负为正是可以考虑的,正负相乘则需要舍弃。按照这个原则进行排序、分割,在处理下去就不难了。有一个Test Case是Segmentation Fault,最后找到原因了,可惜没有时间了,程序如下:

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

int main()
{
	int m, n;
	vector<int> a;
	vector<int> b;

	int i, j;
	int item;
	int s, sum;
	int ai, bi;

	cin >> m;
	for (i = 0; i < m; i++)
	{
		cin >> item;
		a.push_back(item);
	}

	cin >> n;
	for (j = 0; j < n; j++)
	{
		cin >> item;
		b.push_back(item);
	}

	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	
	for(i = 0; i < a.size(); i++)
	{
		if (a[i] >= 0)
		{
			ai = i;
			break;
		}
	}

	for(i = 0; i < b.size(); i++)
	{
		if (b[i] >= 0)
		{
			bi = i;
			break;
		}
	}

	sum = 0;
	for(i = 0, j = 0; (i < ai) && (j < bi); i++, j++)
	{
		sum += a[i] * b[j];
	}

	for(i = a.size() - 1, j = b.size() - 1; (i >= ai) && (j >= bi); i--, j--)
	{
		sum += a[i] * b[j];
	}

	cout << sum << endl;

	return 0;
}

最后的结果还是不错的,这也让我感到惊喜,好久都没有如此开心过了,期待面试通知。

另外,现在所在的实习公司已经有了口头上的offer,给我一个月的时间考虑,在实习结束之前给答复,待遇和淘宝应届是差不多的,而且创业阶段,发展空间还是非常大的,我在部门也受到重视,我相信继续实习一年,毕业后我会处于一个比较高的起点,这样的结果,对于我这么一个挂科达到两位数的刚毕业的本科来说,应该算很不多的了,但是我还是在犹豫。老实说我还是想去大的公司体验两年,体验下大的平台和大的气质;妈妈每次打电话都让我回北京,家近、方便。所以我还在继续投简历。

18号下去2:00-3:00,百度大牛徐串的技术讲座;19号下午2:00,百度内推小型见面会;20号晚6:30,MSTC主席pluskid大神的小课堂,各种大牛,膜拜。

除了这些,印度宝莱坞的电影《三个傻瓜》前前后后看了4遍,哭笑中带来人生的思考;看了《当幸福来敲门》,我喜欢那种“He must have a nice pants”的自信;看了柴静的《面对面》——李连杰“壹基金危机”,“侠之大者,为国为民”,李连杰当之无愧;“方向对了,就不怕路远”,加油吧,Lox!

2lovelycake said:
Sat, 18 Sep 2010 22:46:05 +0800

我走前也做了个礼物,想想又懒得送了就堆在地上,结果估计手艺太差了,被我室友当垃圾扔了,囧。还是你比较勤劳啊。

看的我好晕啊,没看明白你到底是在哪里实习…………给我解答一下吧
来上海实习吗?

Avatar_small
Lox said:
Sun, 19 Sep 2010 03:17:16 +0800

给谁的礼物阿?我改个程序花了1个多小时吧。也不难。

实习公司是华数淘宝,华数和淘宝的合资公司。没事不去上海实习。

2lovelycake said:
Fri, 24 Sep 2010 01:34:48 +0800

为啥不来上海实习啊,王敏不是在上海吗?搞不懂

Avatar_small
Lox said:
Sat, 25 Sep 2010 18:01:36 +0800

我又不是大牛,不是自己想去哪里就能去哪里。
再说两人一定要时刻在一起吗?未必。

2lovelycake said:
Sat, 25 Sep 2010 19:02:57 +0800

也不是,可是会很想,能在一起要珍惜

Avatar_small
Lox said:
Sat, 25 Sep 2010 19:32:54 +0800

所以我会把人带走。


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee