0

场景：我正在寻找深层对象中的特定对象。我正在使用一个遍历孩子的递归函数，并询问他们是在寻找他们还是在寻找他们的孩子或孙子等等。找到时，将返回找到的 obj，否则返回 false。基本上是这样的：

obj.find = function (match_id) {
    if (this.id == match_id) return this;
    for (var i = 0; i < this.length; i++) {
        var result = this[i].find(match_id);
        if (result !== false) return result;
    };
    return false;
}​

我想知道，还有比这更简单的吗？：

var result = this[i].find(match_id);
if (result) return result;

将结果存储在变量中（在每个级别上！）让我很恼火，我只想检查它是否为假并返回结果。我还考虑了以下内容，但出于明显的原因，我更不喜欢它。

if (this[i].find(match_id)) return this[i].find(match_id);

顺便说一句，我也想知道，这种方法甚至是“递归”的吗？它并没有真正称自己为...

非常感谢你。

[编辑]

check_find在 if 语句中使用另一个函数（仅在找到时才返回 true）还有另一种可能性。在一些非常复杂的情况下（例如，您不仅要找到对象，还要更改它），这可能是最好的方法。还是我错了？丁：

4

3 回答 3

3

尽管就搜索算法而言，您拥有的解决方案可能是“最好的”，而且我不一定建议更改它（或者我会更改它以使用地图而不是算法），但这个问题对我来说很有趣，尤其是关于 JavaScript 语言的功能属性，我想提供一些想法。

方法一

以下应该可以工作，而不必在函数中显式声明变量，尽管它们被用作函数参数。它也很简洁，虽然有点简洁。

var map = Function.prototype.call.bind(Array.prototype.map);

obj.find = function find(match_id) {
    return this.id == match_id ? this : map(this, function(u) {
        return find.call(u, match_id);
    }).filter(function(u) { return u; })[0];
};​

这个怎么运作：

  1. 我们测试看看是否this.id == match_id，如果是，返回this。
  2. 我们使用map(via Array.prototype.map) 转换this为“找到的项目”数组，这些“找到的项目”是使用对该find方法的递归调用找到的。（假设，这些递归调用之一将返回我们的答案。没有得到答案的将返回undefined。）
  3. 我们过滤“找到的项目”数组，以便undefined删除数组中的任何结果。
  4. 我们返回数组中的第一项，并将其称为退出。
    • 如果数组中没有第一项，undefined将返回。

方法二

解决此问题的另一种尝试可能如下所示：

var concat = Function.prototype.call.bind(Array.prototype.concat),
    map = Function.prototype.call.bind(Array.prototype.map);

obj.find = function find(match_id) {
    return (function buildObjArray(o) {
        return concat([ o ], map(o, buildObjArray));
    })(this).filter(function(u) { return u.id == match_id })[0];
};

这个怎么运作：

  1. buildObjArray构建一个单一的、大的、一维数组，包含obj和所有obj的孩子。
  2. 然后我们filter基于数组中的对象必须具有idof 的条件match_id。
  3. 我们返回第一场比赛。

Method 1和Method 2虽然很有趣，但它们的性能缺点是即使在找到匹配的 id 后它们仍会继续搜索。他们直到搜索结束才意识到他们拥有所需的东西，这不是很有效。

方法三

提高效率当然是可以的，现在我觉得这个真的很接近你感兴趣的东西了。

var forEach = Function.prototype.call.bind(Array.prototype.forEach);

obj.find = function(match_id) {
    try {
        (function find(obj) {
            if(obj.id == match_id) throw this;
            forEach(obj, find);
        })(obj);
    } catch(found) {
        return found;
    }
};​

这个怎么运作：

  1. 我们将整个find函数包装在一个try/catch块中，这样一旦找到一个项目，我们就可以throw停止执行。
  2. 我们在其中创建了一个内部find函数 (IIFE) try，我们引用它来进行递归调用。
  3. 如果this.id == match_id, 我们throw this, 停止我们的搜索算法。
  4. 如果不匹配，我们递归调用find每个孩子。
  5. 如果匹配，throw则被我们的catch块捕获，并found返回对象。

由于该算法能够在找到对象后停止执行，因此它的性能将接近您的，尽管它仍然具有try/catch块的开销（在旧浏览器上可能很昂贵）并且forEach比典型的for循环慢。这些仍然是非常小的性能损失。

方法四

最后，虽然这种方法不符合您的要求，但如果可能的话，它在您的应用程序中的性能要好得多，值得考虑。我们依赖于映射到对象的 id 映射。它看起来像这样：

// Declare a map object.
var map = { };

// ...
// Whenever you add a child to an object...
obj[0] = new MyObject();
// .. also store it in the map.
map[obj[0].id] = obj[0];

// ...
// Whenever you want to find the object with a specific id, refer to the map:
console.log(map[match_id]); // <- This is the "found" object.

这样，根本不需要任何find方法！

通过使用这种方法，您的应用程序的性能提升将是巨大的。如果可能的话，请认真考虑。

但是，当您不再引用该对象时，请小心从地图中删除该对象。

delete map[obj.id];

这是防止内存泄漏所必需的。

于 2012-09-27T04:20:09.827 回答
2

不，没有其他明确的方法，将结果存储在变量中并没有那么麻烦，实际上这就是变量的用途。

是的，这种方法是递归的：

  • 你有基本情况if (this.id==match_id) return this
  • 你有调用自己的递归步骤obj.find(match_id) { ... var result = this[i].find(match_id); }
于 2012-09-26T23:20:51.240 回答
1

我看不出有什么理由，为什么存储变量会不好。它不是一个副本，而是一个参考，所以它是有效的。加上临时变量是我现在可以看到的唯一方法（不过我可能错了）。

考虑到这一点，我认为一个方法没有check_find多大意义（它很可能基本上是相同的实现），所以如果你真的需要这个check_find方法，我会把它实现为

return this.find(match_id) !== false;

该方法是否是递归的很难说。基本上，我会说是的，因为“find”的实现对于每个对象都是一样的，所以它几乎和

function find(obj, match_id) {
    if (obj.id == match_id) return obj;
    for (var i = 0; i < obj.length; ++i) {
        var result = find(obj[i], match_id);
        if (result !== false) return result;
    }
}

这绝对是递归的（函数调用自身）。

但是，如果你这样做

onesingleobjectinmydeepobject.find = function(x) { return this; }

我不太确定，如果你仍然会称之为递归。

于 2012-09-26T23:37:43.560 回答