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

I have an array of objects similar to the following:

我有一系列类似如下的对象:

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}
];

These objects represent the start and end point of lines and as such, {start: 1, end: 2} and {start: 2, end: 1} represent the same line.

这些对象表示行的开始和结束点，因此，{start: 1, end: 2}和{start: 2, end: 1}表示相同的行。

I am trying to remove all duplicate lines from the array and cannot find an efficient or elegant way to do it. I have tried a nested loop but, I've been told that is bad practice (and I'm getting errors with my implementation, and it's just ugly).

我正试图从数组中删除所有重复的行，但找不到一种高效或优雅的方法。我尝试了一个嵌套循环，但是，有人告诉我这是不好的做法(我的实现出现了错误，而且很难看)。

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;
        }
    }
}

Can anyone offer suggestions?

谁能提供建议吗?

5 个解决方案

#1

Create an object/map in javascript and keep the indexes of the unique objects, store "min(start,end):max(start,end)" as a key and index as a value. Here is an implementation of your question in javascript:

在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]]);
    }
}

#2

You can do like this. I guess this is very fast since there are no searches at all. One Array.prototype.reduce() operation to construct both the hash table (lookup table) and the reduced object at the same time. Then mapping the object keys to get the result. Here it is;

你可以这样做。我想这是非常快的，因为根本没有搜索。一个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);

Well giving it a second thought i eliminated the redundant Object.keys() portion. Now this is nothing more than a single Array.prototype.reduce() pass all completed in just O(n). I suppose this might be as far as it gets concerning the performance. Check it out.

好吧，再考虑一下，我去掉了冗余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);

Well ok yes i have to agree it looks a little cryptic but it is very simple.

好吧，是的，我不得不承认它看起来有点神秘，但它非常简单。

• We are using Array.prototype.reduce() method with an initial value here. This is our initial value {"result":[]}. When reducing our routeArr array our initial element to start with is now an object with a single property named result and value of an empty array.
• 我们正在使用具有初始值的Array.prototype.reduce()方法。这是我们的初始值{"result":[]}。当减少我们的routeArr数组时，我们的初始元素现在是一个对象，它具有一个名为result的属性和一个空数组的值。
• reduce has been provided with an anonymous callback function which takes two arguments (p,c) p stands for previous and c stands for current. So in the first run p is our initializing object, i mean this {"result":[]} and c is the item at index 0 of the array (routeArr) that we have called reduce upon. So in the first round c is {start: 1, end: 2}.
• reduce已经提供了一个匿名回调函数，该函数接受两个参数(p,c) p代表前面，c代表当前。在第一次运行中，p是我们的初始化对象，我的意思是{"result":[]}和c是我们调用reduce的数组(routeArr)的索引0处的项。所以在第一轮c是{start: 1, end: 2}。
• In the beginning of every round we check if our p object contains a property which represent the current elements values in both orders. So the check comes like this !(p[c.start+"-"+c.end] || p[c.end+"-"+c.start]) which in human terms means "is it true that you don't have a string property like c.start-c.end or c.end-c.start".. So for example in the first round the check is like "is it true that you don't have a string property like "1-2" or "2-1". If it has (false) we do nothing but if it hasn't we perform the following actions;
• 在每轮开始时，我们检查p对象是否包含一个属性，该属性表示两个订单中的当前元素值。所以支票是这样的!它在人类术语中的意思是“你真的没有像c.start-c这样的字符串属性吗?”结束或c.end-c.start”. .举个例子，在第一轮的时候支票是这样的"你真的没有一个字符串属性像"1-2"或"2-1"如果它有(假)我们什么也不做，但如果它没有，我们就执行以下操作;
• && (p[c.start+"-"+c.end] = true, p.result.push(c)); return p;. OK the first && ties the two instructions in the parens to the condition of the previous instruction to evaluate to true. In a && b instruction JS engine will only evaluate b if a evaluates to true. So you got it. Again in human terms this is what happens. "is it true that you don't have a string property like "1-2" or "2-1" turns true and we create a property "1-2" with a value true. So in next rounds if we meet a 1-2 or 2-1 we will do nothing at all. Then we push this current object to the result property of the same object (p.result) to become a unique representative of all of it's duplicates or twins. Then we return p for a healthy continuation of the reduce cycles.
• & &(p[c.start +“-”+ c。结束]= true,p.result.push(c));返回p;。好的，第一个&&把这两个说明与先前的说明的条件联系起来，以使其值为真。在a & b指令中，JS引擎只会在a为真时才会对b进行评估。所以你明白了。从人类的角度来说，这就是发生的事情。你没有像“1-2”或“2-1”这样的字符串属性是正确的，我们创建的属性为“1-2”，其值为true。所以在接下来的比赛中，如果我们遇到1-2或2-1，我们什么都不会做。然后我们将当前对象推到同一个对象的result属性(p.result)，从而成为所有副本或双胞胎的唯一代表。然后我们返回p，以使减少循环健康地继续下去。

I hope it is clear.

我希望它是清楚的。

#3

Here is a general solution to the problem of removing duplicate values from javascript arrays:

对于从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;
}

Applied to your given 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;
});

#4

Your nested loop methodology is 'ugly'- but that isn't your issue.

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

Your implementation errors are resulting from the fact that both of your for loops assume the array structure won't change as you're mutating it, which is causing you to skip over some items in the array.

实现错误的原因是，您的两个for循环都假设数组结构不会随着您的突变而改变，这会导致您跳过数组中的某些项。

'i' and 'j' are 'stupid' incrementers - That for loop isn't telling the code to go to the next item in the array with each iteration, it's telling it to go to (array[last_index_i_used+1] - So when you splice something the array you're looking at changes, and the next item in line gets passed over.

“我”和“j”是“愚蠢的”增量器,for循环不是告诉代码去与每个迭代数组中的下一个项目,它告诉它去(数组(last_index_i_used + 1),所以当你拼接数组你看变化,和下一项传递过去。

I see a lot of fancy array methods and ES6 suggestions, but I assume from your question that you are still a bit new to JS, and could use some time building fundamentals (no offense intended).

我看到了许多花哨的数组方法和ES6建议，但是我从您的问题中假设您对JS还是有点陌生，并且可能需要一些时间来构建基础(无意冒犯)。

Try a recursive decrementing function:

尝试递归递减函数:

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);

I like that better than a nested for loop as you are never hitting the same value more often than you need to, which keeps performance consistent regardless of the size of your array.

与嵌套的for循环相比，我更喜欢它，因为您不会比需要更频繁地命中相同的值，无论数组的大小如何，它都保持性能一致。

But you might want to ask yourself if whatever is defining 'routeArr' is doing whatever it's doing in a way that is intelligent - At best, it seems like it's wasting memory and CPU storing data in an inefficient way.

但你可能会问自己，定义“routeArr”的东西是否以一种智能的方式来做它正在做的事情——充其量，它似乎是在以一种低效的方式浪费内存和CPU。

#5

I've wrote the function below to do it neatly

我把下面的函数写得很简洁

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);
}