最近一周一直在解决linux下安装hadoop以及hbase中遇到的问题,到今天还没有解决安装中遇到的版本问题,明天准备换到debian下试一试。从来没有一次安装程序安装成这个样子,郁闷是肯定有的。不过仔细想来,这是我第一次真正意义上解决一个未开发成熟的开源产品。
如果自己停留在云计算的书籍上,可能就碰不到这么多意想不到的问题,开源产品的用户友好度显然不够友好,这是一个方面;但我想另一原因,是自己对于开源社区的接触还不是很充分吧。
等这次安装的问题解决完毕后,我想,应该好好总结一次。
关于mapReduce,还有好多的东西自己还只是停留在大致了解的范围,资料不是很全面,有很多东西讲解的感觉也不是很充分,自己并不能很清晰的了解其中的真正关联。很多东西的理解,需要建立在平台之上,在经过一定的练习和项目才能够理解。现在平台的问题还依旧没有解决。
这半年还有好多的东西要尝试,继续努力。
小记
09月 29th, 2011记录一个创意
09月 23rd, 2011最近感觉自己的时间安排上很混乱,自己想做的事情,很多都没有完成。因此想到一个类似便签的软件,一般便签都要有时间的限制,但是,关于这点,我想取消对时间的严格限制,因为那样会给人(例如我)一种类似强迫症的情绪,把自己完全囿于自我的管理之中,这样也不好。还有关于分类:也不想做那种,一般,紧急。想通过事情的类型来分类。比如:要写的邮件,要看的电影,要看的书,要办的杂事。这个应该交由用户自我管理。还有一点,便签应该保留在什么地方,我想目前可以提供的方式,pc桌面的widget,iphone,android等手持设备。
堆排序的java实现
09月 14th, 2011public class heapSort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] test = {10,655,2,15,49,43,23,90,34,63,62};//test[0]记录数组内元素个数
HeapSort(test);
for(int i=1;i
}
}
public static int parent(int i){
return (int)Math.floor((double)i/2);
}
public static int left(int i){
return 2*i;
}
public static int right(int i){
return 2*i+1;
}
public static void max_heapify(int[] arr,int i){
int largest,tmp;
int l = left(i);
int r = right(i);
if(l<=(arr[0])&&arr[l]>arr[i]){
largest = l;
}else
largest = i ;
if(r< =(arr[0])&&arr[r]>arr[largest])
largest = r;
if(largest !=i){
tmp = arr[i];
arr[i]=arr[largest];
arr[largest]=tmp;
max_heapify(arr,largest);
}
}
public static void buildMaxHeap(int[] arr){
for(int i=(int)Math.floor(arr[0]/2);i>0;i–)
max_heapify(arr,i);
}
public static void HeapSort(int[] arr){
int tmp;
buildMaxHeap(arr);
for(int i=arr[0];i>1;i–)
{
tmp = arr[1];
arr[1]=arr[i];
arr[i]=tmp;
arr[0]-=1;
max_heapify(arr,1);
}
}
}
插入排序的递归实现
09月 12th, 2011遵循分治法的三步骤:
Divide(分解):将问题分解成为一系列的子问题
Conquer (解决):递归的解决子问题,若子问题足够小,直接求解
Combine (合并):将子问题的结果合并成为原问题的解
public class InsertSort {
public static void main(String[] args){
int[] test = {3,5,6,2,67,57,23,97,26};
recursiveInsertion(test,test.length);
for(int t :test){
System.out.print(t+” “);
}
}
public static void recursiveInsertion(int[] arr , int length){
if(length>1){
recursiveInsertion(arr,length-1);
merge(arr,length-1,length);
}
}
public static void merge(int[] arr ,int end, int n){
int tmp=arr[n-1];
int i;
for(i=end-1;i>=0&&arr[i]>tmp;i–){
arr[i+1]=arr[i];
}
arr[i+1] = tmp;
}
}
<设计模式>二原则
09月 4th, 20111 找到变化并封装之
2优先使用类聚合而不是类继承
关于求解斐波那契(Fibonacci)数列的几种方法
05月 25th, 2011斐波那契数列是一个神奇的数列。有很多生物的构成都同斐波那契数列成正相关,同时黄金分割同斐波那契数列也存在关系。
下面我们先写成Fibonacci数列的递归定义:
F(0) = 0 ;
F(1) = 0;
F(n) = F(n-1)+F(n-2);
。
通过上述的递归公式,我们即可给出Fibonacci数列的递归实现方式,这个算法,我想都是作为大家认识递归的入门算法,所以不在详述,下面来分析一下这个算法的时间复杂度。
F(n)=F(n-1)+F(n-2)。
如果利用递归树的分析方法来分析这个算法的话。
F(n)
F(n-1) F(n-2)
F(n-2) F(n-3) F(n-3) F(n-4)
……………………………………………………….
从这个递归树中发现每一层上n只是降低了1或者2,而数据规模却在增大。因此当数据规模至1时,可以发现运行的时间是指数级的。
通过Fibonacci和黄金分割的关系,亦可证明Fibonacci的时间复杂度是指数级的。
黄金分割 Φ=(1+√5)/2 与它的共轭Ô=(1-√5)/2.
有如下关系:
F(i) = (Φˆi-Ôˆi)/√5 (公式1)
如果忽略负数部分 ,可以发现F(i)接近于F(i) = (Φˆi)/√5。
因此可以说明F(i)是指数增长的。
因此当求第n个Fibonacci数时,利用递归的方法来求解,需要花费大量时间。
那么如何才能将指数级的时间复杂度进行降低,一种方法是利用Fibonacci和黄金分割的关系,即公式1 ,然而这个数学公式在计算机里是无法表示的,所以这只能成为一种理论上的解法,实际无法存在。
因此考虑另外一种解法:
通过利用二阶矩阵来解决这个问题。
{{F(n+1) , F(n) } { F(n) , F(n-1) }}={{1 , 1 }{ 1, 0 }}^n
利用这个关于矩阵的公式,同时利用分治法,将{{1 , 1 }{ 1, 0 }}^n分成2个{{1 , 1 }{ 1, 0 }}^(n/2),逐次分解至n=1 ,观察对应的递归树,可以看到时间复杂度为lg(n)的。比起指数级的有很大的改进。
java学习笔记(2):The Adapter Method idiom
05月 24th, 2011今天看《java编程思想》,看到这个Adapter Method idiom这一章节,实现了在一个累实现了iterable接口后,利用foreach循环输出对象中的数据。当想以其他的方法对foreach循环中输出该对象的数据时,可以利用Adapter Method idiom (适配器方法术语,我个人翻译,不知道是否准确)。例如:可以选择以倒序的方式或者随机的方式实现循环输出对象中的数据。对此,我专门查阅了《设计模式》中的Adapter模式,本来以为说的是一个意思,但发现不是的,不过有相似之处。
下面是利用Adapter Method idiom 实现的例子,我对书中的例子稍作改动。
<code>
import java.util.*;
public class iteralClass implements Iterable<string> {
protected String[] words = ("And that is how we know the earth to be banana-shaped.").split(" ");
public Iterator </string><string> iterator(){
return new Iterator</string><string>(){
private int index = 0 ;
public boolean hasNext() {
return index < words.length;
}
public String next() {
return words[index++];
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
public Iterable<String> reversed(){
return new Iterable</string><string>(){
public Iterator</string><string> iterator() {
return new Iterator</string><string>(){
int current = words.length-1;
public boolean hasNext() {
return current> -1;
}
public String next() {
return words[current--];
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
};
}
public Iterable</string><string> randomized(){
return new Iterable</string><string>(){
public Iterator</string><string> iterator() {
List</string><string> shuffled = new ArrayList</string><string>(Arrays.asList(words));
Collections.shuffle(shuffled,new Random(47));
return shuffled.iterator();
}
};
}
public static void main(String[] args){
iteralClass ic = new iteralClass();
for(String s : ic.reversed()){
System.out.print(s+" ");
}
System.out.println();
for(String s : ic.randomized()){
System.out.print(s+" ");
}
System.out.println();
for(String s : ic ){
System.out.print(s+" ");
}
}
}
</string></code>
以这个例子为例,对Adapter Method idiom,我的理解就是为了实现其他的方式浏览这个集合中的数据,重现编写新的方法,使其返回iterable接口,以此可以foreach循环输出集合中的数据。(foreach 只能对数组和实现iterable接口的类来做出循环)。
例子中的方法的编写方式也很好,做个记录!
java学习笔记(1):注意递归的危险。
05月 22nd, 2011thinking in java中讲到的一个crashJava的例子,这个例子讲的挺好,先记录下来:
import java.util.Vector; public class CrashJava { public String toString() { return "CrashJava address:" + this + "\n"; } public static void main(String[] args) { /* 第一种情况,利用vector来判断是否会出现堆栈溢出。 * Vector v = new Vector(); for(int i=0; i<10; i++){ v.addElement(new CrashJava()); } */ //第二种情况判断是否会出现堆栈溢出。 System.out.println(new CrashJava()); } }
当我们使用下述语句时:
“CrashJava address: ” + this
编译器就在一个字串后面发现了一个“+”以及好象并非字串的其他东西,所以它会试图将this 转换成一个
字串。转换时调用的是 toString(),后者会产生一个递归调用。
我判断了两种情况,最终都出现了堆栈溢出。
大数阶乘(java实现)
05月 18th, 2011import java.io.*; import java.math.*; public class Factorial { public static void main(String[] args) { // TODO Auto-generated method stub int n =0 ; try{ System.out.println("n="); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); }catch(IOException e){} //获取所需位数 int length = getBitLength(n); int[] arrValue = new int[length]; //第一位初始化为1 ,其余默认为0 arrValue[0]=1; for(int i=1;i<n ;i++) { try { arrValue[i]=0; } catch(ArrayIndexOutOfBoundsException e){} } int index = 0 ; double bitCount =1; for(index = 2; index<=n ; index++) { int multiValue = 0 ; bitCount +=Math.log10((double)index); for(int j=0; j<(int)bitCount;++j) { multiValue +=(index*arrValue[j]); arrValue[j]= (multiValue%10); multiValue /=10; } } for(int k=arrValue.length-1;k>=0;k--) { System.out.print(arrValue[k]); } } public static int getBitLength(int n) { double sum = 1.0; for(int i=1;i< =n;i++) sum+=Math.log10((double)i); return (int)sum; } }
位段结构的使用示例
05月 9th, 2011位段结构也是一种结构体类型,只不过该类型含有以位作为单位定义存储长度的整数类型位段成员。在某些应用中,有些信息在存储时,并不需要使用一个完整的字节,而只是需要使用一个或者几个二进制位。采用位段结构,既节省存储空间,也方便操作。
在《编程之美》中的1.2中国象棋将帅问题中,采用位段结构来解决此题,很方便,效率也高。也利于理解。
中国象棋将帅问题描述:
假设棋盘中只有“将”和“帅”二子。设A为“将”,B为“帅”。A,B二子分别被限制在己方的3*3的格子运动。每一步A,B可以横向或竖向运动,但不能沿对角线运动。另外:A,B不能碰面,也就是说, A,B不能在同一条竖线上。编写一个程序,输出A,B所有合法位置。要求代码中只能使用一个变量。
当采用位段结构来解决这个问题的时候,代码如下:
struct { unsigned char a:4; unsigned char b:4; }i; for(i.a=1;i.a< =9;i.a++) for(i.b=1;i.b<=9;i.b++) if(i.a%3!=i.b%3) printf("A=%d , B=%d\n",i.a,i.b);
可以看到解决方案很清晰,也易懂。
关于此题的其他解决方案,请参考《编程之美》