javascript - javascript 检查交叉点降低计算复杂度

Question

我有一个列表，其中有 500 000 个对象，每个对象都有一个坐标。我只想在该列表中留下唯一的对象。为此，我执行以下操作：

for (var i = 0; i < features.length; i++) {
   for (var j = 0; j < features.length; j++) {
      if (features[i].coord == features[j].coord) {
         features.splice(features.indexOf(features[j]), 1);
       }
    }
 }

但它不是有效的解决方案，因为它非常慢，复杂度为 O(n^2)。我怎样才能以非常快速的方式只留下独特的元素？

Answer 1

使用 hash/map/table/whatever 去重复；键（必须是字符串）是坐标的表示。

function deduplicate(features) {

    function magicalToString(coordinate) {
        return 'some string representation of the coordinate';
    }

    var table = {};
    for (var i = 0; i < features.length; i++) {
        table[magicalToString(features[i].coord)] = features[i];
    }

    var uniques = [];
    // potential optimization: uniques = new Array(Object.keys(table).length)
    // not guaranteed to be net faster; benchmark and measure.
    for (var k in table) {
        if (table.hasOwnProperty(k)) uniques.push(table[k]);
    }

    return uniques;
}

上）。