从Javascript数组中移除等价但唯一的对象

Question

我有一个类似于以下的对象数组：

var routeArr = [
    {start: 1, end: 2},
    {start: 1, end: 3},
    {start: 1, end: 4},
    {start: 2, end: 1},
    {start: 3, end: 1},
    {start: 4, end: 1}
];

这些对象表示线的起点和终点，因此，{start: 1, end: 2} 和 {start: 2, end: 1} 表示同一条线。

我正在尝试从数组中删除所有重复的线，但找不到有效或优雅的方法。我尝试了嵌套循环，但被告知这是不好的做法（我的实现也出现了错误，而且很丑）。

for(var i = 0, numRoutes = routeArr.length; i < numRoutes; i++) {
    var primaryRoute = routeArr[i];

    for(var j = 0; j < numRoutes; j++) {
        var secondRoute = routeArr[j];

        if(primaryRoute.start === secondRoute.end && primaryRoute.end === secondRoute.start) {
            routeArr.splice(j, 1);
            continue;
        }
    }
}

有人可以提供建议吗？

- ewokthegreat

---

通常的做法是：首先对其进行排序（在您的情况下，如果（end>start），则应将开始和结束反转）。然后重复的行将完全相同。然后只需循环以删除重复项。 - CY_

当您删除数组元素时，永远不要从0到长度运行循环。这是不安全的，因为在删除后，您必须调整索引。最好按降序运行循环，即从长度-1到0，这将适用于您删除数组元素并且永远不会返回具有更大索引的元素的情况。此外，您的if语句仅检查相同行的一个条件，您还必须添加其他带有或语句的检查。 - simon

Answer 1

在JavaScript中创建一个对象/映射，并保留唯一对象的索引，将“min（start，end）：max（start，end）”存储为键，将索引存储为值。以下是您在JavaScript中提出问题的实现：

// your initial array
var routeArr = [
    {start: 1, end: 2},
    {start: 1, end: 3},
    {start: 1, end: 4},
    {start: 2, end: 1},
    {start: 3, end: 1},
    {start: 4, end: 1}
];

// map where we will store key => value where key is a joined start,end of your array's item and value is an item index 
var keyToRouteIndexMap = {};

for (var i in routeArr){
    // calculating min and max from start and end to understand {start:1, end:2} and {start:2, end:1} object as duplicates
    var min = Math.min(routeArr[i].start,routeArr[i].end);
    var max = Math.max(routeArr[i].start,routeArr[i].end);
    // unique key 
    var key = min+':'+max;
    if (!keyToRouteIndexMap.hasOwnProperty(key)){
        keyToRouteIndexMap[key] = i;
    }
}

for(var key in keyToRouteIndexMap){
    if(keyToRouteIndexMap.hasOwnProperty(key)){
        console.log(routeArr[keyToRouteIndexMap[key]]);
    }
}

- simon

---

请注意，如果您使用的是ES6，可以使用Set对象。 - Hamms

还有一些用于模拟哈希集的JavaScript实现：https://github.com/timdown/jshashtable - andor kesselman

@Hamms：Set 对象怎么会有帮助呢？它只比较对象引用。 - le_m

@Vahan Simonyan：在迭代对象键时，您应该检查 hasOwnProperty()。 - le_m

@le_m 谢谢你的有用评论（我已经编辑了答案）。 - simon

@le_m 显然你不能将对象本身用作Set的元素，但是你可以像这个例子一样构造一个键，并将其放在Set中，而不是重复使用对象作为Set。 - Hamms

Answer 2

您可以像这样做。我猜这非常快，因为根本没有搜索。使用一个Array.prototype.reduce()操作同时构建哈希表(查找表)和缩小的对象。然后映射对象键以获得结果。在这里它是;

var routeArr = [
    {start: 1, end: 2},
    {start: 1, end: 3},
    {start: 1, end: 4},
    {start: 2, end: 1},
    {start: 3, end: 1},
    {start: 4, end: 1}
],

reduced = routeArr.reduce((p,c) => {!(p[c.start+"-"+c.end] || p[c.end+"-"+c.start]) && (p[c.start+"-"+c.end] = c);
                                     return p;},{}),
 result = Object.keys(reduced).map(e => reduced[e]);
console.log(result);

经过再次思考，我删除了冗余的 Object.keys() 部分。现在这只是一个单一的 Array.prototype.reduce() 操作，全部完成仅需 O(n) 的时间。我想这可能是性能方面的极限了。看看吧。

var routeArr = [
    {start: 1, end: 2},
    {start: 1, end: 3},
    {start: 1, end: 4},
    {start: 2, end: 1},
    {start: 3, end: 1},
    {start: 4, end: 1}
],

     reduced = routeArr.reduce((p,c) => {!(p[c.start+"-"+c.end]  ||
                                           p[c.end+"-"+c.start]) &&
                                          (p[c.start+"-"+c.end] = true,
                                           p.result.push(c));
                                           return p;
                                        },{"result":[]});
console.log(reduced.result);

好的，我同意这看起来有点神秘，但实际上很简单。

• 我们在这里使用了Array.prototype.reduce()方法以一个初始值作为参数。这个初始值是{"result":[]}。当我们减少（reduce）我们的routeArr数组时，我们的初始元素现在变成了一个对象，它只有一个名为result的属性，其值为空数组。
• reduce提供了一个匿名回调函数，它接受两个参数(p,c)。其中p代表previous（前一个），c代表current（当前）。所以在第一次运行中，p是我们的初始化对象，即{"result":[]}，而c是我们对reduce操作的数组routeArr中的索引0处的项。因此，在第一轮中，c是{start: 1, end: 2}。
• 在每一轮开始之前，我们检查我们的p对象是否包含一个属性，该属性表示当前元素的值的顺序。因此，检查如下：!(p[c.start+"-"+c.end] || p[c.end+"-"+c.start])，人类可以理解为“你没有像c.start-c.end或c.end-c.start这样的字符串属性吗？”例如，在第一轮中，检查是这样的：“你没有像“1-2”或“2-1”这样的字符串属性吗？”如果有（false），我们什么也不做，但如果没有，我们执行以下操作；
• && (p[c.start+"-"+c.end] = true, p.result.push(c)); return p;。好的，第一个&&将括号中的两个指令与前面的条件绑定在一起，以使其评估为true。在a && b指令中，JS引擎只有在a评估为true时才会评估b。所以你明白了。再次用人类的语言来说，发生了什么。“你没有像“1-2”或“2-1”这样的字符串属性吗？”变成了true，我们就创建了一个值为true的“1-2”属性。因此，在下一轮中，如果我们遇到一个1-2或2-1，我们将什么也不做。然后，我们将当前对象推送到同一个对象的result属性（p.result）中，以成为它所有重复项或双胞胎的唯一代表。最后，我们返回p，以便继续进行reduce循环。

希望这很清楚。

- Redu

---

优美的功能性解决方案。现在我真的很想看看与非功能性方法的性能比较。 - le_m

我认为你现在在代码压缩方面有些过头了。选择自我说明的变量名称并不将赋值放入比较中可能会帮助OP更好地理解您的好解决方案 :) - le_m

@le_m 是的，我想你可能是对的。我会在下面加上一些解释。对我来说，这看起来像一首诗。 :) - Redu

Answer 3

以下是一个通用的解决方案，用于从javascript数组中删除重复值：

/**
 * Takes an input array and returns a new array without identical elements.
 *
 * @param {array} input
 * @callback id   identity function returning identical values for identical elements
 */
function uniquify(input, id) {
    result = [];
    map = {};
    for (var i = 0, length = input.length; i < length; ++i) {
        var element = input[i], identity = id(element);
        if (!map.hasOwnProperty(identity)) {
            result.push(element);
            map[identity] = true;
        }
    }
    return result;
}

应用到您提供的routeArr：

var routeArr = [
    {start: 1, end: 2},
    {start: 1, end: 3},
    {start: 1, end: 4},
    {start: 2, end: 1},
    {start: 3, end: 1},
    {start: 4, end: 1}
];

routeArr = uniquify(routeArr, function(route) {
    return route.start < route.end ? '' + route.start + ':' + route.end : '' + route.end + ':' + route.start;
});

- le_m

---

我猜回调函数将{start:2，end:3}和{start:6，end:1}映射到同一位置。 - Redu

Answer 4

你的嵌套循环方法“丑陋”，但这不是你的问题。

你的实现错误是由于你的两个for循环都假设数组结构在你变异它时不会改变，这导致你跳过了一些数组项。

'i'和'j'是“愚蠢”的增量器-那个for循环没有告诉代码在每次迭代中去下一个数组项，而是告诉它去(array[last_index_i_used+1] -所以当你切割数组时，你正在查看的数组发生了变化，下一个项被跳过了。

我看到了很多花哨的数组方法和ES6建议，但我认为从你的问题中可以看出你还有点新手JS，并且需要一些时间来建立基础（无意冒犯）。

尝试使用递归递减函数：

function uniquify(inputArray, ind){
    var checkStart = inputArray[ind].start, checkEnd =inputArray[ind].end
    for (var i=(ind-1);i > -1; --i){
        var thisStart = inputArray[i].start, thisEnd = inputArray[i].end
        if ((thisStart == checkStart || thisStart == checkEnd) && (thisEnd == checkStart || thisEnd == checkEnd)){

            inputArray.splice(i,1)
        }
    }

    --ind
    if (ind > -1){
        uniquify(inputArray,ind)
    }
}
uniquify(routeArr,routeArr.length -1);

我认为这种方法比嵌套循环更好，因为你不需要重复多次访问同一个值，这样可以保持性能的一致性，无论数组的大小如何。

但是你可能需要问一下自己，定义'routeArr'的方法是否明智 - 最好的情况是，它似乎在以低效的方式存储数据，浪费了内存和CPU。

- Iron Gremlin

---

我建议在JS中无论何时都使用分号，即使它们并不总是必需的。另外，您的循环索引i是全局变量，最好使用var将其定义为局部变量。 - le_m

你的猜测是正确的，我在JS方面还很新，至少在这样一个大型项目中是这样。长话短说，我们正在将一个旧的C++应用程序重写为iPad和Android上运行。决定使用HTML5和Javascript与Cordova（一开始我支持它，但现在有些疑虑）。不幸的是，在以前的C++版本中做出了一些设计决策，迫使我们以非传统的方式处理应用程序数据。我正在尝试找到一种优雅而高效的解决方案。谢谢您的回复，我正在尝试着去实践它。 - ewokthegreat

@le_m - 感谢您发现我循环中缺少var的问题。我进行了编辑以更正。 - Iron Gremlin

Answer 5

我已经编写了下面的函数，以便整洁地完成它。

var routeArr = [{
  start: 1,
  end: 2
}, {
  start: 1,
  end: 3
}, {
  start: 1,
  end: 5
}, {
  start: 2,
  end: 1
}, {
  start: 3,
  end: 1
}, {
  start: 4,
  end: 1
}];

routeArr.IsDuplicate = function(obj) {
    var i = this.length;
    var count = 0 
    while (i--) {
        if ((this[i].start === obj.start && this[i].end === obj.end ) || (this[i].start === obj.end && this[i].end === obj.start) ) {
            count++;
        }
    }
    return count>1;
}

for(var i = routeArr.length-1; i--;){
    if (routeArr.IsDuplicate(routeArr[i])) routeArr.splice(i, 1);
}

- Mina Jacob

---

这是操作上效率低下的。它需要您多次评估每个对。例如，如果您将routeApp长度增加到19，则会进行189次评估。Map似乎是更清晰的方法。在Java中，Hashmap是这种类型实现的一个很好的数据结构。https://github.com/timdown/jshashtable是javascript中的hashset实现。 - andor kesselman

JavaScript对象已经提供了“哈希映射”实现，唯一的问题是键不能是对象 - 因此您需要一个“哈希”函数，可以通过将对象通用映射到哈希（您的链接）来实现，但这样效率低下，因为您需要遍历原型链，或者使用更高效的用户提供的函数。 - le_m