Sparse array processing

A sparse array is an array where most elements are empty or have default values. When dealing with sparse arrays, attention must be paid to performance and memory usage issues. JavaScript provides various methods to optimize such scenarios.

Characteristics of Sparse Arrays

Sparse arrays in JavaScript are represented as arrays with "holes," which can be detected using the in operator:

const sparseArr = [1, , 3];  // Index 1 is a hole
console.log(1 in sparseArr);  // false
console.log(sparseArr.length); // 3

Using Array.from() to create an array preserves the holes:

const arr = Array.from({length: 5}); 
console.log(arr);  // [undefined, undefined, undefined, undefined, undefined]

Detecting Sparse Arrays

You can determine if an array is sparse by comparing its length with the number of actual elements:

function isSparse(arr) {
    return arr.length !== Object.keys(arr).length;
}

const dense = [1,2,3];
const sparse = [1,,3];
console.log(isSparse(dense)); // false
console.log(isSparse(sparse)); // true

Differences in Iteration Methods

Different array methods handle sparse arrays differently:

const sparse = [1, , 3];

// forEach skips holes
sparse.forEach(item => console.log(item)); // 1, 3

// map preserves holes
const mapped = sparse.map(x => x * 2); // [2, empty, 6]

// filter removes holes
const filtered = sparse.filter(Boolean); // [1, 3]

Performance Optimization Techniques

When working with large sparse arrays, performance considerations are crucial:

1. Using for...of loops is faster than traditional for loops:

const largeSparse = new Array(1e6);
largeSparse[999] = 'value';

// Slower approach
for (let i = 0; i < largeSparse.length; i++) {
    if (i in largeSparse) {
        console.log(largeSparse[i]);
    }
}

// Faster approach
for (const item of largeSparse) {
    if (item !== undefined) {
        console.log(item);
    }
}

2. Use Object.keys() to get valid indices:

const validIndices = Object.keys(sparse).map(Number);
validIndices.forEach(i => {
    console.log(sparse[i]);
});

Practical Use Cases

1. Storing game board states:

// Using sparse arrays to store board states
const chessBoard = new Array(8);
for (let i = 0; i < 8; i++) {
    chessBoard[i] = new Array(8);
}

// Only store positions with pieces
chessBoard[0][0] = '♜';
chessBoard[0][7] = '♜';
chessBoard[7][0] = '♖';

2. Compressing time-series data:

// Original data
const timeSeries = [];
for (let i = 0; i < 24; i++) {
    timeSeries.push(null); // One slot per hour
}

// Only record time points with data
timeSeries[9] = {value: 42, unit: '°C'};
timeSeries[15] = {value: 38, unit: '°C'};

// Convert to compact format
const compact = timeSeries
    .map((val, idx) => val !== null ? {time: idx, data: val} : null)
    .filter(Boolean);

Converting Between Sparse and Dense Arrays

1. Sparse to dense:

function toDense(sparse) {
    return [...sparse].filter(item => item !== undefined);
}

const sparse = [1, , , 4];
const dense = toDense(sparse); // [1, 4]

2. Dense to sparse (as needed):

function toSparse(dense, length) {
    const sparse = new Array(length);
    dense.forEach((item, i) => {
        sparse[i] = item;
    });
    return sparse;
}

const dense = [1, 2, 3];
const sparse = toSparse(dense, 5); // [1, 2, 3, empty × 2]

Memory Management Considerations

When handling extremely large sparse arrays:

// Wrong approach - allocates memory immediately
const badHugeArray = new Array(1e8); // Allocates memory right away

// Correct approach - use Proxy for lazy allocation
const hugeArray = new Proxy({}, {
    get(target, prop) {
        if (prop === 'length') return 1e8;
        return prop in target ? target[prop] : undefined;
    },
    set(target, prop, value) {
        target[prop] = value;
        return true;
    }
});

hugeArray[999999] = 'value'; // Only stores actually used indices

Handling Sparsity in Typed Arrays

Typed arrays do not support true sparsity but can simulate it:

// Use a sentinel value to represent "empty"
const typedArray = new Int32Array(10).fill(Number.MAX_SAFE_INTEGER);
typedArray[3] = 42;
typedArray[7] = 24;

function getTypedSparseValues(arr, emptyValue) {
    const result = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] !== emptyValue) {
            result.push(arr[i]);
        }
    }
    return result;
}

const values = getTypedSparseValues(typedArray, Number.MAX_SAFE_INTEGER);