SparseArayの紹介
4113 ワード
まずSparsearrayとは何かを言います。javaではこのAPIを見たことがありません。えっと、Androidで定義されているクラスです。文字どおりにはまばらな配列ですが、ソースの注釈によって、配列と大きな違いがあります。
その二つの構造関数をもう一度見てください。
SparsearyにはHashMapと似たような実用的な方法があります。
これらを知ったら、今後はHashMapの代わりにSparsearrayを使うことができますが、Sparsearrayのkeyはintタイプで、実際にはintタイプではない場合は素直にmapを使うことができます。また、key-valueのvalueタイプによって、SparseIntAray、Sparse Boarse Lorary、Arviceなどをパッケージ化しました。使い方もSparsearrayと同じです。Mapを使えば、Sparsearyを使います。
SparseArrays map integers to Objects. Unlike a normal array of Objects,
* there can be gaps in the indices. It is intended to be more memory efficient
* than using a HashMap to map Integers to Objects, both because it avoids
* auto-boxing keys and its data structure doesn't rely on an extra entry object
* for each mapping.
私たちはこの注釈を通して大体知っています。アンディはSparsearrayを使っていくつかの場合にはHashMapの代わりに使ってほしいです。それはより良い性能があるので、メモリはとても貴重なもので、特に携帯電話の中でよく知っています。その二つの構造関数をもう一度見てください。
/**
* 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 = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
そのデフォルトのkey-value配列のサイズは10であることが分かりました。もちろんカスタムでもいいです。SparsearyにはHashMapと似たような実用的な方法があります。
put(int key, E value)
get(int key)
get(int key, E valueIfKeyNotFound)
delete(int key)
removeAt(int index)
keyAt(int index)
valueAt(int index)
。
適当に一つの方法を分析してください。例えば、put(int key、E value):/**
* 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);
}
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
コードの中でまずこのkeyがSparsearrayに既に存在しているかどうかを調べます。存在する場合、置換し、存在しない場合、対応するkeyとvalueを対応する配列に挿入して、mSize++++。皆さんはkeyを検索する時に使う半値検索に気づきました。ソースを見てください。class ContainerHelpers {
// 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
}
static int binarySearch(long[] array, int size, long value) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final long 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
}
}
私たちはjavaでよく使う検索方法ですか?これらを知ったら、今後はHashMapの代わりにSparsearrayを使うことができますが、Sparsearrayのkeyはintタイプで、実際にはintタイプではない場合は素直にmapを使うことができます。また、key-valueのvalueタイプによって、SparseIntAray、Sparse Boarse Lorary、Arviceなどをパッケージ化しました。使い方もSparsearrayと同じです。Mapを使えば、Sparsearyを使います。