JS: Extract only unique attribute objects from array

user_11613622 0
Viewed 102

I am currently working on developing an API, where I need to make a function to extract "completely" unique objects, i.e. no attribute match in any of the objects.

I have an array of objects of fixed schema like: (Modified this)

let arr = [{
      "a": "a1",
      "b": "b1",
      "c": "c1",
      "d": "d1",
      "e": "e1"
    },
    {
      "a": "a2",
      "b": "b2",
      "c": "c2",
      "d": "d2",
      "e": "e2"
    },
    {
      "a": "a3",
      "b": "b3",
      "c": "c2", // matching attribute
      "d": "d3",
      "e": "e3"
    },
    // values in previous object should not affect this unique object:
    {
      "a": "a3",
      "b": "b3",
      "c": "c3",
      "d": "d3",
      "e": "e3"
    },
    // … more objects here, maximum 200 * 33 objects
  ]

And I want the result as:

[
  {
    "a": "a1",
    "b": "b1",
    "c": "c1",
    "d": "d1",
    "e": "e1"
  },
  {
    "a": "a2",
    "b": "b2",
    "c": "c2",
    "d": "d2",
    "e": "e2"
  },
  {
    "a": "a3",
    "b": "b3",
    "c": "c3",
    "d": "d3",
    "e": "e3"
  },
  // … 
]

In case of matching attribute, the object which is encountered first in the array shall be kept and the other be discarded. Different properties will never have overlapping values.

My current implementation (wrong, see comments):

for (let i in arr[0]) {
    let map = new Map();
    arr = arr.filter(obj => map.get(obj[i]) ? false : map.set(obj[i], true));
}
console.log(arr);

I̶s̶ ̶t̶h̶e̶r̶e̶ ̶a̶n̶y̶ ̶b̶e̶t̶t̶e̶r̶ ̶(̶m̶o̶r̶e̶ ̶e̶f̶f̶i̶c̶i̶e̶n̶t̶)̶   What is the correct way to do this?

javascript
4 Answers

I'd make a Set of all values found so far. When checking a new object, check if any of its values are included in the set: if so, exclude it, otherwise add all values to the set:

let arr = [{
      "a": "a1",
      "b": "b1",
      "c": "c1",
      "d": "d1",
      "e": "e1"
    },
    {
      "a": "a2",
      "b": "b2",
      "c": "c2",
      "d": "d2",
      "e": "e2"
    },
    {
      "a": "a3",
      "b": "b3",
      "c": "c2", // matching attribute
      "d": "d3",
      "e": "e3"
    },
    // values in previous object should not affect this unique object:
    {
      "a": "a3",
      "b": "b3",
      "c": "c3",
      "d": "d3",
      "e": "e3"
    },
    // … more objects here, maximum 200 * 33 objects
];
const valuesFound = new Set();
const uniques = arr.filter((obj) => {
  const vals = Object.values(obj);
  if (vals.some(val => valuesFound.has(val))) {
    return false;
  }
  for (const val of vals) {
    valuesFound.add(val);
  }
  return true;
});
console.log(uniques);

This has the lowest computational complexity possible - there aren't any nested loops except the .some, and that .some's callback is O(n), since it's using Set.prototype.has.

user_95152070

I think this is more concise. The moment something returns false every will shortcircuit.

arr.filter(function(o){
    var that = this,
        vals = Object.values(o),
        pass = vals.every(v=>!~that.indexOf(v));
    return pass && that.push.apply(that,vals);
},[])

Change the lamba to regular func and it work everywhere, not only ES6.

user_94104120

It should be faster to only track values, rather than looking up values by key, especially for each iteration.

Below uses one global cache to track values and a local cache (i.e. added) to provide cleanup when an object isn't unique (so values aren't retained in the cache).

const data = getData()
const cache = {}

const results = data.filter(obj => {
  const added = {}
  for (const v of Object.values(obj)){
    if( cache[v] ){
      Object.keys(added).forEach(v=>delete cache[v])
      return false
    }
    else
      added[v] = cache[v] = 1
  }
  return true
});

console.log(results);

/* ===================================================== */
function getData() {
  return [{
      "a": "a1",
      "b": "b1",
      "c": "c1",
      "d": "d1",
      "e": "e1"
    },
    {
      "a": "a2",
      "b": "b2",
      "c": "c2",
      "d": "d2",
      "e": "e2"
    },
    {
      "a": "a3",
      "b": "b3",
      "c": "c2", // matching attribute
      "d": "d3",
      "e": "e3"
    },
    // values in previous object should not affect this unique object:
    {
      "a": "a3",
      "b": "b3",
      "c": "c3",
      "d": "d3",
      "e": "e3"
    },
    // … more objects here, maximum 200 * 33 objects
  ];
}

Option 2

Instead of adding to cache and then removing those values when not unique, it might be worthwhile to:

  1. only check cache & added upfront and add to added in the loop
  2. add added to cache after the loop (only reached if the entire object is unique)

That way you don't have to go through and do cleanup, which could be expensive if there are a lot of values. Any performance tuning (optimizations) depends on the data (size and type) and might require different adjustments to best suit the data.

That would look like:

const data = getData()
const cache = {}

const results = data.filter(obj => {
  const added = {}
  for (const v of Object.values(obj)){
    if( cache[v] || added[v])
      return false
    else
      added[v] = 1     // store in local cache
  }
  Object.keys(added).forEach(v=>cache[v]=1)   // store in permanent cache
  return true
});

console.log(results);

/* ===================================================== */
function getData() {
  return [{
      "a": "a1",
      "b": "b1",
      "c": "c1",
      "d": "d1",
      "e": "e1"
    },
    {
      "a": "a2",
      "b": "b2",
      "c": "c2",
      "d": "d2",
      "e": "e2"
    },
    {
      "a": "a3",
      "b": "b3",
      "c": "c2", // matching attribute
      "d": "d3",
      "e": "e3"
    },
    // values in previous object should not affect this unique object:
    {
      "a": "a3",
      "b": "b3",
      "c": "c3",
      "d": "d3",
      "e": "e3"
    },
    // … more objects here, maximum 200 * 33 objects
  ];
}

user_104082800

it is verified :)

     let ids=[]
     let filtered_arr=arr.filter(ar=>{
      if(ids.includes(ar.c)){ 
        return false
       }    
       else{
        ids.push(ar.c);
        return true;}  
     }  
      )
    console.log(filtered_arr);
user_89590940
Related