从Python学习中得到的一点启发

看了几天Python，感觉记忆力不行了，很多东西记不住了。但是终归是得到了一点知识：重写一个ArrayList，允许从负值的索引得到指定的项。然后写一个得到斐波拉契数组的方法，这种方法要比递归调用的方式好很多，性能上大概提升几百倍。

关于Java的递归调用的性能：

　　Java中的每一个方法调用都会把这个调用的方法加入到调用栈，等到一个方法执行完毕返回的时候（return，如果没有显式写return语句，实际上还是有的 - 方法内还有一个指针，用来执向当前执行的代码位置），才把方法从栈中弹出来，

而在Java中，这个栈的维护会很费性能，而且递归调用还有个5000次的约束。所以，在Java中尽量不要使用递归调用。

　　如果在Android中还可以使用SoarseIntArray来代替ArrayList，那样性能更好些，避免了大量创建BigInteger对象的，性能还能再提升N倍，N>100
        SparseIntArray sia = new SparseIntArray();

现在看下这个实现吧：

  1 package com.xinye.test;


import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

/**
 * 斐波那契数列的各种实现方式
 * F0 = 0
 * F1 = 1
 * Fn = Fn-2 + Fn-1
 * 
 * 
 * @author xinye
 *
 */
public class Test {
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        XYArrayList<BigInteger> list = getFiboArray(1, 1, 50);
        for(BigInteger b : list){
            System.out.println(b.toString());
        }
        System.out.println("计算" + list.size() + "项花费的时间是：" + (System.currentTimeMillis() - startTime) + "毫秒");
    }
    /**
     * 得到斐波那契数组
     * @param first 数组第一项
     * @param second 数组第一项
     * @param index 要得到的最大项，从2开始
     * @return
     */
    public static XYArrayList<BigInteger> getFiboArray(int first,int second,int index){
        XYArrayList<BigInteger> feiboArray = new XYArrayList<BigInteger>();
        if(index <= 0){
            return feiboArray;
        }
        BigInteger bi01 = BigInteger.valueOf(first);
        feiboArray.add(bi01);
        if(index == 1){
            return feiboArray;
        }
        BigInteger bi02 = BigInteger.valueOf(second);
        feiboArray.add(bi02);
        if(index == 2){
            return feiboArray;
        }
        for(int i = 2;i < index;i++){
            feiboArray.add(feiboArray.get(-1).add(feiboArray.get(-2)));
        }
        return feiboArray;
    }
}
/**
 * 一个采用了负值索引的ArrayList
 * 最后一项索引-1，倒数第二项-2，倒数第三项-3
 * 也可以正向取值：0,1,2,3,4,5
 * 
 * @author xinye
 *
 * @param <E>
 */
class XYArrayList <E> extends ArrayList<E>{
    
    /**
     * 
     */
    private static final long serialVersionUID = -1319739564479533206L;
    
    public E get(int index){
        
        if(index < 0){
            index = index + size();
        }
        return super.get(index);
    }
    public E set(int index,E element){
        if(index < 0){
            index = index + size();
        }
        return super.set(index, element);
    }
    public void add(int index, E element) {
        if(index < 0){
            index = index + size();
        }
        super.add(index, element);
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        if(index < 0){
            index = index + size();
        }
        return super.addAll(index, c);
    }
    public E remove(int index) {
        if(index < 0){
            index = index + size();
        }
        return super.remove(index);
    }
    /**
     * 删除指定范围内的对象
     * 无论从正向取值还是负向取值，fromIndex总要比toIndex先出现
     */
    public void removeRange(int fromIndex, int toIndex) {
        if(fromIndex < 0){
            fromIndex = fromIndex + size();
        }
        if(toIndex < 0){
            toIndex = toIndex + size();
        }
        super.removeRange(fromIndex, toIndex);
    }
    /**
     * 得到从fromIndex到toIndex的List的子集
     * 无论从正向取值还是负向取值，fromIndex总要比toIndex先出现
     */
    public List<E> subList(int fromIndex, int toIndex) {
        if(fromIndex < 0){
            fromIndex = fromIndex + size();
        }
        if(toIndex < 0){
            toIndex = toIndex + size();
        }
        return super.subList(fromIndex, toIndex);
    }
}

So Easy.

做个笔记，忘了的时候再来看看！