我要评论前言
昨晚想在android应用中增加一个int映射到string的字典表，使用hashmap实现的时候，eclipse给出了一个警告，昨晚项目上线紧张，我直接给忽略了，今天看了一下具体的eclipse提示如下：
use new sparsearray<string> (...) instead for better performance
这个警告的意思是使用sparsearray来替代，以获取更好的性能。
源码
因为sparsearray整体代码比较简单，先把源码展示出来，然后再分析为什么使用sparsearray会比使用hashmap有更好的性能。
public class sparsearray<e> implements cloneable {
private static final object deleted = new object();
private boolean mgarbage = false;
private int[] mkeys;
private object[] mvalues;
private int msize;
/**
* creates a new sparsearray containing no mappings.
*/
public sparsearray() {
this(10);
}
/**
* creates a new sparsearray containing no mappings that will not
* require any additional memory allocation to store the specified
* number of mappings. if you supply an initial capacity of 0, the
* sparse array will be initialized with a light-weight representation
* not requiring any additional array allocations.
*/
public sparsearray(int initialcapacity) {
if (initialcapacity == 0) {
mkeys = containerhelpers.empty_ints;
mvalues = containerhelpers.empty_objects;
} else {
initialcapacity = arrayutils.idealintarraysize(initialcapacity);
mkeys = new int[initialcapacity];
mvalues = new object[initialcapacity];
}
msize = 0;
}
@override
@suppresswarnings("unchecked")
public sparsearray<e> clone() {
sparsearray<e> clone = null;
try {
clone = (sparsearray<e>) super.clone();
clone.mkeys = mkeys.clone();
clone.mvalues = mvalues.clone();
} catch (clonenotsupportedexception cnse) {
/* ignore */
}
return clone;
}
/**
* gets the object mapped from the specified key, or <code>null</code>
* if no such mapping has been made.
*/
public e get(int key) {
return get(key, null);
}
/**
* gets the object mapped from the specified key, or the specified object
* if no such mapping has been made.
*/
@suppresswarnings("unchecked")
public e get(int key, e valueifkeynotfound) {
int i = containerhelpers.binarysearch(mkeys, msize, key);
if (i < 0 || mvalues[i] == deleted) {
return valueifkeynotfound;
} else {
return (e) mvalues[i];
}
}
/**
* removes the mapping from the specified key, if there was any.
*/
public void delete(int key) {
int i = containerhelpers.binarysearch(mkeys, msize, key);
if (i >= 0) {
if (mvalues[i] != deleted) {
mvalues[i] = deleted;
mgarbage = true;
}
}
}
/**
* alias for {@link #delete(int)}.
*/
public void remove(int key) {
delete(key);
}
/**
* removes the mapping at the specified index.
*/
public void removeat(int index) {
if (mvalues[index] != deleted) {
mvalues[index] = deleted;
mgarbage = true;
}
}
/**
* remove a range of mappings as a batch.
*
* @param index index to begin at
* @param size number of mappings to remove
*/
public void removeatrange(int index, int size) {
final int end = math.min(msize, index + size);
for (int i = index; i < end; i++) {
removeat(i);
}
}
private void gc() {
// log.e("sparsearray", "gc start with " + msize);
int n = msize;
int o = 0;
int[] keys = mkeys;
object[] values = mvalues;
for (int i = 0; i < n; i++) {
object val = values[i];
if (val != deleted) {
if (i != o) {
keys[o] = keys[i];
values[o] = val;
values[i] = null;
}
o++;
}
}
mgarbage = false;
msize = o;
// log.e("sparsearray", "gc end with " + msize);
}
/**
* adds a mapping from the specified key to the specified value,
* replacing the previous mapping from the specified key if there
* was one.
*/
public void put(int key, e value) {
int i = containerhelpers.binarysearch(mkeys, msize, key);
if (i >= 0) {
mvalues[i] = value;
} else {
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);
}
if (msize >= mkeys.length) {
int n = arrayutils.idealintarraysize(msize + 1);
int[] nkeys = new int[n];
object[] nvalues = new object[n];
// log.e("sparsearray", "grow " + mkeys.length + " to " + n);
system.arraycopy(mkeys, 0, nkeys, 0, mkeys.length);
system.arraycopy(mvalues, 0, nvalues, 0, mvalues.length);
mkeys = nkeys;
mvalues = nvalues;
}
if (msize - i != 0) {
// log.e("sparsearray", "move " + (msize - i));
system.arraycopy(mkeys, i, mkeys, i + 1, msize - i);
system.arraycopy(mvalues, i, mvalues, i + 1, msize - i);
}
mkeys[i] = key;
mvalues[i] = value;
msize++;
}
}
/**
* returns the number of key-value mappings that this sparsearray
* currently stores.
*/
public int size() {
if (mgarbage) {
gc();
}
return msize;
}
/**
* given an index in the range <code>0...size()-1</code>, returns
* the key from the <code>index</code>th key-value mapping that this
* sparsearray stores.
*
* <p>the keys corresponding to indices in ascending order are guaranteed to
* be in ascending order, e.g., <code>keyat(0)</code> will return the
* smallest key and <code>keyat(size()-1)</code> will return the largest
* key.</p>
*/
public int keyat(int index) {
if (mgarbage) {
gc();
}
return mkeys[index];
}
/**
* given an index in the range <code>0...size()-1</code>, returns
* the value from the <code>index</code>th key-value mapping that this
* sparsearray stores.
*
* <p>the values corresponding to indices in ascending order are guaranteed
* to be associated with keys in ascending order, e.g.,
* <code>valueat(0)</code> will return the value associated with the
* smallest key and <code>valueat(size()-1)</code> will return the value
* associated with the largest key.</p>
*/
@suppresswarnings("unchecked")
public e valueat(int index) {
if (mgarbage) {
gc();
}
return (e) mvalues[index];
}
/**
* given an index in the range <code>0...size()-1</code>, sets a new
* value for the <code>index</code>th key-value mapping that this
* sparsearray stores.
*/
public void setvalueat(int index, e value) {
if (mgarbage) {
gc();
}
mvalues[index] = value;
}
/**
* returns the index for which {@link #keyat} would return the
* specified key, or a negative number if the specified
* key is not mapped.
*/
public int indexofkey(int key) {
if (mgarbage) {
gc();
}
return containerhelpers.binarysearch(mkeys, msize, key);
}
/**
* returns an index for which {@link #valueat} would return the
* specified key, or a negative number if no keys map to the
* specified value.
* <p>beware that this is a linear search, unlike lookups by key,
* and that multiple keys can map to the same value and this will
* find only one of them.
* <p>note also that unlike most collections' {@code indexof} methods,
* this method compares values using {@code ==} rather than {@code equals}.
*/
public int indexofvalue(e value) {
if (mgarbage) {
gc();
}
for (int i = 0; i < msize; i++)
if (mvalues[i] == value)
return i;
return -1;
}
/**
* removes all key-value mappings from this sparsearray.
*/
public void clear() {
int n = msize;
object[] values = mvalues;
for (int i = 0; i < n; i++) {
values[i] = null;
}
msize = 0;
mgarbage = false;
}
/**
* puts a key/value pair into the array, optimizing for the case where
* the key is greater than all existing keys in the array.
*/
public void append(int key, e value) {
if (msize != 0 && key <= mkeys[msize - 1]) {
put(key, value);
return;
}
if (mgarbage && msize >= mkeys.length) {
gc();
}
int pos = msize;
if (pos >= mkeys.length) {
int n = arrayutils.idealintarraysize(pos + 1);
int[] nkeys = new int[n];
object[] nvalues = new object[n];
// log.e("sparsearray", "grow " + mkeys.length + " to " + n);
system.arraycopy(mkeys, 0, nkeys, 0, mkeys.length);
system.arraycopy(mvalues, 0, nvalues, 0, mvalues.length);
mkeys = nkeys;
mvalues = nvalues;
}
mkeys[pos] = key;
mvalues[pos] = value;
msize = pos + 1;
}
/**
* {@inheritdoc}
*
* <p>this implementation composes a string by iterating over its mappings. if
* this map contains itself as a value, the string "(this map)"
* will appear in its place.
*/
@override
public string tostring() {
if (size() <= 0) {
return "{}";
}
stringbuilder buffer = new stringbuilder(msize * 28);
buffer.append('{');
for (int i=0; i<msize; i++) {
if (i > 0) {
buffer.append(", ");
}
int key = keyat(i);
buffer.append(key);
buffer.append('=');
object value = valueat(i);
if (value != this) {
buffer.append(value);
} else {
buffer.append("(this map)");
}
}
buffer.append('}');
return buffer.tostring();
}
}
首先，看一下sparsearray的构造函数：
/**
* creates a new sparsearray containing no mappings.
*/
public sparsearray() {
this(10);
}
/**
* creates a new sparsearray containing no mappings that will not
* require any additional memory allocation to store the specified
* number of mappings. if you supply an initial capacity of 0, the
* sparse array will be initialized with a light-weight representation
* not requiring any additional array allocations.
*/
public sparsearray(int initialcapacity) {
if (initialcapacity == 0) {
mkeys = containerhelpers.empty_ints;
mvalues = containerhelpers.empty_objects;
} else {
initialcapacity = arrayutils.idealintarraysize(initialcapacity);
mkeys = new int[initialcapacity];
mvalues = new object[initialcapacity];
}
msize = 0;
}
从构造方法可以看出，这里也是预先设置了容器的大小，默认大小为10。
再来看一下添加数据操作：
/**
* adds a mapping from the specified key to the specified value,
* replacing the previous mapping from the specified key if there
* was one.
*/
public void put(int key, e value) {
int i = containerhelpers.binarysearch(mkeys, msize, key);
if (i >= 0) {
mvalues[i] = value;
} else {
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);
}
if (msize >= mkeys.length) {
int n = arrayutils.idealintarraysize(msize + 1);
int[] nkeys = new int[n];
object[] nvalues = new object[n];
// log.e("sparsearray", "grow " + mkeys.length + " to " + n);
system.arraycopy(mkeys, 0, nkeys, 0, mkeys.length);
system.arraycopy(mvalues, 0, nvalues, 0, mvalues.length);
mkeys = nkeys;
mvalues = nvalues;
}
if (msize - i != 0) {
// log.e("sparsearray", "move " + (msize - i));
system.arraycopy(mkeys, i, mkeys, i + 1, msize - i);
system.arraycopy(mvalues, i, mvalues, i + 1, msize - i);
}
mkeys[i] = key;
mvalues[i] = value;
msize++;
}
}
再看查数据的方法：
/**
* gets the object mapped from the specified key, or <code>null</code>
* if no such mapping has been made.
*/
public e get(int key) {
return get(key, null);
}
/**
* gets the object mapped from the specified key, or the specified object
* if no such mapping has been made.
*/
@suppresswarnings("unchecked")
public e get(int key, e valueifkeynotfound) {
int i = containerhelpers.binarysearch(mkeys, msize, key);
if (i < 0 || mvalues[i] == deleted) {
return valueifkeynotfound;
} else {
return (e) mvalues[i];
}
}
可以看到，在put数据和get数据的过程中，都统一调用了一个二分查找算法，其实这也就是sparsearray能够提升效率的核心。
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
}
个人认为（lo + hi） >>> 1的方法有些怪异，直接用 lo + (hi - lo) / 2更好一些。
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论