3
\$\begingroup\$

I've made this function which returns a copy of a given array with no duplicated elements in it.

/**
 * Returns an array with only unique elements. Based
 *  upon an array which might possibly contain duplicates.
 * @param { array } arrayToCheck
 * @return { array }
 * @throws { Error } when given parameter is
 *  detected invalid.
 */

function createArrayWithoutDuplicates(arrayToCheck) {
  'use strict';
  var arrayWithoutDuplicates = [];

  if (!arrayToCheck || !Array.isArray(arrayToCheck)) {
    throw new TypeError('Array expected but ' +
      typeof arrayToCheck + ' found.');
  }

  arrayToCheck.forEach(function(element) {
    if (!arrayWithoutDuplicates.includes(element)) {
      arrayWithoutDuplicates.push(element);
    }
  });

  return arrayWithoutDuplicates;
}

// --------------------------------------------------
// --------- JUST USAGE-DEMO ------------------------
// -- ... not that important, folks! ;) -------------

var arr = [0, 1, 2, 3, 4, 5, 6, 7, 1, 2, 7, 8];
var arr2 = ['a', 'b', 'c', 'd', 'e', 'a', 'b'];

function testCreateArrayWithoutDuplicates(arrayWithDuplicates) {
  let unique = createArrayWithoutDuplicates(arrayWithDuplicates);

  console.log('With duplicates: %o', arrayWithDuplicates);
  console.log('Without duplicates: %o', unique);
  console.log('Array with duplicates: %s', arrayWithDuplicates.length);
  console.log('Array without duplicates: %s', unique.length);
}

testCreateArrayWithoutDuplicates(arr);
console.log('\n');
testCreateArrayWithoutDuplicates(arr2);

As far as I can say: It is doing alright.

But I would like to know:

Is there a better pattern for solving the task of getting a duplicate-free array?

If someone knows a better solution then I would appreciate his/her answer.

Moreover:

- Is my documentation understandable and done in a good way? Or do I have to improve?

- Is my parameter validation done correctly?

Looking forward to read your answers. :)

\$\endgroup\$
1
\$\begingroup\$

Agreeing with Mike's comments, I would point out the following possible syntax improvements:

if (!arrayToCheck || !Array.isArray(arrayToCheck)) {
    throw new TypeError('Array expected but ' +
      typeof arrayToCheck + ' found.');
}

I think there is no need for !arrayToCheck. I just checked and Array.isArray(null) and Array.isArray(undefined) returns false. Also I would use template literals instead of string concatenation.

So you can write something like this:

if (!Array.isArray(arrayToCheck)) {
    throw new TypeError(`Array expected but ${typeof arrayToCheck} found.`);
}

Also, I am not sure there is a point of creating a new array and just returning it. Instead you can just filter and return a new array:

return arrayToCheck.filter((e, i, arr) => i === arr.indexOf(e));

Also, variables names can be shorter I think. So finally you might have something like:

function removeDuplicates(array) {
  'use strict';
  if (!Array.isArray(array)) 
    throw new TypeError(`Array expected but ${typeof array} found.`);
  return array.filter((e, i, arr) => i === arr.indexOf(e));
}

And I am not really sure you need comments, because removing duplicates is a an easy thing to do and the function name should be self-explanatory.

\$\endgroup\$
3
\$\begingroup\$

Sets are basically like magic for pulling unique values from an array; since, by their very definition, any Set will only hold one copy of any specific value, no matter how many times you try to add it.

That, combined with the ability of Sets to be easily turned back into arrays using the spread operator, makes the overall task rather straight-forward:

function noDuplicates(arr){
  return [...new Set(arr)]
}

It actually makes the task so quick and easy that it begs the question of whether a function is even needed; since anytime you need to pull only the unique values of an array you can simply use:

var unique = [...new Set(arr)] 

Both the function-based and non-function-based approaches are fully viable options though, so choose whichever you prefer. Hope this was helpful!

\$\endgroup\$
1
  • \$\begingroup\$ Indeed helpful & absolutely awesome. Thanks. \$\endgroup\$ – michael.zech Mar 27 '17 at 10:54
2
\$\begingroup\$

Performance-wise, the fact that you are using includes function (which must iterate the entire array in the worst case) inside of a loop, means you have \$\mathcal{O}(n^2)\$ solution, which is not ideal. If you might be working with large input arrays, this could really perform poorly. If you do not need to consider such cases, what you have is probably fine.

Some alternate implementations might include:

  • sorting the array first, which would allow you to then iterate the sorted result, only inserting new values into result array when current values changes. This would operate in \$\mathcal{O}(n \log n + n)\$. This of course would not preserve any ordering in the array, which may or may not be important to you.
  • reading the input array into object map as keys and then iterating the resulting object properties back into array. This would operate in \$\mathcal{O}(2n)\$ but would cause need to also add some logic when building the map to check and store type of values (integer, string, etc.) so that you can restore the proper typing when building the result array since JavaScript would cast integer values as strings when writing the object map keys. Again, order would not be preserved.

I also wonder how resilient this code is for more complex values in input array. For example, what is desired behavior if an array of objects is passed?

You function name seems overly verbose. Perhaps just arrayUnique?

Since you tagged this for ECMA6, you might consider using let instead of var to initialize your result array, just as a matter of habit, though there is no meaningful difference here.

\$\endgroup\$
1
  • \$\begingroup\$ Can sadly accept only one answer. Although both answers gave me valuable thoughts to consider. Thank you both for your time answering my question. I really appreciate it. \$\endgroup\$ – michael.zech Mar 27 '17 at 2:54
1
\$\begingroup\$

In ES6, a duplicate-free list is a Set. So, you can convert your array to a Set (which will remove all duplicates) and then you can convert it back to an array. The advantage of using a Set is that it will accept any type of object or primitive as a key, including objects and it uses a relatively fast lookup to see if something is already in the Set and the constructor for a Set will take an array to automatically build the Set from the initial array.

function deDup(arr) {
    return Array.from(new Set(arr));
}

If you wanted to just remove elements from the existing array without creating a new array (e.g. in place), you could do that like this:

function removeDups(arr) {
    let items = new Set();
    let i;
    for (i = 0; i < arr.length; i++) {
         if (items.has(arr[i]) {
             arr.splice(i, 1);
             i--;
         } else {
             items.add(arr[i];
         }
    }
    return arr;
}

If you want to do this in ES5 (without the benefit of a Set object), then you can use an object with properties as your fake Set, but only as long as the values in your array have a simple and unique string conversion. It won't work for Objects in the array, for example because they don't have a unique string representation which is needed to represent them as a property on an object. And, it will treat 1 and "1" as duplicate values since they both have the same string conversion. So, with those limitations, you could do this in ES5 like this:

function deDup(arr) {
    var items = {};
    var result = [], item;
    for (var i = 0; i < arr.length; i++) {
        item = arr[i];
        if (!items.hasOwnProperty(item)) {
           result.push(item);
           items[item] = true;
        }
    }
    return items;
}

There is a more complicated way around the limitations here that involves adding type info to the string key and involves adding a custom property on objects to identify them with a unique string key. These techniques are used in the ES5-compatible Set object here (Mimicking Set objects in Javascript) so it would probably be best to just use that object if you really wanted that mixed type functionality in ES5.

\$\endgroup\$
1
  • \$\begingroup\$ Great techniques and approaches. Many thanks. \$\endgroup\$ – michael.zech Mar 27 '17 at 11:11
1
\$\begingroup\$

My solution

Thanks to Dan for suggesting template literals for input validation.

const myUnique = (input) => {
    'use strict'
    let result = [];

    if (!Array.isArray(input)) {
        throw new TypeError(`Array expected but ${typeof input} found.`);
    }

    for (let i = 0; i < input.length; i++) {
        if (result.indexOf(input[i]) === -1) {
            result.push(input[i]);
        }
    }

    return result;
};

Solutions' comparison

Benchmark's result

Comments about your code

  • Your documentation is fine. The sole fact that you document your code is already a lot! If I could change anything, I would reword and shorten it a bit.
  • You could and even requested to use ES6 (by tagging with ecmascript-6 tag), so you should go for it.
  • !Array.isArray(arrayToCheck) already covers all and more cases than !arrayToCheck and as such the latter is redundant. I've tested it and for null, undefined, NaN and Infinity isArray() will behave as expected.
  • Your code's probably biggest bottleneck is includes() in forEach(); that gives you O(n^2) complexity.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ The speed depends on the array size. Naturally, creating a Set has a big overhead but if the array is huge and the element values aren't clamped to a small set, indexOf takes exponentially more time to complete. For example on 10k elements indexOf is 100 times slower and I'm not even sure how many hours or days it'll take to process 100MB... \$\endgroup\$ – wOxxOm Mar 29 '17 at 7:06
  • \$\begingroup\$ @wOxxOm: That's absolutely true, but for majority of cases using regular indexOf() will be faster in practice. Using Set or any other duplicate-free structure will be of course better choice for larger inputs. \$\endgroup\$ – Przemek Mar 29 '17 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.