JavaScript存储坐标数据：三维对象、一维对象和Map的性能对比

我在游戏开发过程中，遇到了用于存储坐标的需求。每个坐标对应着一个数据，在游戏过程中，需要不定期对特定坐标进行的存取。

假设位于一个长宽高为64X64X64的空间，那么一共有262,144个坐标需要储存。不考虑空间复杂度，目前有三种思路：

通过三维对象存储坐标

class Data3D {
    constructor() {
        this.object = {};
    }
    getData({ x, y, z }) {
        const object = this.object;
        if (object[x] === undefined)
            return undefined;
        if (object[x][y] === undefined)
            return undefined;
        return object[x][y][z];
    }
    setData({ x, y, z }, data) {
        const object = this.object;
        if (object[x] === undefined)
            object[x] = {};
        if (object[x][y] === undefined)
            object[x][y] = {};
        object[x][y][z] = data;
    }
}

第一层对象存储所有x坐标，第二层y坐标，第三层z坐标。是我最开始拍脑袋想出来的数据结构。由于三维对象结构较为复杂，在读取、添加及遍历数据时需要额外的代码。

通过一维对象存储坐标

class Data3D {
    constructor() {
        this.object = {};
    }
    getData({ x, y, z }) {
        const object = this.object;
        return object[`${x},${y},${z}`];
    }
    setData({ x, y, z }, data) {
        const object = this.object;
        object[`${x},${y},${z}`] = data;
    }
}

每个坐标对应的字符串为索引，将所有坐标存储在一个对象中。好处是代码简洁易于理解，容易操作。

通过一维Map存储坐标，将字符串作为索引

class Data3D {
    constructor() {
        this.object = new Map;
    }
    getData({ x, y, z }) {
        const object = this.object;
        return object.get(`${x},${y},${z}`);
    }
    setData({ x, y, z }, data) {
        const object = this.object;
        object.set(`${x},${y},${z}`, data);
    }
}

每个坐标对应的字符串为索引，将所有坐标存储在一个Map中。和一维对象储存坐标类似。优点是，相对于JavaScript的对象，Map对增删查改进行了专门的优化。

通过一维Map存储坐标，将含有坐标的数组作为索引

class Data3D {
    constructor() {
        this.object = new Map;
    }
    getData({ x, y, z }) {
        const object = this.object;
        return object.get([x, y, z]);
    }
    setData({ x, y, z }, data) {
        const object = this.object;
        object.set([x, y, z], data);
    }
}

每个坐标对应的数组为索引，将所有坐标存储在一个Map中。由于Map可以接受数组作为key，所以我们将上面例子中的字符串改为数组。

然后，通过以下代码对四种数据结构进行性能测试。后来还对size翻了十倍后的性能进行了测试。

let a = new Data3D();
let size = 262144;
console.log('Size:' + size);
console.time('Set');
for (let i = 0; i <= size; i++) {
    let x = i;
    let y = 2 * i;
    let z = 3 * i;
    a.setData({ x, y, z }, Math.round(Math.random() * 100));
}
console.timeEnd('Set');
console.time('Get');
for (let i = 0; i <= size; i++) {
    let x = i;
    let y = 2 * i;
    let z = 3 * i;
    a.getData({ x, y, z });
}
console.timeEnd('Get');

得到以下性能结果：

三维对象
Size: 262144
Set: 241.56787109375 ms
Get: 19.34716796875 ms
Size: 2621444
Set: 2020.6728515625 ms
Get: 163.132080078125 ms

一维对象
Size: 262144
Set: 237.472900390625 ms
Get: 114.237060546875 ms
Size: 2621444
Set: 2704.130126953125 ms
Get: 1300.183837890625 ms

一维Map，字符串为key
Size: 262144
Set: 244.215087890625 ms
Get: 34.088134765625 ms
Size: 2621444
Set: 2144.610107421875 ms
Get: 240.362060546875 ms

一维Map，含有坐标信息的数组为key
Size:262144
Set: 51.0009765625 ms
Get: 16.833984375 ms
Size: 2621444
Set: 560.06201171875 ms
Get: 21.866943359375 ms

性能对比如图

由此可见，性能排序为：以数组为索引的一维Map>三维对象>以字符串为索引的一维Map>一维对象。并且，值得注意的是，虽然都是一维Map，通过数组进行索引的性能要远远好于字符串。

那么，是不是应当选择以数组为索引的Map作为最终方案？

答案是：不是的！当我进行完性能对比时，我突然意识到，Map其实是将数组的引用作为索引。如果数组数据相同，但索引不同（不是同一个数组），那么将无法正常读取数据！因此，这个数据结构将毫无用处。我最开始使用的三维对象依然是最优解。

但是，从工程的角度而言，在对性能要求不苛刻的情况下，可以选择一维Map方案，从而降低后期理解和维护成本。

2021年1月更新：可以了解一下八叉树，专门用于处理在三维空间中的数据储存问题。主流碰撞检测算法就是基于八叉树或类似结构。

欢迎来到Yari的网站：yar2001 » JavaScript存储坐标数据：三维对象、一维对象和Map的性能对比