美文网首页
Android之SparseArray性能分析

Android之SparseArray性能分析

作者: 福later | 来源:发表于2019-12-04 18:13 被阅读0次

    为什么说SparseArray性能快。这句话对么?
    啥也不说了,直接撸代码

        private boolean mGarbage = false;
    //存储key值
        private int[] mKeys;
    //存储 value值
        private Object[] mValues;
        private int mSize;
        public SparseArray() {
    //默认10
            this(10);
        }
    

    代码就不解释了,很简单,我想知道的是它是如何维护mKeys 与 mValues的一一对应关系的;解铃还须系铃人,我们直接看如何存一个对象到集合

        public void put(int key, E value) {
    //计算索引
            int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
            if (i >= 0) {
                mValues[i] = value;
            } else {
    //x的按位取反结果为-(x+1)
                i = ~i;
                if (i < mSize && mValues[i] == DELETED) {
                    mKeys[i] = key;
                    mValues[i] = value;
                    return;
                }
    
                if (mGarbage && mSize >= mKeys.length) {
                    gc();
    
                    // Search again because indices may have changed.
                    i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
                }
    
                mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
                mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
                mSize++;
            }
        }
    

    其实SparseArray 的性能的快慢与ContainerHelpers.binarySearch() 方法息息相关,看看该方法吧

     // This is Arrays.binarySearch(), but doesn't do any argument validation.
        static int binarySearch(int[] array, int size, int value) {
            int lo = 0;
            int hi = size - 1;
    
            while (lo <= hi) {
                final int mid = (lo + hi) >>> 1;
                final int midVal = array[mid];
                if (midVal < value) {
                    lo = mid + 1;
                } else if (midVal > value) {
                    hi = mid - 1;
                } else {
                    return mid;  // value found
                }
            }
            return ~lo;  // value not present
        }
    

    可以看到,采用的是二分查找法,还记得二分查找法的前置条件么,就是所有元素有序排列,这个函数的算法时间复杂度与size值密切相关,size值很大的话,while 循环里面执行的时间可能会很长,我们在来看看GrowingArrayUtils.insert这个函数吧

     public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
            assert currentSize <= array.length;
    
            if (currentSize + 1 <= array.length) {
                System.arraycopy(array, index, array, index + 1, currentSize - index);
                array[index] = element;
                return array;
            } else {
                T[] newArray = (Object[])((Object[])Array.newInstance(array.getClass().getComponentType(), growSize(currentSize)));
                System.arraycopy(array, 0, newArray, 0, index);
                newArray[index] = element;
                System.arraycopy(array, index, newArray, index + 1, array.length - index);
                return newArray;
            }
        }
    

    继续看看growSize()方法

     public static int growSize(int currentSize) {
            return currentSize <= 4 ? 8 : currentSize * 2;
     }
    

    也是两倍扩容,从以上可以看得出,插入元素,如果超出长度,扩容还是很耗性能的,因为数组的扩容需要移动每个元素。
    所以在这里我们可以回到下开始我们提出的问题:为什么说SparseArray性能快。这句话对么?答案是不对,存取一些小量数据时,性能很快,数据量大还是用Map吧。

    相关文章

      网友评论

          本文标题:Android之SparseArray性能分析

          本文链接:https://www.haomeiwen.com/subject/sqjlgctx.html