填充填充算法选择具有最少邻居数的像素

Question

我正在研究一种板块构造模拟器,它使用改变后的洪水填充算法来检测大陆.算法大致相同.唯一的区别是它适用于顶点而不是像素.

我一直在努力改善这种行为的质量 - 我想看看当它忽略具有两个邻居或更少的大陆地壳的像素/顶点时它的表现如何.是否存在支持此功能的泛洪填充算法的现有变体？

我的(有点简化)代码如下:

var group = [];
var stack = [initialVertex];
while(stack.length > 0){
    var next = stack.pop();
    if (group.indexOf(next) != -1 && isContinental(next)){
        group.push(next);
        stack = stack.concat(getNeighbors(next));
    }
}
return group 

Answer 1

从理论上讲，跳过对集合进行的算法中的元素应该会减少该算法所花费的时间。速度的提高是否显着取决于您的数据集以及检查每个元素所花费的时间。如果有很多情况都适用跳过条件，那么可以合理地说算法的效率将会提高。

令 C = 执行此类跳跃算法所需的时间
    S = 跳过的元素总数
    s = 检查是否应跳过某个元素所需的时间
    E = 元素总数
    e = 处理一个元素所花费的时间

C = (E - S) * e + E * s

如果(C < E * e)那么该算法对于该特定数据集比没有跳过条件更有效。下图演示了一种场景，其中检查元素的成本为处理元素的 10%。随着跳过更多元素，函数的成本自然会降低。

考虑到您使用洪水填充算法的情况，由于问题的图形性质和变量初始坐标，可能很难提前知道跳过某些元素是否有帮助。一方面，可以通过跳过该顶点来从过程中消除与一个顶点相邻的整个元素链，另一方面，检查的成本可能超过其优点。一些测试将针对您的特定数据集进行。

如果您的简化代码准确地反映了实际代码，那么我想指出几个问题。

1. 指数

   使用检查扩展数组中是否存在元素indexOf比检查哈希映射或关联数组等元素是否存在要慢得多。原因是，随着数组在操作过程中扩展，检查元素是否在该数组中的成本变得越来越高。哈希映射往往会更快，但会消耗一些内存。{}您可以通过使用与每个元素的某些唯一特征（例如 ID）相关联的简单对象来执行类似的操作。（此外，您的原始示例代码中存在拼写错误。未找到元素时indexOf返回，并且结果与而不是进行比较。）-1!===

2. 连接

   使用 将concat一个数组与另一个数组连接实际上会产生一个全新的数组。当您继续将数组与数组连接时，您会创建许多不必要的垃圾。保留原始堆栈数组并直接推入该数组会更有效。

我已经设置了一个jsperf 演示，演示了可以对算法进行的一些更改，涉及基本效率，例如使用关联映射、不使用Array.concat、忽略碰巧是顶点本身的顶点的邻居，当然， ，跳过元素。与任何优化问题一样，您应该首先进行分析 ，以找出程序花费大部分时间的地方，并适当地对代码中的更改进行基准测试。希望这对您有所帮助，祝您好运！

演示中使用的最重要代码的副本如下：

function hasSufficientContinentalNeighbors(vert) {
    var i = vert.neighbors.length, n = 0;

    if (i <= 2) { return false; }

    while (i--) {
        if (isContinental(vert.neighbors[i])) {
            // Return true at nearest opportunity.
            if (++n === 3) { return true; }
        }
    }

    return false;
}

// Skip (w/o redundancies)
var group = [], grouped = {};
var stack = [initialVertex];
var next, nearby, i;
while (stack.length > 0) {
    next = stack.pop();
    if (grouped[next.id] === undefined && isContinental(next) && hasSufficientContinentalNeighbors(next)) {
        group.push(next);
        grouped[next.id] = true;
        nearby = getNeighbors(next);
        i = nearby.length;
        while (i--) {
            if (nearby[i] !== next) { stack.push(nearby[i]); }
        }
    }
}