6

在我的代码中，我有一个包含一系列像素坐标的对象。该对象的性能至关重要，因为它用于 60fps 的游戏，输出不能总是被缓存。

经过实验和基准测试，3D 数组被证明是使用无类型数组时最快的实现方式：

var PixelCollection = function() {
    this.pixels = [];
};

PixelCollection.prototype = {
    add: function(x, y) {
        var pixels = this.pixels;
        if (pixels[y]) {
            pixels[y].push(x);
        } else {
            pixels[y] = [x];
        }
    },
    each: function(callback) {
        var pixels = this.pixels;
        for (var y = 0, m = pixels.length; y < m; y++) {
            var row = pixels[y];
            if (row) {
                for (var i = 0, mm = row.length; i < mm; i++) {
                    callback(row[i], y);
                }
            }
        }
    }
};

在某些情况下，对象不够快，所以我尝试了一个Uint8Array实现，使用 2D 数组：

var WIDTH = 255;
var HEIGHT = 160;

PixelCollection = function() {
    this.pixels = new Uint8Array(WIDTH * HEIGHT);
};

PixelCollection.prototype = {
    add: function(x, y) {
        this.pixels[WIDTH * y + x] = 1;
    },
    each: function(callback) {
        var pixels = this.pixels;
        for (var i = 0, m = pixels.length; i < m; i++) {
            if (pixels[i]) {
                callback(i % WIDTH, Math.floor(i / WIDTH));
            }
        }
    }
}

这个比较慢。我认为它会更快，因为写入 - 和从Uint8arrays 读取更快，但是由于我为每个 PixelCollection 对象创建了一个巨大的对象，因此检索像素要慢得多，因为遍历所有像素需要更长的时间。（注意：我还尝试了使用无类型数组的上述实现：它要慢得多）

PixelCollection 通常不会设置所有像素。但是，边界框可能跨越整个画布，所以我确实需要使用这么大的缓冲区创建数组。

不过可能有办法解决。我可以创建一个大的共享缓冲区并为每个 PixelCollection 使用一个字节偏移量。因此，当 PixelCollectionP1占用 100 个字节时，PixelCollectionP2将从字节偏移量 100 开始。这会更有效地使用内存，但我需要跟踪每个 PixelCollection 使用的字节范围（这就是 C 所说的“指针”吗？） .

烦人的部分：当P1的边界框扩大时，我需要移动P2为P1. 而且我需要为共享缓冲区设置一个安全的缓冲区大小，所以我需要对它需要多少内存进行安全的猜测。

实现这一点是可能的，但需要大量时间、反复试验。

所以在开始之前：这似乎是一个好方法吗？有没有更好或更简单的方法来做到这一点？你知道我可以学习的任何示例实现吗？

编辑：我添加了一个 jsperf，以防您想尝试优化。
如果您对优化有一个绝妙的想法，请添加到这个 jsperf。

4

1 回答 1

1

我猜你的意思是慢跑PixelCollection.each？如果设置为 1 的点不多，第二个示例可能会更慢，因为它仍然检查所有可能的位置，而第一个示例只运行添加的点。如果您真的不惜一切代价想要每一个可能的纳秒（在这种情况下是内存），那么您可以在两个 s 中预先分配最大大小Uint8Array并单独跟踪大小。

var WIDTH = 255;
var HEIGHT = 160;

var PixelCollection = function() {
    this.pixels.length = 0;
    this.pixels.x = new Uint8Array(WIDTH * HEIGHT);
    this.pixels.y = new Uint8Array(WIDTH * HEIGHT);

};

PixelCollection.prototype = {
    add: function(x, y) {
        this.pixels.x[this.pixels.length] = x;
        this.pixels.y[this.pixels.length] = y;
        this.pixels.length++;
    },
    each: function(callback) {
        var pixels = this.pixels;
        for (var i = 0; i < this.pixels.length; i++) {
            callback(this.pixels.x[i], this.pixels.y[i]);

        }
    }
};

如果您知道 PixelCollection 的添加数量限制，那么您可以减少内存使用量。您甚至可以将两个数组组合成一个双倍长度的交替 x 和 y 值。

但是，如果您希望能够删除单个点，此方法会变得很棘手，而且它也不太可能比您使用@Pudge601 的循环更改的第一种方法快得多。

于 2014-06-02T15:34:02.473 回答