5

我正在开发一个板块构造模拟器，该模拟器使用重新调整用途的洪水填充算法来检测大陆。算法大致相同。唯一的区别是它使用顶点而不是像素。

我一直在努力提高这种行为的质量——我想看看它在忽略具有两个邻居或更少的大陆地壳的像素/顶点时的表现。是否有任何现有的洪水填充算法变体支持这一点？

我的（有些简化的）代码如下：

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
4

2 回答 2

1

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

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

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

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

C的图

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

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

  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]); }
        }
    }
}
于 2013-11-06T20:14:15.040 回答
1

最后一点也不难。我所要做的就是将isContinental检查移动到相邻的顶点。我不能说这是否是最有效的方法，但它确实有效：

var group = [];
var stack = [initialVertex];
while(stack.length > 0){
    var next = stack.pop();
    if (group.indexOf(next) != -1){
        var neighbors = getNeighbors(next).filter(isContinental)
        if (neighbors.length > 3){
            group.push(next);
            stack = stack.concat(neighbors);
        }
    }
}
return group;
于 2013-11-06T19:13:55.057 回答