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其实是将数组的引用作为索引。如果数组数据相同,但索引不同(不是同一个数组),那么将无法正常读取数据!因此,这个数据结构将毫无用处。我最开始使用的三维对象依然是最优解。

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

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址