Massive Algorithms: Sparse Array

Sparse Array

https://edgblog.wordpress.com/2013/05/07/sparsearray-vs-hashmap/

A Map is represented internally as an array of lists, where each element in these lists is a key,value pair. Both the key and value are object instances.
A sparse array is simply made of two arrays: an arrays of (primitives) keys and an array of (objects) values. There can be gaps in these arrays indices, hence the term “sparse” array.

The main interest of the SparseArray is that it saves memory by using primitives instead of objects as the key.

– difference in size of the key: an int is 4 bytes while an Integer is typically 16 bytes (JVM-dependent).

– Overhead of a Hashmap entry compared to an array element. ie. a HashMap.Entry instance must keep track of the references for the key, the value and the next entry. Plus it also needs to store the hash of the entry as an int.

A sparse array as a linked list contains nodes linked to each other. In a one-dimensional sparse array, each node includes the non-zero element's "index" (position), the element's "value", and a node pointer "next" (for linking to the next node). Nodes are linked in order as per the index. In the case of a two-dimensional sparse array, each node contains a row index, a column index (which together give its position), a value at that position and a pointer to the next node.

http://www.sanfoundry.com/java-program-implement-sparse-array/

Sparse Array as Linked List

```
class List
```
```
{
```
```
    private int index;
```
```
    private Object value;
```
```
    private List nextindex;
```
```
 
```
```
    public List(int index)
```
```
    {
```
```
        this.index = index;
```
```
        nextindex = null;
```
```
        value = null;
```
```
    }
```
```
 
```
```
    public List()
```
```
    {
```
```
        index = -1;
```
```
        value = null;
```
```
        nextindex = null;
```
```
    }
```
```
 
```

    public void store(int index, Object value)

```
    {
```
```
        List current = this;
```
```
        List previous = null;
```
```
 
```
```
        List node = new List(index);
```
```
        node.value = value;
```
```
 
```

        while (current != null && current.index < index)

```
        {
```
```
            previous = current;
```

            current = current.nextindex;

```
        }
```
```
 
```
```
        if (current == null)
```
```
        {
```
```
            previous.nextindex = node;
```
```
        } else
```
```
        {
```
```
            if (current.index == index)
```
```
            {
```

                System.out.println("DUPLICATE INDEX");

```
                return;
```
```
            }
```
```
            previous.nextindex = node;
```
```
            node.nextindex = current;
```
```
        }
```
```
        return;
```
```
    }
```
```
 
```
```
    public Object fetch(int index)
```
```
    {
```
```
        List current = this;
```
```
        Object value = null;
```

        while (current != null && current.index != index)

```
        {
```

            current = current.nextindex;

```
        }
```
```
        if (current != null)
```
```
        {
```
```
            value = current.value;
```
```
        } else
```
```
        {
```
```
            value = null;
```
```
        }
```
```
        return value;
```
```
    }
```
```
 
```
```
    public int elementCount()
```
```
    {
```
```
        int elementCount = 0;
```

        for (List current = this.nextindex; (current != null); current = current.nextindex)

```
        {
```
```
            elementCount++;
```
```
        }
```
```
        return elementCount;
```
```
    }
```
```
}
```
```
 
```
```
public class SparseArray
```
```
{
```
```
    private List start;
```
```
    private int index;
```
```
 
```
```
    SparseArray(int index)
```
```
    {
```
```
        start = new List();
```
```
        this.index = index;
```
```
    }
```
```
 
```

    public void store(int index, Object value)

```
    {
```

        if (index >= 0 && index < this.index)

```
        {
```
```
            if (value != null)
```

                start.store(index, value);

```
        } else
```
```
        {
```

            System.out.println("INDEX OUT OF BOUNDS");

```
        }
```
```
    }
```
```
 
```
```
    public Object fetch(int index)
```
```
    {
```

        if (index >= 0 && index < this.index)

```
            return start.fetch(index);
```
```
        else 
```
```
        {
```

            System.out.println("INDEX OUT OF BOUNDS");

```
            return null;
```
```
        }
```
```
    }
```
```
 
```
```
    public int elementCount()
```
```
    {
```
```
        return start.elementCount();
```
```
    }
```
```
}
```

https://github.com/android/platform_frameworks_base/blob/master/core/java/android/util/SparseArray.java
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;
public SparseArray() {
this(10);
}
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;
}

@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;
}
}
}

/**
* @hide
* Removes the mapping from the specified key, if there was any, returning the old value.
*/
public E removeReturnOld(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

if (i >= 0) {
if (mValues[i] != DELETED) {
final E old = (E) mValues[i];
mValues[i] = DELETED;
mGarbage = true;
return old;
}
}
return null;
}

/**
* 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);
}

mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}

/**
* Returns the number of key-value mappings that this SparseArray
* currently stores.
*/
public int size() {
if (mGarbage) {
gc();
}

return mSize;
}
public int keyAt(int index) {
if (mGarbage) {
gc();
}

return mKeys[index];
}
@SuppressWarnings("unchecked")
public E valueAt(int index) {
if (mGarbage) {
gc();
}

return (E) mValues[index];
}
public void setValueAt(int index, E value) {
if (mGarbage) {
gc();
}

mValues[index] = value;
}

public int indexOfKey(int key) {
if (mGarbage) {
gc();
}

return ContainerHelpers.binarySearch(mKeys, mSize, key);
}
public int indexOfValue(E value) {
if (mGarbage) {
gc();
}

for (int i = 0; i < mSize; i++)
if (mValues[i] == value)
return i;

return -1;
}

public void clear() {
int n = mSize;
Object[] values = mValues;

for (int i = 0; i < n; i++) {
values[i] = null;
}

mSize = 0;
mGarbage = false;
}
public void append(int key, E value) {
if (mSize != 0 && key <= mKeys[mSize - 1]) {
put(key, value);
return;
}

if (mGarbage && mSize >= mKeys.length) {
gc();
}

mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
mValues = GrowingArrayUtils.append(mValues, mSize, value);
mSize++;
}

}

Sparse Array

Labels

Popular Posts