Xavier's Blog

使用Jython操作HBase

| Comments

之前使用Python的PLY写了一个操作HBase的类SQL编译器的雏形,目前还只初步完成了词法语法分析器,等开始写后面的预处理器、逻辑计划产生器和物理计划产生器的时候,问题出现了:HBase以及整个Hadoop项目都是用Java写成的,当然是使用Java API最直接。如果想使用其他语言的API接口,可以有这么几种方式:

现在,如果要完成操作HBase的类SQL编译器的话,有三种方案:

  1. 前端继续用Python写编译器,后端用Java API操作HBase,中间的结果用某种形式(比如文件)进行保存

  2. 重新用Java写词法语法编译器,然后直接使用HBase的Java API

  3. 继续用Python写编译器,然后使用Jython

对于方案一,中间的结果可能会是比较复杂的数据结构,不便于保存,就算可以保存,读写也会比较麻烦。

对于方案二,风险集中在需要重新寻找和学习Java的词法语法编译器。之前找到了ANTLRJavaCC等等,但是大多都比较笨重,学习成本较高,况且我预期的类SQL编译器相对简单,不需要那么高级的工具库。

对于方案三,用PLY写的编译器可以说已经完成一半了,使用起来也很轻便,如果Jython能够比较好的操作HBase的话,进度还是可以保证的。试用了Jython一下,感觉还不错!

综合各方面因素,暂时决定采用方案三。

好了,有点跑题了,言归正传,来看看Jython如果操作HBase。(配置Jython和HBase就不在这里讲了)

首先,将HBase启动:

bin/start-hbase.sh

或者,HBase用到的classpath(因为Jython需要使用在classpath下的Java类),

ps auwx | grep java | grep org.apache.hadoop.hbase.master.HMaster | perl -pi -e "s/.*classpath //"

ps是获取正在运行的进程,其中Java启动的进行的格式类似于

/usr/lib/jvm/java-6-sun//bin/java –Xmx1000m … –classpath XXX

最后使用的perl就是用来获取-classpath后面的XXX的。-p是指对于输入一行一行的循环操作,i是指不需要对输入文件进行备份,-e是指执行命令s/.*classpath //。(这个命令是把classpath以及之前的字符都去掉,一定能保证-classpath是最后一个参数吗?后面还有与classpath无关的参数怎么办?实际的情况的确有无关的参数,幸好只有一点,这里算是个小bug了。)

将获取的classpath导入到环境变量中

export CLASSPATH=XXX

这样,你就可以用Jython运行python脚本操作HBase了。下面是一个简单的例子:

import java.lang
from org.apache.hadoop.hbase import HBaseConfiguration, HTableDescriptor, HColumnDescriptor, HConstants
from org.apache.hadoop.hbase.client import HBaseAdmin, HTable, Put, Get

conf = HBaseConfiguration()

admin = HBaseAdmin(conf)

tablename = "test_jython_hbase"

desc = HTableDescriptor(tablename)
desc.addFamily(HColumnDescriptor("content"))

# Drop and recreate if it exists
if admin.tableExists(tablename):
    admin.disableTable(tablename)
    admin.deleteTable(tablename)
admin.createTable(desc)

table = HTable(conf, tablename)

# Add content
row = 'row_x'
put_row = Put(row)
put_row.add('content', 'some_content', 'some_value')
table.put(put_row)

# Read content
get = Get(row)
data_row = table.get(get)
data = java.lang.String(data_row.value(), "UTF8")
print "The fetched row contains the value '%s'" % data

# Delete the table.
admin.disableTable(desc.getName())
admin.deleteTable(desc.getName())

输出结果如下所示:

…………
12/01/29 23:55:51 DEBUG client.HConnectionManager$HConnectionImplementation: Cached location for .META.,,1.1028785192 is ubuntu2-vmware:60020
12/01/29 23:55:52 DEBUG client.MetaScanner: Scanning .META. starting at row=test_jython_hbase,,00000000000000 for max=2147483647 rows
12/01/29 23:55:52 INFO zookeeper.ZooKeeper: Initiating client connection, connectString=ubuntu3-vmware:2181,ubuntu2-vmware:2181 sessionTimeout=180000 watcher=hconnection
12/01/29 23:55:52 INFO zookeeper.ClientCnxn: Opening socket connection to server ubuntu3-vmware/192.168.1.202:2181
12/01/29 23:55:52 INFO zookeeper.ClientCnxn: Socket connection established to ubuntu3-vmware/192.168.1.202:2181, initiating session
12/01/29 23:55:52 INFO zookeeper.ClientCnxn: Session establishment complete on server ubuntu3-vmware/192.168.1.202:2181, sessionid = 0x1352c9556270012, negotiated timeout = 180000
12/01/29 23:55:52 DEBUG client.HConnectionManager$HConnectionImplementation: Lookedup root region location, connection=org.apache.hadoop.hbase.client.HConnectionManager$HConnectionImplementation@8a2006; hsa=ubuntu3-vmware:60020
12/01/29 23:55:52 DEBUG client.HConnectionManager$HConnectionImplementation: Cached location for .META.,,1.1028785192 is ubuntu2-vmware:60020
12/01/29 23:55:52 DEBUG client.MetaScanner: Scanning .META. starting at row=test_jython_hbase,,00000000000000 for max=10 rows
12/01/29 23:55:52 DEBUG client.HConnectionManager$HConnectionImplementation: Cached location for test_jython_hbase,,1327910151208.09451a5e064db613648741bd8c896eb7. is ubuntu2-vmware:60020
The fetched row contains the value 'some_value'
12/01/29 23:55:52 INFO client.HBaseAdmin: Started disable of test_jython_hbase
12/01/29 23:55:52 DEBUG client.HBaseAdmin: Sleeping= 1000ms, waiting for all regions to be disabled in test_jython_hbase
12/01/29 23:55:53 DEBUG client.HBaseAdmin: Sleeping= 1000ms, waiting for all regions to be disabled in test_jython_hbase
12/01/29 23:55:54 INFO client.HBaseAdmin: Disabled test_jython_hbase
12/01/29 23:55:55 INFO client.HBaseAdmin: Deleted test_jython_hbase

Mozilla Wiki Secure Coding Guidelines笔记

| Comments

最近网站安全问题频发啊,我在某技术论坛上的帐号也沦陷了(虽然N年不用了)。自己赶紧补补这方面的知识,重点看了下Mozilla Wiki中的Secure Coding Guidelines,记下一些重点和之前忽略的地方。

密码怎么设计?

密码设计原则

  • 最好是8位或8位以上

  • 要有数字、字母的组合,最好是包含字母大小写和特殊字符

  • 设置密码黑名单,禁止用户注册过于简单的密码,以防止黑客通过社会工程学猜到密码

之前做项目只想到第一条,而且还是只要求6位。要是用户只注册含有数字的6为密码,那就可以被轻易破解了。人人网都没有做到以上全部,我的人人密码就是6位数字。。。虽说密码设计应该是用户自己的事情,但是简单的密码实在是太好破解了,还是最好引导用户设计出相对复杂的密码比较好。

密码怎么保存?

密码应该用hmac+bcrypt进行加密保存。

简单的说,hmac是通过含有密钥的hash算法,生成消息认证码(Message Authentication Code),可以进行数据一致性检测和消息认证;bcrypt是一种较“慢”的hash算法,这样可以使得暴力枚举破解的时间成本极大提升。

bcrypt的Python实现py-bcrypt和Java实现jBCrypt

我感觉,即使不用Mozilla推荐的hmac+bcrypt的策略,至少也应该是用md5和sha来保存的。明文是绝对不允许的,否则一抓包,用户名和密码就搞到手了。让黑客暴力破解出密码可能不是你的错,但是直接把密码告诉黑客,就是你的不对了。

输入是在客户端验证,还是在服务端验证?

都要!因为即使有客户端的js验证,用户也可以禁用浏览器的js功能,将“脏”数据传到服务端。

在客户端验证,是为了有很好的用户体验,避免什么数据都要先提交到服务端,然后再告诉你提交的数据有误;在服务端验证,则是加上了第二把锁,并且,有的数据是一定要到服务端才能检测的,比如帐号密码。

另外,在验证输入时,应该检测符合要求的格式,即“accept known good”,而不是检测不符合要求的格式,即“reject known bad”。符合要求的格式是可以设计全面的,它的补集则不可以。

输出编码

输出编码是防止XSS和各种注入的首要手段。(输入验证是次要手段)

输出编码就是将一些HTML、JS、XML等格式中的特殊字符进行转义,比如将<script>转化为&lt;script&gt;。这样,即使用户在之前的输入中填写了恶意代码,等到系统显示的时候,它也不会被执行了。

在进行SQL查询时,应该使用参数化的SQL语句(parameterized queries),千万不要使用字符串拼接来进行SQL查询(貌似之前的项目绝大部分都是这么做的 :( )。一些ORM(比如Hibernate)可以阻止一部分的SQL注入,但是在一些情况下,ORM仍然会使用native SQL,所以ORM不是万能的。

访问控制

应该防止一些URL暴露保密的内容,即使你没有提供给用户,一些用户也会有意无意的访问到那些URL(比如通过枚举)。设计某个Web工程的时候,应该先要按照某种原则设计好URL目录,然后根据不同的路径设计不同的访问权限,比如可以通过url filter实现。

安全可是永恒的话题,先写这么多,以后还要在实践中慢慢领悟。

—EOF—

写在2011到2012

| Comments

离2012年还有不到一个小时的时间了,不能免俗,还是要总结一下这一年,规划规划新的一年。

家庭方面

2011年初奶奶突然去世了,本来以为只是老年人平常生了点小病,但没有想到会走得那么快。在医院,是我去见奶奶最后一眼的,看着曾经最疼爱我的奶奶一动不动的躺在病床上,怎么喊她也再没有回应,我当时真的已经泣不成声。曾经我还说等毕业找到了工作,好好孝敬她老人家,现在已经无法实现了。父母在这一年身体都还不错,平时都很注意保养,他们平时也经常嘱咐我要开始注意保养了,比如要按时睡觉、不要在电脑前待太久。

学业方面

从研三开始,就准备开始写毕业论文了。做学术研究、写毕业论文,是一件很煎熬的事情,期间需要看很多论文,要想创新点。通过这一年整个做学术研究的过程,我基本上可以肯定我不适合做研究,至少不太适合做理论研究。而且我渐渐感觉到,中国的学术圈比较浮躁,我也没兴趣再待在里面了。但是,在学术方面我也算是尽力了,出了一篇小论文,昨天刚刚完成了毕业设计论文。

工作方面

今年从九月底开始,我就开始边复习专业知识边找工作,整个过程还是挺辛苦的,没有公司的笔试面试,就在学校看专业书籍、看笔经面经,有时也会一天跑两三家公司,来不及好好吃饭,就跑到KFC吃点垃圾食品将就一下,终于有了点赶场子的感觉。最后经过一个多月的求职,自己幸运的找到了一份比较不错的工作,我还是比较满意的。

技术方面

年初一直在做USACO,完成了差不多2/3。然后去了一家公司实习,但没想到实习了20天左右,就被导师强行召回了,具体情况请见这里,不过现在想想,其实大部分是我的错。被召回之后,平时研究的东西就比较杂了,chrome插件、scala、python、设计模式、数据结构、hadoop…………其中大部分研究的内容都记录在了我的技术博客里面了。

感情方面

仍然没有什么进展啊!这一年我还是喜欢过一个女生的,那个女生很活泼,我们聊的挺愉快。我们一起吃了几次饭、看了一次电影,也互相送了点东西,有时QQ聊天也会聊到很晚。我以为她的想法跟我一样,可没想到她只是把我当作朋友,好吧,是我想多了。。。我曾经一度很伤心、很痛苦,没有再和她联系,但后来想开了,虽然感觉再也回不到之前那么的关系亲密,但也还算是朋友,我也真心希望她好。(刚刚还收到她的祝福元旦快乐的短信,应该是群发的,不过我已经很欣慰了)

嗯……这一年差不多就是这个样子,下面改思考下新的一年应该怎么过了。

先是完成学业,再完善完善论文的实验,以及好好准备答辩

毕业之后,我想去躺北京和天津,去看看帝都,去拜访一些在北京的dcc dccmx、王公公等人,已经在天津的Tom Harvard。

下面就是准备开始工作了,找房子、熟悉工作环境……

另外,在新的一年还希望自己能够坚持做以下事情:

  • 坚持锻炼,有了好身体,才能好好生活、好好工作

  • 坚持钻研技术,平时多和dcc dccmx和小新等人讨论讨论,技术博客里面文章的深度还要再加强

  • 坚持学英语,希望以后有机会去美国看看那边的同学和朋友,同时也是为了防止哪天在天朝待不下去了,能多一条出路

  • 坚持看书,多看一些非专业的杂书,扩展自己的知识面,出来混,没点综合实力怎么行

好吧,就写这么多吧。总之,新的一年,希望自己能好好生活,好好工作,好好学习,让自己的生活充实起来,真诚的对待身边的每一个人,多关心父母,多关心同学。最后,要感谢同学、朋友、老师、家人在这一年来对我的关心和帮助。又是新的一年啊!加油吧!

—EOF—

一些Python图表工具

| Comments

考虑到最近写毕业论文以及以后自己博客中的实验分析,绘制一些图表就变得在所难免,再加上最近对Python比较感兴趣,于是就找了写利用Python绘制图表的工具库。说实话,一找一大堆,挑了几个自己感觉不错的,作为候选。

matplotlib

matplotlib可谓是matlab的Python版本,可以绘制高质量的2D图表,例如柱状图,饼状图,散点图,以及很多我不知道科学图表。除了能以python script的形式编程,还能通过ipython shell来进行交互。另外,matplotlib不但能进行绘图,还能进行复杂的科学计算(通过 numpymatplotlib.mlab)。如果之前熟悉matlab的话,应该能很快上手。
matplotlib很好很强大,图表又好看,就算对于一个搞科研的人来说,也是足够的。不过相应的代价就是学习曲线较陡,尤其是对于之前没有接触过matlab和python的人来说。

Pycha (PYthon CHArts)

Pycha是一个基于Cairo图形库的、轻量级、易于使用的python包。Pycha在大多数默认情况下能有很漂亮的外观,当然你也可以定制各种细节。它并不像matplotlib那样可以画出几乎所有的图形,只是提供了一些常用的图表类型。

Pychart

也是一个轻量级的python图形库,支持线状图、柱状图、饼状图、范围图,以及Encapsulated Postscript, PDF, PNG, SVG 等多种格式。图表外观朴素不花哨,已经够用了。
有意思的是,官网上,作者还说自己写的这个图形库已经用在了自己发表的几篇论文里面了,还列举了一些与它类似的图形库并讲了他们的优缺点。再一查作者信息,果然是牛人,在HP实验室待过 ,05年去了google。

另外,还有像CairoPlotChartDirector for Python等也是不错的选择。下面是这些图形库的柱状图例子,可以有个直观的感觉。总的来说,如果时间充裕或者今后后大量用到科学图表的话,matplotlib就是最好的选择了。如果就偶尔画一些简单的图形的话,上面介绍的都能基本满足需求,实在不行干脆直接用VISIO!

matplotlib

//////////////////////////////////////////////////////////////

Pycha


//////////////////////////////////////////////////////////////

Pychart

//////////////////////////////////////////////////////////////

CairoPlot

//////////////////////////////////////////////////////////////

ChartDirector for Python

—EOF—

Hadoop中的一些概念

| Comments

Hadoop,在不同的上下文的环境下,会表示不同范围的概念。有人可能把Hadoop单单理解为一个分布式文件系统,我感觉欠妥,因为也有很多其他的分布式文件系统。Hadoop之所以称为Hadoop,其核心在于它的MapReduce框架。所以,Hadoop的最精简的理解应该是HDFS (Hadoop Distributed File System)+ MapReduce。除了核心,也可以算上它的许多子项目,例如Hbase、Pig、Hive等等,可以通过下图来了解下Hadoop的Big Picture:

hadoop_ecosys

既然HDFS以及MapReduce是Hadoop的核心,对于它们的一些概念就要有所掌握。好,下面来讲解一下。

HDFS中的重要概念:

NameNode 它是整个HDFS的核心,里面包含了整个文件系统中的所有文件的路径,并且监控存有文件的服务器,NameNode本身并不存储文件。NameNode就相当于一个接口,当用户想要对HDFS中的文件进行读/写/添加/删除时,首先要询问NameNode,然后NameNode再给你一个存储着文件的服务器(DataNode)的列表。 注意:HDFS中只有一个NameNode (除非使用ZooKeeper),也就是意味着如果NameNode失效了,整个HDFS也就失效了。

DataNode 存放HDFS数据的节点,一般来说,HDFS都有多个DataNode,一个数据会在不同的DataNode上存储多份,以防止部分节点失效后数据丢失。DataNode启动后,会一直试图通知NameNode,以便让NameNode知道它的存在。

SecondaryNameNode 为了弥补NameNode单点失效的缺点,可以在一台单独机器上配置SecondaryNameNode。不过,SecondaryNameNode只是保存一些记录点(check point),并不会对数据进行冗余保存。

MapReduce计算模型中的重要概念:

TaskTracker 集群中真正执行计算的节点,它的操作包括:Map、Reduce以及Shuffle。每个TaskTracker都设置了一系列的slot,表示这个TaskTracker可以同时接受任务的数量。

JobTracker 分发MapReduce任务的节点。这个(活动的)JobTracker在一个MapReduce服务中只有一个,因此JobTracker也是单点失效的,如果JobTracker失效了,所有TaskTracker中的任务都会停止。

JobTracker和TaskTracker的交互过程:

  • 用户提交一个MapReduce任务(Job)给JobTracker

  • JobTracker与NameNode通信,以确定数据的位置

  • 根据数据的位置,定位那些1)在数据节点或者在数据节点附近 2)有可用slot的TaskTracker

  • JobTracker向TaskTracker提交对应的任务

  • JobTracker开始监控TaskTracker,如果监控不到TaskTracker的心跳,或者TaskTracker上面执行的任务失败,就将任务提交到其他TaskTracker

  • 当TaskTracker上的任务完成后,JobTracker会更新它的状态

嗯,差不多就这么多吧,有时间再深入研究研究!

—EOF—

程序员求职的一些总结

| Comments

从九月底到现在,本人历时一个多月的求职之路算得上基本结束了。回顾整个过程,经历了许多,感觉既辛苦又幸运,整体来说还是蛮好玩的。既然在整个过程中经历了许多事情,自己还是写一些东西吧,一方面是对自己的总结和反省,另一方面也算是对学弟学妹将来找工作的一个参考吧。

不要“海投”

在求职期间,千万不要见到是跟自己专业相关的公司就去投简历。第一,现在投简历不是直接发个简历就完事的,每投一个公司,自己就要从头到尾填一遍信息,很是浪费时间;第二,之前投了太多公司,到时候各种宣讲会、笔试、面试就会有很多冲突,即使没有冲突,你的时间也会排得满满的,整天疲于奔命,根本没有时间用来准备专业知识。我建议,一般选择6~8家公司就可以了。 另外,如果宣讲会只是宣讲会,之后没有投简历、笔试等环节的话,那就没什么必要去了,能听到的信息在网上也能找到的,除非你想要宣讲会上发的小礼品。。。

选公司要有梯度

选择要有梯度,这让我突然想起了高考填报志愿的时候,老师就教导我们选学校要有梯度,学校之间拉开水平。选公司的时候,也是同样的道理,可以把公司根据自己的实力分为三个等级。第一等级的公司,基本上是十拿九稳可以拿到offer的,俗称保底offer;第二等级的公司,虽然竞争也很大,但是自己通过前期的准备和复习,可以搞定的概率还是比较大的;第三等级的公司,就是业内一流的公司,如果能进这样的企业,将会对自己的职业生涯有很大的正面影响,这样的企业,可以尽全力试一试,虽然很难进,但是如果不试一下,未免就有点遗憾了。

有针对性的准备

每个公司考核求职者的侧重点都不一样,有的偏C/C++,有的偏Java,有的偏逻辑和算法,有的偏项目经验,有的偏网络,有的还会重点考察外语能力。我们求职前期,可以把大体都会考察到的知识点都粗略看一边。等到要进行笔试/面试的前几天,就可以有针对性的准备了,看看网上关于该公司的笔经/面经,把出现次数很多的题目重点看一看,把该公司的整个招聘流程的风格了解下,到时候可以心里有底、处变不惊。

动手写代码

可能许多人在复习专业知识的时候,都是抱着几本书看,但是这样是不够的。想一想,作为程序员,最基本的工作是什么?不就是编代码嘛。现在但凡要求高一点的公司,都会让你在面试的时候,现场写代码的。(我的情况是,有三次面试,让我现场在纸上写代码,还有一次电话面试,让我写出可以运行的程序,一小时后交给面试官)所以,复习专业知识的时候,一定要尽量让自己在电脑或纸上写出该部分的程序,不写不知道,一写才发现自己有许多细节没考虑到。并且,尽量自己多写几遍,可能一开始写需要40分钟甚至1小时,只有多多练习,在面试的时候才能在20分钟左右熟练的写出令面试官满意的代码。

面试时一般不用穿正装

一开始准备求职之前,我还在想要不要准备一套正装,可以等自己经过了1、2次面试之后,发现完全没有这个必要。我面试的行头一般就是衬衫+牛仔裤+运动鞋,(有一次有家公司突然通知我当天去面试,结果我只好穿着当天的一套运动装就去了。。。)我感觉作为搞技术的去应聘,穿的干净、整洁就可以了,不要搞得太正规,除非你平时就是一直穿着正装的。(嗯,DCC就是这样的 :–) )

至少有一个自己真正参与的项目

“真正参与”是什么意思,相信大家都懂的!可能你不是项目的leader,你只是负责其中一部分功能,但你应该有“主人翁”意识嘛,项目是什么背景的,用了哪些技术、哪些框架,难点在哪,最有挑战性的地方是什么,有什么优化的措施,这些问题你都应该有所了解。在参与的项目当中,至少有一个项目你能够很清楚的回答出以上这些问题。几乎在所有面试的时候,面试官也都会问你这些问题。 但是,可能很多人都有这样的困惑,那就是平常没有机会做项目,或者做的项目都是跟公司的业务不相关的,那怎么办?我建议大家平常利用业余时间,一个人或者几个人多做些小项目,总之多创造些实践的机会。这些实践可能对于现在来说好像不是必需的,但是多实践、多总结,对你的前途影响还是很大的,也算是一种培养自信的方式。

有一个技术博客

强烈建议大家弄一个自己的技术博客,把自己平时的总结、对于行业的看法等都记录在上面,这是一种技术积累、整理思路的好方法。对于一般只是想记录写文字,对其他没有要求的同学,搞个免费的博客就可以了;如果想要一个独立的博客域名的话,那就弄个虚拟主机,每年付个域名费和服务器空间费用就可以了;更高级的,那就整个VPS,在上面自己搭个博客,正好还能练练Linux下的操作,而且如果有些什么小项目的话,还能直接放到上面,大家就都可以用啦。 说起来也巧,我在一次面试的过程中,面试官看到我简历上面写有自己的技术博客,就直接在他的电脑上访问了一下我的博客,还饶有兴趣的问了我一些博客文章里面涉及到的技术问题,因为都是自己写的,基本上答得都没什么问题。 可以看出,单从这一点来说,面试官对我的面试表现还是比较满意的。

嗯!想要总结的基本上就是这么多,欢迎拍砖!

—EOF—

对于程序员应该去怎样的企业的一点点看法

| Comments

平时我就在想,我们这些程序员,或者说是写代码的,应该去怎样的企业呢?去怎样的企业,使我们能有长远的发展?去怎样的企业,让我们能为社会贡献的更多?最近自己都在找工作,我也不得不面对这样的问题。对我来说,期望值从高到低应该是这样一个顺序:

一流研究机构(微软亚洲研究院、Yahoo! 研究院、IBM研究院)

创新,是改变世界、使得社会得以不断发展的一个重要的因素,而研究机构正是孕育创新摇篮。研究机构里面的研究成果,可能只是一个设想、一个原型,不一定能够立即投入到应用当中。不过一旦研究出点什么,则会对我们的生活有着本质的影响。想起前段时间在南京软件博览会上玩的Kinect,就让人不由的感受到了创新对于改变人们生活方式的力量。

在我的想象当中,一流研究机构里面员工的工作方式应该是:一群人在几乎没有压力的情况下,根据自己的兴趣方向,查阅大量文献资料,找到有意义的创新点,自己编码做出原型系统并不断改进,然后重复上述步骤。

能够在几乎无压力的情况下做自己感兴趣的事情,自己喜欢的事情就是自己的事业,这应该就是最理想的情况了。但是,一流的研究机构对于员工的要求也是及其严格的(这似乎已经大大超出程序员的职责了),你要有深厚的科研能力、扎实的数学功底、缜密的逻辑思维,而且还要有相当的编程能力,能同时具备这些素质的人,很少很少!

中大型互联网公司(Google、百度、腾讯、阿里巴巴、网易、淘宝)

这个时代毕竟是Web的时代,Web已经是无处不在了,所以从事互联网行业还是很有前途的。互联网的主要用户是和我们一样,都是年轻人。互联网公司中的员工,绝大部分也是年轻人。年轻人嘛,都是希望自由、平等、不受拘束,所以公司的氛围一般都是比较轻松的,人与人之间的交流也比较平等、单纯。而且,由于互联网行业的特点,一旦有了较高的、稳定的用户量,公司将会有较快的发展速度,员工就能在这个过程中与公司一同成长,能够经历很多,也能学到很多。

其中,对于那些大型互联网公司,用户量庞大并且稳定,已经找到很好的盈利点,肯定是饿不死的。不过,公司里面的人员机构也会相对臃肿一些,员工在里面可能只会接触到其中的很小一块,不会一开始就了解公司系统的整体构架,但应该会做的比较深。

而那些还处在发展中阶段的中型互联网公司,刚刚起步,员工在里面能经历到公司发展的各个阶段,也能在一开始就了解公司系统的各个方面。不过,在这种公司冒的风险就要稍微大一点了,万一外部或者内部环境出了状况,公司一口气上不来,就。。。

国外著名软件公司(微软、IBM、Oracle)

谁叫计算机是外国人发明出来的呢,外国(尤其是美国)在计算机这一块还是遥遥领先于其他国家的,他们经历了电脑从无到有、PC普及、以及目前互联网的时代。我想不管是理论上、技术上,还是整个的氛围,都比国内高不止一个档次。这些国外著名的软件公司,历史悠久,资金雄厚,技术方面更是不用说。因此,如果能进入这些公司,可以感受到国际一流的技术和氛围,也有机会能与全世界各国的人士交流,整个视野也会比较开阔。而且,这些公司绝大部分都会落户于北京、上海这样的中国一线城市,对于想在一线城市打拼的人来说应该是个不错的选择。

当然,正如前面说到的,公司一旦大了,就难免显得臃肿,每个员工在里面一开始都只负责其中的一小块。而且,其中有些公司,真正的核心技术还是在国外的总部进行研发的,中国的公司可能就负责一些周边的系统,有的甚至是处理一些服务性质的工作,如果是这样的话,那就没什么意思了。

大型非软件公司的IT部门(中兴、华为、移动、银行)

有些大公司,不是纯粹的软件公司,有可能是做电信的或者金融,但其中的IT部门也会有很大的规模。在这些公司的话,工作就会集中在某一个行业里了,做的深的话就可以成为某一个行业的IT专家了,优点是可以凭经验吃饭,工作时间越长越有竞争力,缺点就是你只能局限在一个小圈子甚至几个同类公司了。里面有些公司,业务散得很大,需要大量的人,所以进去相对容易一些,比如中兴、华为。(不过至今未收到中兴的面试通知,好歹给我个保底啊!)另外一些公司,不需要大量的人力,想进去就困难的多了,比如中国移动或者一些银行。(上次在网上看了摩根斯坦利的技术笔试题,感觉对员工的英语、数学、逻辑以及技术的要求都非常高。)

创业公司

这两年在中国,创业的氛围还是挺浓的。我周围就有一些同学一毕业或者工作2、3年就去创业了,有的不时还诱惑我,希望我跟他们一起干。上次我还意外的去了家创业公司看了看,里面的老板是CMU毕业的博士,在国外工作了二十多年,然后回国创业。公司的技术氛围还不错,跟老板聊了聊,感觉人家还是挺有想法的。

在创业公司工作的话,几乎就是从零开始,好处很明显,如果公司起来了,你就是创始人之一啦!但是,在创业公司压力也很大,公司说不定随时都会倒掉。如果没有足够的拼劲和毅力的话,不要选择创业公司;如果没有自己的想法,只想完成别人给你的任务,也不要选择创业公司;如果自己技术不过关,那更不要选择创业公司。因为在创业公司,每一位员工都是要有贡献的,是容不得人吃闲饭的。

外包公司(南大富士通、东软)

外包嘛,大家都懂得,就是一些公司把非核心技术方面的东西拿给这些公司来做。如果有固定的客户或者就是某个公司的“内包”的话,那就不愁没项目接,不然就要去到处拉项目了。做外包项目,基本上都是些大同小异的东西,最终只要按合同上写好的要求完成就可以了。在外包公司里面,我感觉技术方面学不到很多,不过工程方面的知识和经验倒还是可以学到不少的。

嗯,大概就是这些吧!本人能力有限,能想到的大概是这么多,肯定有许多考虑不周的地方,欢迎拍砖!

从最近找工作说起

| Comments

求职季开始了,大家都忙碌起来了,完善自己的简历,进行网申,复习专业知识,准备笔试和面试。这个过程,其实也是对自己整个大学生涯的回顾和总结。看看自己的简历,看看自己以前到底做过些什么,到底做过些什么有意义的事情,到底做过些什么没有任何人逼你、你却乐在其中、做完后很有成就感的事情。这些事情,对我来说,有,但不多。

还是来说说最近碰到的一些事情以及一些感悟吧。

写简历时,我发现一个很严重的问题:在研究生阶段,自己的能力没有得到什么提高,至少没有明显的提高。之前准备上研究生的时候,总是会憧憬着研究生阶段会有许多项目做,生活会很忙碌、很充实。可是没想到,原来研究生阶段大多都是自学成才!(我周围都是这样的,不代表所有情况)研究生阶段,说白了就是给导师打工,很可惜,导师一般情况下给你不会是实际的项目,而是让你些各种策划书,查阅论文,搜集资料。至于学术研究,大家都是自己搞自己的一部分,遇到问题基本上也没人可以讨论的,自己研究的东西导师可能也不是很了解。相比较而言,还是本科的时候更自在、更充实!但是,有些事情自己还是要肯定一下自己的。比如研究生阶段还是去做了POJ和USACO上面的题目,搞了个人的技术博客,仍然坚持关注业内的动态,去考了中级口译(虽然口试部分没通过 :( ),也还是算在不停折腾的,没有完全打酱油。

当然,我也不能说我选择上研究生是错误的,无论选哪一条路,只要走好了,前途都会很光明的。读研也是有很多好处的,例如没有工作那么辛苦,有一些自由的时间,可以做一些自己感兴趣的事情(当然,这里感兴趣的事情,是与专业相关的,不是玩游戏、看电视剧这些事情)。反正有利有弊吧,就看你怎么做了。

另外,最近在找工作时也发生了一件令人哭笑不得的事情。教研室一X同学看许多公司招聘职位的要求里面都需要熟悉Python,他从没学过Python,但居然在简历里面写上“熟悉Python”投给了应聘的公司。为了不露馅,这两天配置了一下Python环境,看了几页书,写出个“Hello,world”,他就表示自己已经熟悉Python了。。。你说你之前学过些什么,现在记不清了,复习一下,这还情有可原,但在简历里面写着熟练掌握的东西,自己居然从来没学过,这就有点太过分了。你看中国的教育把X同学折磨成什么样了,这简直就是应试的另一个极端体现。不是因为Python是一门简洁的语言,不是因为Python可以高效的解决平时开发中的种种问题,而是因为招聘单位要求熟悉Python,所以他才要学习Python,真是让人觉得可笑又可悲。

当然,我也相信,许多同学(包括我)都会或多或少的给简历加点“水分”,添点色彩,谁又能完全免俗呢?但是,我希望能在这个复杂的世界里面能尽量保持一份单纯,怀着单纯的喜爱做出一些觉得对自己、对别人有意义的事情,并且希望能把这个世界变得更好。世界的复杂我们也许无法改变,但我们能够改变自己,或者说是改善自己,这是在我们力所能及的范围之内的。我们从小学、中学、大学、或者再到研究生,难道得到的仅仅是一个个学历,一张张纸吗?绝对不应该是这样!学习的目的之一,应该就是让我们有这样的理想、这样的动力,让我们在这纷繁的世界中保持相对的单纯,而不是在这个世界随波逐流,与这个世界“同流合污”。

Hadoop极精简运行实验

| Comments

出于对海量数据处理的兴趣以及毕设实验的要求,最近空闲时间小搞了一下Hadoop。对Hadoop不了解的同学,可以看这里。简单的说,它是一个利用MapReduce编程模型进行分布式大规模数据处理的框架。在Hadoop中,数据都表示为键/值对的形式,以便用MapReduce进行处理。MapReduce的思想十分简单,数据的处理过程分为两个阶段:map和reduce。map过程是将value(源数据)映射到不同的key中,这样所有数据就变成了key/value的集合,一个key会对应多个value;而在reduce阶段,则将每一个key的value集合进行处理,最后也同样得到key/value的集合,但这里一个key对应的一个value(计算结果)。

对于使用Hadoop的人来说,其实我们只需编写map和reduce函数,以及一个驱动程序即可,至于Hadoop是如何将多个value统一到一个key中,并且对这些value进行分组、排序,我们可以不考虑(只是暂时的)。由于手边没有“海量”数据,我只好自己造了。简单起见,我直接以键值对的形式生成了数据,而场景就是找到每个key的最大value。

我们首先来看map函数:

package main;

import java.io.IOException;

import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Mapper.Context;

/*
* map function
* the 4 class arguments of Mapper mean: input key, input value, output key, output value
*/
public class FindMaxInKeyMapper extends Mapper<LongWritable, Text, IntWritable, IntWritable>
{

    public void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException
    {
        String line = value.toString();
        String[] results = line.split(" ");
        int id, num;
        try
        {
            id = Integer.parseInt(results[0]);
            num = Integer.parseInt(results[1]);
        }
        catch (Exception ex)
        {
            return;
        }
        // add key/value
        context.write(new IntWritable(id), new IntWritable(num));
    }
}

map阶段是数据的整理阶段,基类Mapper中的类型参数分别表示:输入的key、value类型,以及输出的key、value类型。注意,这里输出的key/value与MapReduce中的概念是一致的,而输入的key/value则不是,一般来说,输入的key表示输入数据的偏移量,而输入的value表示数据本身。所以,map阶段的主要任务就是把输入的value(源数据)表示成key/value的形式,供下一步的reduce使用。我们这个例子中,只需将表示一行的String分别分解成两个int就可以了。

好,再来看看reduce函数:

package main;

import java.io.IOException;

import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.Reducer.Context;

public class FindMaxInKeyReducer  extends Reducer<IntWritable, IntWritable, IntWritable, IntWritable>
{
    /*
     * reduce function
     * find the max value in values (in the same key)
     */
    public void reduce(IntWritable key, Iterable<IntWritable> values, Context context) throws IOException, InterruptedException
    {
        int maxValue = Integer.MIN_VALUE;
        for (IntWritable value: values)
        {
            maxValue = Math.max(maxValue, value.get());
        }
        context.write(key, new IntWritable(maxValue));
    }
}

reduce阶段就是数据进行实质处理的阶段了,它的输入源于map阶段,是一个key和一个value的集合,它的输出就是一个key/value对。输入输出的key/value类型可以各不相同,只要map输出的key/value类型和reduce输入的一样就可以了。在我们的例子里面,只要在values里面找到一个最大的,然后以同样的key和那个最大的value最为输出、放入context即可。

最后,写一个驱动程序(不是设备的驱动程序,你懂的):

package main;

import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;

public class FindMaxInKey { 

    public static void main(String[] args) throws Exception{
        if ( args.length != 2 )
        {
            System.err.println("Usage: FindMaxInKey <input path> <output path>");
            System.exit(-1);
        }

        Job job = new Job();
        job.setJarByClass(FindMaxInKey.class);

        FileInputFormat.addInputPath(job, new Path(args[0]));
        FileOutputFormat.setOutputPath(job, new Path(args[1]));

        job.setMapperClass(FindMaxInKeyMapper.class);
        job.setReducerClass(FindMaxInKeyReducer.class);

        job.setOutputKeyClass(IntWritable.class);
        job.setOutputValueClass(IntWritable.class);

        System.out.println("start working");
        System.exit(job.waitForCompletion(true) ? 0: 1);
    }

}

驱动程序的工作也很简单,设置一下Map类、Reduce类、数据输入输出路径,基本上就可以了。好,下面,跑起来!

如果在配置中采用默认设置,Hadoop底层的文件系统就是本地操作系统的文件系统。不过,一般都要设置成HDFS分布式文件系统的。(肯定啊,否则Hadoop有个什么意义)将工程打成jar包,然后敲入命令:

quxiao@ubuntu1:~/hadoop/bin$ ./hadoop jar /home/quxiao/workspace/HadoopTest/HadoopTest.jar main.FindMaxInKey /user/quxiao/data.in /user/quxiao/outputdata

就可以看到命令行中提示map和reduce的完成百分比,在Hadoop自带的监控系统可以更直观的看到运行的信息。

运行之后,程序的输出是这种形式:

0 2147435993
1 2147464484
2 2147479158
3 2147458512
4 2147389924
5 2147416503
6 2147378427
7 2147478518
8 2147433586
9 2147435229
10    2147381593
11    2147463851
12    2147454928
13    2147462197
14    2147480411
15    2147481870
16    2147469297
17    2147435232
18    2147439681
19    2147437661

好!这个极精简实验就算是运行成功了。初步来看,用Hadoop做数据分析还是挺简单的,你不用担心数据的分组、排序、存储,以及许多分布式相关的细节,只要写好map和reduce函数即可。

双端堆

| Comments

之前有同学问我,怎么在一个集合中高效的找到最大以及最小的元素?(注意,不是总是找最大元素,或者总是找最小元素,而是类似随机的查找最大以及最小元素。)一开始有几种想法:

朴素的想法

把集合遍历一遍,就可以知道最大或者最小元素了,查找复杂度是O(N),查找并删除的复杂度也是O(N)。

堆结构

用两个堆,一个最大堆,一个最小堆,两个堆各存一份数据。查找最大元素,就在最大堆里面找;查找最小元素,就在最小堆里面找,他们的查找时间复杂度是O(1),查找并删除的复杂度是O(logN)。但是,怎么“同步”这两个堆呢?即,在最大堆里面删除最小的元素,在最小堆里面删除最大的元素。我们知道的只是:最小(大)元素在最大(小)堆的叶子上。怎么判断节点是叶子呢?下标×2 > size就是叶子,但是叶子上面的元素又不是排序的,查找的复杂度只能是O(N)。所以,这种想法的复杂度还是O(N)。

双端堆(灯,等灯等灯!)

突然想到小倩同学之前好像说过一个叫双端堆的数据结构,可以同时高效的查找最大最小元素。问了下小倩,然后又发现原来最近看的《数据结构基础》上面,就有相关的内容,只不过里面不叫双端堆,而是叫做对称最小-最大堆。(我个人感觉这两种名称讲的就是同一个数据结构)它就可以在O(1)的复杂度的情况下,找到最小(大)元素;O(logN)的情况下找到并删除最小(大)元素。

双端堆的特点

双端堆是一棵满二叉树,最顶端的根是一个虚根,不存放数据。定义element(N)为节点N的所有子孙节点(不包括N本身)的集合,N的左孩子left(N)(如果有的话)是element(N)中最小的元素,右孩子right(N)(如果有的话)是element(N)中最大的元素。

当以下条件成立时,它才是双端堆:

  • P1:每个节点的元素小于等于它的右兄弟(如果有)

  • P2:对于每个有祖父的节点N,其祖父节点的左孩子小于等于N

  • P3:对于每个有祖父的节点N,其祖父节点的右孩子大于等于N

比如下图就是一个双端堆

image

下面我们看看实现

既然是一个满二叉树,那么就可以像堆一样有一个数组来表示,下标为n的节点的左右孩子的下标分别为2×n和2×n+1。

插入操作

现将该元素放在树的最后,看有没有满足性质P1,若违反,交换两节点的内容。再看是否满足上面讲的性质P2或者P3,如果满足,就将元素放在当前位置;若没有:

  • 违反P2,将当前节点与其祖父的左孩子交换,祖父的左孩子变成当前节点;

  • 违反P3,将当前节点与其祖父的右孩子交换,祖父的右孩子变成当前节点。

重复进行判断,直至找到合适的位置。

假设插入2,过程如下图:

image => image => image

代码如下:

public void insert (T data) throws Exception
    {
        int curIdx = ++ size;
        if ( size >= HEAP_MAX_SIZE )
            throw new Exception();
        int grandpa;
        int parentMin, parentMax;       //爷爷的左右孩子
        while (true)
        {
            //是否有更大的左兄弟
            if ( (curIdx & 1) == 1 && data.compareTo(heap[curIdx-1]) < 0 )
            {
                heap[curIdx] = heap[curIdx-1];
                -- curIdx;
            }

            grandpa = curIdx >> 2;
            if ( grandpa == 0 )
                break;
            parentMin = grandpa << 1;
            parentMax = parentMin + 1;
            if ( heap[parentMin].compareTo(data) > 0 )
            {
                heap[curIdx] = heap[parentMin];
                curIdx = parentMin;
            }
            else if ( heap[parentMax].compareTo(data) < 0 )
            {
                heap[curIdx] = heap[parentMax];
                curIdx = parentMax;
            }
            else
                break;
        }
        heap[curIdx] = data;
    }

删除操作

这里面的删除操作应该是指找到并删除最小(大)元素,找到很容易,最小元素是根的左孩子,最大元素是根的右孩子。但是,删除之后怎么调整以满足双端堆的特性呢?我们以删除最小元素为例,算法如下:

我们将树的最后一个元素暂时放在删除元素的位置,判断两个条件:

是否满足P1,不满足则交换两元素

与其左孩子、以及右兄弟节点的左孩子(如果有的话)比较,是否是最小的,不是则与最小的节点交换。(其左孩子和右兄弟的左孩子是两个次小的节点)

重复以上判断,直至满足这两个条件。

如果删除4的话,过程如下图:

image => image => image => image => image

代码如下:

public T deleteMin () throws Exception
    {
        if ( size < 2 )
            throw new Exception();
        if ( size == 2 )
            return heap[size --];

        T tmp;
        int minChildIdx;
        T data = heap[size --];
        int curIdx = 2;
        T ret = heap[curIdx];
        while ( true )
        {
            if ( (curIdx & 1) == 0 && curIdx + 1 <= size && data.compareTo(heap[curIdx+1]) > 0 )
            {
                tmp = heap[curIdx+1];
                heap[curIdx+1] = data;
                data = tmp;
            }
            minChildIdx = curIdx << 1;
            if ( minChildIdx > size )
                break;
            if ( ((curIdx + 1) << 1) <= size && heap[minChildIdx].compareTo(heap[(curIdx+1)<<1]) > 0 )
                minChildIdx = (curIdx + 1) << 1;
            if ( data.compareTo(heap[minChildIdx]) > 0 )
            {
                heap[curIdx] = heap[minChildIdx];
                curIdx = minChildIdx;
            }
            else
                break;
        }
        heap[curIdx] = data;
        return ret;
    }

所有代码可以在这里看到。