二叉树

 
/*
 * 求二叉树的深度
 */
public class TreeDepth {
	private class Node {
		Node left;
		Node right;
		int id;
 
		Node(Node l, Node r, int id) {
			this.left = l;
			this.right = r;
			this.id = id;
		}
	}
 
	public int getDepth(Node root) {
		if(root == null)
			return 0;
 
		if(root.left == null && root.right == null)
			return 0;
 
		int leftDepth = getDepth(root.left);
		int rightDepth = getDepth(root.right);
 
		return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
	}
 
	public void runTest() {
		Node n4 = new Node(null, null, 4);
		Node n5 = new Node(null, null, 5);
		Node n3 = new Node(n4, n5, 3);
		Node n2 = new Node(n3, null, 2);
		Node n1 = new Node(null, null, 1);
		Node n0 = new Node(n1, n2, 0);
 
		int depth = getDepth(n0);
 
		System.out.println(depth);
	}
 
	public static void main(String[] args) {
		TreeDepth treeDepth = new TreeDepth();
		treeDepth.runTest();
	}
}

字符串操作

 
import java.util.HashMap;
import java.util.Map;
 
/*
 * 给定一个字符串,其中一个字符出现的次数是奇数次,其余字符出现次数是偶数次,找出出现奇数次的那个字符
 */
public class OddChar {
	public void methodByMap(char[] a) {
 
 
		Map<Character, Integer> char_num = new HashMap<Character, Integer>();
		for(int i=0; i<a.length; i++) {
			char c = a[i];
			if(char_num.containsKey(c)) {
				char_num.put(c, char_num.get(c) + 1);
			}
			else {
				char_num.put(c, 1);
			}
		}
 
		for(Character c: char_num.keySet()) {
			Integer integer = char_num.get(c);
			if(integer % 2 == 1) {
				System.out.println(c);
				break;
			}
		}
	}
 
	public void methodByXOR(char[] a) {
		if(a.length == 0) {
			return;
		}
 
		if(a.length == 1) {
			System.out.println(a[0]);
		}
 
		char k = a[0];
		for(int i=1; i<a.length; i++) {
			k ^= a[i];
		}
 
		System.out.println(k);
	}
 
	public void methodByXORForString(String x) {
		int length = x.length();
 
		if(length == 0) {
			return;
		}
 
		if(length == 1) {
			System.out.println(x.charAt(0));
		}
 
		char k = x.charAt(0);
		for(int i=1; i<length; i++) {
			k ^= x.charAt(i);
		}
		System.out.println(k);
	}
 
	public static void main(String[] args) {
		OddChar odd = new OddChar();
 
		char[] a = {'a', 'a', 'a', 'b', 'b', 'c', 'c', 'd', 'd', 'x', 'x'};
 
		odd.methodByMap(a);
 
		odd.methodByXOR(a);
 
		String string = new String(a);
		odd.methodByXORForString(string);
 
		System.out.println( 'a' ^ 'a' ^ 'b');
	}
}

实习经历

在杭州实习阶段即将结束,在过去的两个月里面,应该写写的却始终敲不开键盘。总的来说,在这边不忙也不累,闲着的那段可以安静地看源代码;无能为力的那段到处寻找帮助。

实习阶段主要做了两项工作,分别对应到两种完全迥异的感觉。

第一项是阅读itest及相关框架的源代码,完成itest的web测试用例。这个从第三周开始全力投入的,前后延续一个月。我从最开始对测试一无所知,到对测试框架的理解,再到对被测对象(web 服务)的深入学习,完成了一次提升。整个过程慢慢揭开了一次源码+原理之旅。itest是老大叶渡开发的,其架构在单元测试和web测试之上,通过模拟服务(web服务)的运行环境做service test和web test。其扩展了单元测试框架junit,依赖于spring的服务配置管理,高层支持web服务测试,底层与数据库交互。我基本了解了在junit做扩展的机制,体会到java annotation和反射机制的灵活;另外,完成开源web框架支持用例过程中,了解到web服务中请求的发起、处理、返回的机理及运行上下文环境的构建。

第二项是做Aifly项目的预研。项目主要关注的是用java技术完成前端页面测试。我做的事情是调研已有的web页面测试框架在不启动浏览器的方式下完成一些测试用例。我之前在前端技术上的积累非常有限,尤其头疼的是JavaScript技术。这个异常灵活而形式纷繁的技术为各个浏览器演绎得各有千秋,产生了为前端工程师最为关注的兼容性问题。现有的页面测试框架一般都基于各个浏览器实现各自的方案,彼此不能统一。在不启动浏览器的方式下,主流的是使用一个“通用”的JS引擎来执行页面中的JS代码。而这里的“通用”实在是能力有限。面对这种境遇,我选择了解尝试的态度。了解JS的基本原理,尝试页面测试框架的基本功能。向项目组的师姐请教,向前端开发工程师寻求远程帮助,感受到公司里面同学般的互助和支持。真心祝福项目fly~

一个阶段很难判断自己的变化,但确实在变化。相信这次经历今后回想起来,感恩于其中的成长。

实习一周

到杭州有一个星期了,开始一次预工作的旅程。一个陌生的环境,一群未曾谋面的人,我默默地让自己知道一个从零开始的含义。

周末到的杭州。坐在大巴车里,听着一个杭城的节目。这次听到的话题是“放弃”,而主持人谈论的内容确是不要放弃,这题恰合了我的心境。不放弃工作,不放弃感情,不放弃追求,不放弃自己。不放弃收听电台。不该放弃的东西太多太多,现在只记得主持人说:如果一个男人在二十岁的时候不帅,在三十岁的时候不强壮,在四十岁的时候不富有,在五十岁的时候不智慧,那就真的该放弃了。

我下了大巴,来到的车站是一个分站,不是上次的那个,一种陌生迎面而来。走到公交站台寻找熟悉的名字,匹配头脑里面那张刚刚收录的地图。少了一分无知的兴奋,多了一分成长的惆怅。打的、旅店、入住、室友。

开心的是室友还是校友,上帝还给我们安排了一次默契的见面礼:我们穿了完全一样的T恤衫!呵呵,异乡的亲切~

周一到公司报到,我们一群人调研不足,随便拍拍脑袋找线路,吃过早饭,搭上备选线路。花了35分钟公交+15钟步行,总算没有迟到。我们一群Parttimer遇到上了Parttime HR,不熟悉啊不熟悉,凑合着把合同签了。后面是主管接人,我正顾虑着老大是不是还在度假,却听到了我的名字。终于见到老大了,和我预计的差不多,30左右,沉稳、智慧。

老大很快给我安排了一周工作,也就是这个成了一个纠结的开始。我很快搭建了工作环境,第一个任务看起来是那样容易。我忽略的是任务背后的复杂性,公司系统不是玩具,牵扯到安全,业务需求,隐藏了很多完全不懂的东西。问题是什么,一下子成了最棘手的问题。

第一周认识最深刻的教训是,事情没有想象的那样简单,自己所知道和掌握的东西非常有限。是的,承认无知才是学习的开始,是成长的开始。老大对我遇到的问题明确答复不会给予直接帮助:别人告诉你的,只是学到知识,解决问题的能力得不到提高;完成任务不是目的,学习和思考解决方法才是真正的锻炼。

明天又要去面对那个看似简单到让人抓狂的问题。哈哈,我愿意继续与你磨蹭。但愿能从你身上挖掘出真正的解决之道!

经历太少,所以什么都不懂

男孩子27岁的时候才开始考虑那些女孩24岁的时候就开始考虑的事情。我则更为甚之。很早被称为一个懂事的孩子,其实并不懂。只是比较早的意识到自己不能像其他伙伴那样娇惯和任性,却不知道该怎么面对现前的境况。

很久没有接到大哥的电话,这一次又是那个话题。我知道,无论说什么都行,我要做的是当一个平静的倾听者。他说现在很怀疑自己当初的选择。找一个能够理解和帮助自己女的朋友,找一个可以共同奋斗的女朋友,是多少人期待的啊,但是现在才发现,这样的女生做朋友很合适,但是却不适合在一起生活。生活中有太多的细节,细节到做家务。从大哥的描述中,我开始真切的意识到,生活的简单是其根本,正是这些无足挂齿事情占据了生活的主题。我对他说,她的一些问题真的是我之前没有能够预料到的,有些地方真的无法让人接受。大哥永远的怕误导我,总是会给我的结论加上一个前提,诸如他自己的问题也很多,控制不了脾气,性子急什么的。我知道他是在告诉我,问题彼此都有,过非不是单方的。我真的不懂,一对那么优秀的人,也知道问题就在那里,仍然没有办法解决。到现在,坚持有3年了,还是找不到一个突破或是妥协。我幼稚了,二十年的时间塑造的人格定势、思维定势,也束缚了彼此努力能够弥补的效力。大哥最后只问我决得他们两到底合不合适,我想到他说的离开那又到哪里找到合适的人,无言以对。我只能把他心中的困扰他的答案给了他:不合适。

和一些已经工作的朋友聊天,我迫切的想知道他们的现状,想知道他们经历社会洗礼后的感悟。三年没有改变太多,却是注定了太多不能改变。t哥戏谑自己成了老油条,也有跳槽的想法,却没有找到去想,从头开始是一个很难接受的条件。忙过一圈,依然是一个人,在一个熟悉而又陌生的城市寻租下一个住处。想起见面开始的闲谈,一个晃荡中的社会,让大家都无所适从,无限的观望。

l子消失了一个多月,却是纠结了半年后的结果终究还是一个人。做一个普通的人,也是很不容易。工作中没有逃避的可能,自己的职责完全由自己承担;自己揽下了太多家人的期待,社会的要求。只有他自己知道自己有多累。

优秀的他们早已经踏上新的旅程,愿意将就的也各自找到了归处。剩下的虽说都各自有剩下的理由,但我想一半是没找到合适自己的,一半是不知道自己想要什么。我自己这两项都沾上了。有理由解释自己的懈怠,但是疲倦、低落让我苦恼,这些不是我能接受的。Keeping looking, don’t setting! 永远的督促自己行动,哪怕受伤,哪怕一无所获,不愿后悔,不愿意遗憾。

渐渐的清晰了自己需要全力以赴的地方:走出自己的局限,接触更多的人,更多优秀的人,有想法和激情的人;努力留在那里,承认自己的无知,从零开始,态度上丢弃自己的那份一无是处的傲慢和容易懈怠的散漫;对未来的可能做一个调查,问问那些经历过的朋友,选择的原因,坚持的动力,无法逃避的困惑以及今后的追求,对自己有一个交代,对另一半给出一份承诺。

与其整天去怨对,不如专心去面对

不能不坚定

被问及很多话题,我都无言以对,因为没有考虑。

我敷衍的解释是:想不到那么长远。

于我的现状,现前的事情都还没解决,想到那么远就没有勇气前进了。

她现在做的,不正是你自己希望她尝试的吗,既然这样就更应该坚持自己的决定。

最近看见一句话:过多的关心别人,是自身没有安全感的表现。是的,我很多时候就是这样的,自己没有办法让自己坦然。

傻蛋,醒醒吧,世界不会围绕你转。勇敢点,心怀畏惧依然要前行;随性些,追寻那个天真的自己。

初识Java项目管理工具Maven

最近浏览了一下许晓斌的《Maven实战》,作者是Maven专家,书写得深入浅出。作者定位Maven是一个基于java平台的项目建构、依赖管理和项目信息管理工具。通过他的介绍,我才晓得Maven可以干很多事情。从项目管理的角度切入,Maven可以完成项目名称、目录架构、依赖关系、建构过程(包括编译、测试这两个主要部分)及Web发布。

Maven中的核心概念:

1. 坐标

这个是用来唯一定位一个构件(最直白的代表是jar包形式的库):通过groupId, artifactId, version, packaging, classifier这几个tag来标识。

2. 依赖

这个主要是指构件间的依赖关系。我们一般是在开发一个项目,可以称其为当前构件,开发中一般会重用其他已经开发好的构件(典型的成为第三方jar包/库)。Maven将依赖关系描述成xml格式的结构化配置。

3. 仓库

存储和维护了很多构件,可以通过坐标定位并提供下载。这个类似于linux的软件源,只是里面存储的是构建而非软件。

4. 生命周期

Maven核心作用还是构建项目,从源码到字节码,到打包,再到测试集成,最后部署。Maven的这个过程采用了模板方法(template method),主类中实现了这个算法流程,将用到的方法暴露给子类重新实现,这样变得高可配。将这个构建过程严格规定化后称为生命周期。Maven中有三个生命周期:clean,default,site。每个生命周期中又被细分为很多阶段(phase)。一般运行命令行任务就是在执行某个生命周期,直到某个指定的阶段结束。

5. 插件

生命周期是一个抽象的定义,具体在构建过程中,Maven是调用插件来完成相应的构建任务。为了使构建足够灵活,Maven将完成生命周期中具体任务时候采用插件的方式交给插件构件完成(插件也是构件)。插件可以特定于构建过程中某个或者某几个阶段完成相应的任务。

在这种架构下,生命周期中完成具体任务的插件也是可配置的,而且插件间可以有依赖、继承关系(模块化软件构建),这些十分类似于构件的依赖问题。

Streaming in Hadoop

1. 基本过程
获取数据进程:数据输入文件夹下面的数据会变成流数据进入stdin,交给数据处理进程(process),然后该进程输出到stdout,并作为mapper的stdin。
map/reduce任务进程:进程一行一行(line by line)的从stdin读入数据记录,调用mapper/reducer中设定的可执行或者脚本(executable or script)处理每行记录,并把结果输出到stdout中。

2. 一些默认设置
数据默认以tab分割,也可通过参数配置;
默认的输入格式:-inputformat的参数是TextInputFormat,并且忽略掉LongWritable类型的key,只向mapper传递value

3. 参数设置
参数分为[genericOptions] [streamingOptions],必须先设定genericOptions,后设定streamingOptions,并且后者会覆盖前者。
-file 参数向cluster提交local的文档,包括mapper,reducer,share file等,这样可以把文档分布到集群上。

参考:官方文档 http://hadoop.apache.org/common/docs/r0.20.203.0/streaming.html

Serialization in Hadoop

1. Serialization in Hadoop using Writable interface

序列化(Serialization)是把内存中的结构化对象转换成可以在网络上传输和磁盘上存储的字节流的过程
反序列化(Deserialization)是序列化的反过程,即将字节流转成对象。

分布式系统中对象序列化主要用在两个方面:1. 进程间通信(interprocess communication),主要是将对象序列化后用于网络传输;2. 持久化(persistent storage),主要是将对象存储于磁盘。其实,本质上是一样的,将内存中的对象变成可序列传输和存储的字节流。

Hadoop定义了自己的序列化格式:可以序列化的类实现org.apache.hadoop.io.Writable接口。
Writable接口定义了两个方法:将自身的状态写入DataOutput对象中;从DataInput对象中读入状态数据。

public interface Writable {
  /**
   * Serialize the fields of this object to out.
   *
   * @param out DataOuput to serialize this object into.
   * @throws IOException
   */
  void write(DataOutput out) throws IOException;
 
  /**
   * Deserialize the fields of this object from in.
   *
   * For efficiency, implementations should attempt to re-use storage in the
   * existing object where possible.
   *
   * @param in DataInput to deseriablize this object from.
   * @throws IOException
   */
  void readFields(DataInput in) throws IOException;
}

Hadoop框架默认支持对key进行排序,而且排序很多是基于外存的merge sort。所有作为key的数据类在支持序列化(实现writable接口)的同时还是看比较的(实现Comparable)。Hadoop进一步将这两个接口集成起来,org.apache.hadoop.io.WritableComparable是同时实现了org.apache.hadoop.io.Writable和java.lang.Comparable两个接口。这样诸如org.apache.hadoop.io.IntWritable, org.apache.hadoop.io.Text等实现了WritableComparable接口,作为key的时候,可以被序列化和排序。

writable

Hadoop的I/O类中也实现了Comparator,用于比较两个对象。参考上图,org.apache.hadoop.io.RawComparator扩展了java.util.Comparator,新增了一个compare方法,该方法主要是对两个byte[]作比较。其实其主要是考虑了hadoop I/O中的类都实现了Writable方法,可以被序列化为二进制流,这样RawComparator的compare方法直接比较序列化后的字节数组,就省去了将二进制流反序列化为对象再作比较。
org.apache.hadoop.io.WritableComparator类,为实现了Writable接口的I/O类做了一般意义上的实现。包括如何比对两个byte[]、从byte[]中读取int,long,double等基本类型数据。该类中也对Comparator的compare方法做了实现,比较那些实现了WritableComparator的类的时候,直接使用那些类的compareTo方法,实现代码如下:

  /** Compare two WritableComparables.
   *
   *
 
 The default implementation uses the natural ordering, calling {@link
   * Comparable#compareTo(Object)}. */
  @SuppressWarnings("unchecked")
  public int compare(WritableComparable a, WritableComparable b) {
    return a.compareTo(b);
  }
 
  public int compare(Object a, Object b) {
    return compare((WritableComparable)a, (WritableComparable)b);
  }

这里需要特别注意的是,如果自定义比较器的时候,可能需要重写public int compare(Object a, Object b)方法,使之与RawCompare的compare实现一致。
特别的,WritableComparator中用一个HashMap注册那些实现了WritableComparable接口的类的Comparator,便于hadoop框架可以根据类型获确其比较器。

2.  Serialization Frameworks

Hadoop提供API实现插件化支持第三方Serialization Frameworks。org.apache.hadoop.io.serializer.*中的Serialization接口提供了三个方法:

/**
 * <p>
 * Encapsulates a {@link Serializer}/{@link Deserializer} pair.
 * </p>
 * @param <T>
 */
public interface Serialization<T> {
 
  /**
   * Allows clients to test whether this {@link Serialization}
   * supports the given class.
   */
  boolean accept(Class<?> c);
 
  /**
   * @return a {@link Serializer} for the given class.
   */
  Serializer<T> getSerializer(Class<T> c);
 
  /**
   * @return a {@link Deserializer} for the given class.
   */
  Deserializer<T> getDeserializer(Class<T> c);
}

accept方法判断该Serialization是否支持给定的class;getSerializer返回一个序列化对象(Serializer),getDeserializer返回一个反序列化对象(Deserializer)。Serializer接口中定义了三个方法:open,打开一个OutputStream;serialize,将对象序列化到输出流中;close,关闭输出流并清理资源。Deserializer接口定义了三个方法:open,打开输入流;deserialize,将对象从输入流中读入对象信息并构建对象;close,关闭输入流并清理资源。Hadoop中默认的实现是WritableSerialization,支持实现了Writable接口的类的序列化。
第三方序列化框架有Apache Thrift,Google Protocol Buffers,Apache Avro。其中Avro是Doug Cutting的创造的。

Class factories in Hadoop

Hadoop中的一个编程实现方式:

类中使用static域,注册类型的构造工厂单例,便于以后重用

1. 实现Writable接口的类注册匿名类到工厂集合WritableFactories中

public class JobProfile implements Writable {
 
  static {                                      // register a ctor
 
  WritableFactories.setFactory (JobProfile.class,
 
    new WritableFactory() {
 
      public Writable newInstance() { return new JobProfile(); }
 
   });
 
}

在WritableFactories中有一个HashMap缓存实现了Writable接口的类及工厂:

public class WritableFactories {
  private static final HashMap<Class, WritableFactory> CLASS_TO_FACTORY =
    new HashMap<Class, WritableFactory>();
 
  private WritableFactories() {}                  // singleton
 
  /** Define a factory for a class. */
  public static synchronized void setFactory(Class c, WritableFactory factory) {
    CLASS_TO_FACTORY.put(c, factory);
  }

2. WritableComparator类中有一个HashMap用于注册其子类

public class WritableComparator implements RawComparator {
 
  private static HashMap<Class, WritableComparator> comparators =
 
    new HashMap<Class, WritableComparator>(); // registry
 
  ...
 
}

下面是FloatWritable.class中的部分代码,其中static域在第一次装载FloatWritable.class时会将该类的比较器注册到WritableComparator中的HashMap中

/** A Comparator optimized for FloatWritable. */
 
public static class Comparator extends WritableComparator {
 
  public Comparator() {
 
   super(FloatWritable.class);
 
  }
 
  public int compare(byte[] b1, int s1, int l1,  byte[] b2, int s2, int l2) {
 
    float thisValue = readFloat(b1, s1);
 
    float thatValue = readFloat(b2, s2);
 
    return (thisValue<thatValue ? -1 : (thisValue==thatValue ? 0 : 1));
 
  }
 
}
 
static {                                        // register this comparator
 
WritableComparator.define(FloatWritable.class, new Comparator());
 
}