稀疏数组处理

稀疏数组是指大部分元素为默认值（通常是0或null）的数组。处理稀疏数组可以优化存储和计算性能，特别是在数据压缩和传输场景下。

稀疏数组的特点

稀疏数组在JavaScript中表现为含有"空洞"的数组。通过in运算符或hasOwnProperty方法可以检测数组元素的真实存在性：

const sparseArr = [1, , 3];  // 索引1的位置是空洞
console.log(1 in sparseArr); // false
console.log(sparseArr.hasOwnProperty(1)); // false

与密集数组的区别主要体现在：

1. for-in循环会跳过空位
2. forEach/map/filter等方法会跳过空位
3. length属性包含空位计数

创建稀疏数组的常见方式

// 1. 直接声明空位
const arr1 = [1, , 3];

// 2. 修改length属性
const arr2 = [1, 2];
arr2.length = 5;

// 3. 删除元素
const arr3 = [1, 2, 3];
delete arr3[1];

// 4. 使用Array构造函数
const arr4 = new Array(5);

稀疏数组的检测方法

判断数组是否稀疏的几种技术方案：

function isSparse(arr) {
    // 方法1：比较length与实际元素数
    return arr.length > Object.keys(arr).length;
    
    // 方法2：使用in运算符检测
    for(let i = 0; i < arr.length; i++) {
        if(!(i in arr)) return true;
    }
    return false;
    
    // 方法3：ES6的includes方法
    return arr.includes(undefined);
}

稀疏数组的遍历处理

处理稀疏数组时需要特别注意遍历方式的选择：

const sparse = [1, , , 4];

// 安全遍历方案
Array.from(sparse).forEach(item => {
    console.log(item); // 1, undefined, undefined, 4
});

// 使用for...of会处理空位为undefined
for(const item of sparse) {
    console.log(item); // 1, undefined, undefined, 4
}

// 传统for循环需要手动判断
for(let i=0; i<sparse.length; i++) {
    if(i in sparse) {
        console.log(sparse[i]);
    }
}

稀疏数组压缩技术

将稀疏数组转换为紧凑表示形式的常见算法：

function compressSparseArray(arr) {
    return arr.reduce((acc, val, idx) => {
        if(val !== undefined && val !== null) {
            acc.push([idx, val]);
        }
        return acc;
    }, []);
}

// 使用示例
const sparseData = [, , 3, , 5, , , 8];
const compressed = compressSparseArray(sparseData);
console.log(compressed); // [[2,3], [4,5], [7,8]]

对应的解压缩函数：

function decompressArray(compressed, length) {
    const arr = new Array(length).fill(null);
    compressed.forEach(([idx, val]) => {
        arr[idx] = val;
    });
    return arr;
}

实际应用场景

棋盘类游戏状态存储

// 初始空棋盘
const chessBoard = new Array(8).fill().map(() => new Array(8));

// 放置棋子后的稀疏表示
function saveChessState(board) {
    const state = [];
    for(let i=0; i<8; i++) {
        for(let j=0; j<8; j++) {
            if(board[i][j]) {
                state.push(`${i},${j},${board[i][j]}`);
            }
        }
    }
    return state;
}

图像处理中的非零像素存储

// 二值图像压缩存储
function compressBinaryImage(imageData) {
    const pixels = [];
    for(let i=0; i<imageData.length; i+=4) {
        if(imageData[i] > 0) {  // 只存储非黑色像素
            pixels.push([
                Math.floor(i/4) % imageData.width,
                Math.floor(i/4/imageData.width),
                imageData[i], imageData[i+1], imageData[i+2]
            ]);
        }
    }
    return pixels;
}

性能优化技巧

处理大型稀疏数组时的注意事项：

1. 避免使用delete操作符，这会显式创建稀疏数组
2. 使用TypedArray处理数值型稀疏数据更高效
3. 批量操作时优先考虑使用Array.from或扩展运算符

// 高效初始化大型稀疏数组
const LARGE_SIZE = 1000000;
const sparseArray = [];
sparseArray[999999] = 'value';  // 只设置最后一个元素

// 更优的方案
const optimizedArray = new Array(LARGE_SIZE);
optimizedArray[LARGE_SIZE-1] = 'value';

与密集数组的转换

稀疏数组与密集数组相互转换的实用方法：

// 稀疏转密集
function toDenseArray(arr) {
    return Array.from(arr).map(item => item === undefined ? null : item);
}

// 密集转稀疏
function toSparseArray(arr) {
    const sparse = [];
    arr.forEach((item, index) => {
        if(item !== null && item !== undefined) {
            sparse[index] = item;
        }
    });
    return sparse;
}

ES6+新特性的应用

现代JavaScript提供了处理稀疏数组的新工具：

// 使用Array.prototype.fill
const dense = new Array(5).fill(0);

// 使用flatMap过滤空位
const withHoles = [1, , 3];
const noHoles = withHoles.flatMap(x => x === undefined ? [] : [x]);

// 使用Object.values获取有效值
const validValues = Object.values(sparseArray).filter(Boolean);

类型化数组处理方案

对于数值型稀疏数据，TypedArray提供更高性能的解决方案：

// 使用Float64Array处理稀疏矩阵
const matrix = new Float64Array(1000 * 1000);
matrix[1000*500 + 123] = 3.14;  // 设置特定位置的值

// 零值压缩存储
function compressTypedArray(arr) {
    const indices = new Uint32Array(arr.length);
    const values = new Float64Array(arr.length);
    let count = 0;
    
    arr.forEach((val, idx) => {
        if(val !== 0) {
            indices[count] = idx;
            values[count] = val;
            count++;
        }
    });
    
    return {
        indices: indices.slice(0, count),
        values: values.slice(0, count),
        originalLength: arr.length
    };
}