Efficient way to dedupe large list of arrays

Question

I have a very large array of arrays (on the order of 960,799 entries or possibly much larger). I need to process it into a new array such that:

1. Each sub-array contains no duplicates.
2. The main array contains no duplicate sub-arrays.

The problem is that "duplicate sub-arrays" must include arrays with the same values in a different order. In other words, if I had these sub-arrays:

[[1,2,3], [1,2,3], [3,1,2]]

They would all be considered duplicates and only one would be kept (any of them, it doesn't matter; I've been just keeping the first one; it's also fine if the order of the selected sub-array doesn't actually match, i.e. if the order of elements in the sub-array changes during processing).

My attempted solution has been to map all the sub-arrays into strings based on de-duping the sub-array, sorting it, and joining it with a delimiter. Then I de-dupe that final array, then map them back to arrays with a split. It works, but the process is extremely slow. It takes over 30 seconds for a single pass, and since the array I end up processing can grow exponentially larger, this is not acceptable. I need a more efficient algorithm.

Here's the code I'm using now that's slow (ret is the input array):

const stringList = ret.map(list => {
    return [...new Set(list)].sort().join('|');
});
const hashSet = new Set(stringList);
const output = [...hashSet].map(str => str.split('|'));

Can anyone help me get the same result more efficiently? Thanks.

EDIT

To elaborate, I'm getting these massive input arrays by calculating what is essentially the power set of some input of strings. This is the code; if it's possible to stop it from producing duplicate entries in the first place, that would work well, too, I think:

// Calculate the Cartesian product of set s
function cart(s) {
    return s.reduce((acc, val) => {
        return acc.map((x, i) => {
            return val.map(y => {
                return x.concat([y]);
            });
        }).flat();
    }, [[]]);
}

// Use the Cartesian product to calculate the power set of set s
function pset(s) {
    let ret = [];
    for (let i = 0; i < s.length; ++i) {
        const temp = [];
        for (let j = 0; j <= i; ++j) {
            temp.push([].concat(s));
        }
        ret = ret.concat(cart(temp));
    }
    return ret;
}

Answer 1

You could generate the power set without duplicates.

function pset(array) {
    function iter(index, temp) {
        if (index >= array.length) {
            temp.length && result.push(temp);
            return;
        }
        iter(index + 1, temp.concat(array[index]));
        iter(index + 1, temp);
    }
    var result = [];
    iter(0, []);
    return result;
}

console.log(pset(['a', 'b', 'c']));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

Given that I'm not able to perform a benchmark with real data, I can't verify how much faster this approach is for your use case, but by using basic for loops and avoiding functional code as much as conveniently possible, I've come up with the following:

const ret = [[1, 2, 3], [1, 2, 3], [3, 1, 2], [1, 4, 5], [4, 1, 5]];

function ascending (a, b) {
  // works for strings and numbers
  return -(a < b) || +(a > b);
}

function ascending2d (a, b) {
  const aLength = a.length;
  const bLength = b.length;
  const length = Math.min(aLength, bLength);

  for (let i = 0; i < length; ++i) {
    const difference = ascending(a[i], b[i]);
    if (difference !== 0) return difference;
  }

  return aLength - bLength;
}

for (let i = 0; i < ret.length; ++i) {
  ret[i].sort(ascending);
}

ret.sort(ascending2d);

const output = [ret[0]];

for (let i = 1; i < ret.length; ++i) {
  const value = ret[i];
  if (ascending2d(ret[i - 1], value) !== 0) output.push(value);
}

console.log(output);

Let me know if this is an improvement over your current approach. You can always improve performance further by profiling your code and looking for bottlenecks that can be re-written.

Performance Benchmark

I've published a benchmark using the test data in my example here, comparing your original solution, my solution, and Andrew's solution. I couldn't include Nina's for comparison because hers doesn't perform deduplication on ret, instead it modifies the generation of ret.

Answer 3

EDIT: Nevermind, my implementation had no benchmarks. It is slower. Due to the underlying implementation of JSON.parse, JSON.stringify, and the default algorithm for Array#sort.

Since you're looking for bleeding edge performance, it's hard to get an elegant solution. If you instantiate an object with Object.create(null) you minimize the overhead for O(1) insertion. It creates a POJO with no prototype. You also don't need to check in the for in loop for Object.hasOwnProperty, because there's no prototype to search.

const ret = [[], [1, 2, 3], [3, 1, 2], [1, 4, 5], [4, 1, 5]];

const hashMap = Object.create(null)
function createUniqArraysOfPrimitiveArrays(ret) {
  for (let i = 0; i < ret.length; i++) {
    const currEl = ret[i]
    if (currEl.length === 0) {
      hashMap['[]'] = null
    } else if (currEl.length === 1) {
      hashMap[`[${currEl[0]}]`] = null
    } else {
      hashMap[JSON.stringify(currEl.sort())] = null
    }
  }
  const outputArray = []
  for (const array in hashMap) {
    outputArray.push(JSON.parse(array))
  }
  return outputArray
}

console.log(createUniqArraysOfPrimitiveArrays(ret))