8 ways to remove duplicates from Array in TypeScript

How can we code when we want to get unique values from an array? Which one is the fastest? I will show the performance result at the end.

Distinct an array of primitive values

The arrays that we will use are the following. Number and string array. We need to handle an object array differently, so let’s start with a simple one.

const primitiveNumbers = [1, 2, 3, 2, 4, 5, 6, 3, 1];
// unique values -> [ 1, 2, 3, 4, 5, 6 ]
const primitiveStrings = [
    "aaa", // duplicated 1
    "bbb",
    "ddd", // duplicated 2
    "aaa", // duplicated 1
    "eee",
    "ccc",
    "ddd", // duplicated 2
];
// unique values -> [ 'aaa', 'bbb', 'ddd', 'eee', 'ccc' ]

We need to execute several functions to see if those results are the same. I prepare the generic function to make it easy.

type UniqFunc<T> = (array: T[]) => T[];
function test<T>(array: T[], funcs: UniqFunc<T>[]) {
    for (const func of funcs) {
        const start = performance.now();
        const result = func(array);
        const elapsedTime = performance.now() - start;
        console.log(`${func.name}, time: ${Math.round(elapsedTime)}`);
        console.log(result);
    }
}

const funcsForPrimitive = [
    uniqByForOf,
    uniqByForEach,
    uniqByReduce,
    uniqByFilter,
    uniqBySetWithArrayFrom,
    uniqBySetWithSpread,
];
test(primitiveNumbers, funcsForPrimitive);
test(primitiveStrings, funcsForPrimitive);

All functions are defined as UniqFunc type that requires array variable. We can specify anything as far as it’s an array but I will use only number/string/object in this post.
test function measure how long it takes to complete the function’s work. funcsForPrimitive stores functions that I will show in this post.

Comparing values one by one

The first idea is to loop the array and check whether the item has already been shown or not. Add the value if it has not been in result variable.

function uniqByObject<T>(array: T[]) {
    const result: T[] = [];
    for (const item of array) {
        if (!result.includes(item)) {
            result.push(item);
        }
    }
    return result;
}

If you prefer forEach you can write it like this below.

function uniqByForEach<T>(array: T[]) {
    const result: T[] = [];
    array.forEach((item) => {
        if (!result.includes(item)) {
            result.push(item);
        }
    })
    return result;
}

Using Array.prototype.reduce

There are other ways if you don’t want to define a middle-man that stores results.

function uniqByReduce<T>(array: T[]): T[] {
    return array.reduce((acc: T[], cur: T) => {
        if (!acc.includes(cur)) {
            acc.push(cur);
        }
        return acc;
    }, [])
}

The first arg acc of reduce function callback is an accumulator that will be the return value. The second arg cur is the current value. What this does is basically the same as previous examples.

Using Array.prototype.filer

It can be written with one line if using the filter function.

function uniqByFilter<T>(array: T[]) {
    return array.filter((value, index) => array.indexOf(value) === index);
}

The behavior of indexOf is following.

The indexOf() method returns the first index at which a given element can be found in the array, or -1 if it is not present.

This table shows the relationships.

Since indexOf function returns the first index the result of indexOf is different from the current index of the array.

Using Map

Map offers key-value object. If it receives the same key name it updates the value. It means that we don’t have to check the values in there if using the value as a key.

function uniqByMap<T>(array: T[]): T[] {
    const map = new Map();
    for (const item of array) {
        map.set(item, item);
    }
    return Array.from(map.values());
}

map.values() returns IterableIterator type but not array. It should be converted to Array type. That’s why Array.from() is used here.

Using Set object

I think it’s the easiest way to do it. What we have to do is just put the array into the constructor. Set object stores unique values. It removes the duplicates.

function uniqBySetWithArrayFrom<T>(array: T[]): T[] {
    return Array.from(new Set(array));
}
function uniqBySetWithSpread<T>(array: T[]): T[] {
    return [...new Set(array)];
}

Unfortunately, it can’t be used for an object because it refers to a reference but not the values in the object.

Distinct an array of key-value object

The examples that I showed above can’t be used for an object. An object isn’t as simple as a primitive value because it refers to a reference. The following two objects have the same values but the result is false.

const obj1 = {foo: 1, hoge: 2};
const obj2 = {foo: 1, hoge: 2};
console.log(obj1 === obj2);
// false

If the same reference is assigned to another variable the result becomes true.

const obj1 = {foo: 1, hoge: 2};
const obj3 = obj1
console.log(obj1 === obj3);
// true

The objects are defined somewhere in the address space. The reference value of the object is the address. obj1 and obj2 are respectively stored in different addresses obj1 === obj2 becomes false.

To compare objects we need to check the values one by one. We will use the following object.

const objects = [
    { name: "aaa", price: 50 },
    { name: "bbb", price: 30 }, // duplicated 1
    { name: "ccc", price: 80 }, // duplicated 2
    { name: "aaa", price: 15 },
    { name: "bbb", price: 30 }, // duplicated 1
    { name: "ccc", price: 80 }, // duplicated 2
];
// Unique values
// [
//   { name: 'aaa', price: 50 },
//   { name: 'bbb', price: 30 },
//   { name: 'ccc', price: 80 },
//   { name: 'aaa', price: 15 }
// ]

Using lodash.isEqual

The way for object is basically the same as the one for primitive values. Loop the array and check the value one by one. The difference is to use lodash.isEqual in order to compare all primitive values in the object.

function uniqForObject<T>(array: T[]): T[] {
    const result: T[] = [];
    for (const item of array) {
        const found = result.some((value) => isEqual(value, item));
        if (!found) {
            result.push(item);
        }
    }
    return result;
}

This function can be used for primitive values as well.

Performance comparison

Let’s compare the functions’ performance! I used Node.js version 14.13.0 for the experiment. This is the code for it.

type UniqFunc<T> = (array: T[]) => T[];
function test<T>(array: T[], funcs: UniqFunc<T>[], loopCount = 1) {
    const times: number[] = [];
    for (const func of funcs) {
        const start = performance.now();
        for (let i = 0; i < loopCount; i++) {
            const result = func(array);
        }
        const elapsedTime = performance.now() - start;
        times.push(Math.round(elapsedTime));
    }
    return times;
}

function generatePrimitiveArray(length: number, range: number): number[] {
    const result = [];
    for (let i = 0; i < length; i++) {
        const value = Math.floor(Math.random() * range);
        result.push(value);
    }
    return result;
}

function measure() {
    const settings = [
        { arrayLen: 10, loopRangeS: 10000, loopRangeE: 200000, step: 5000 },
        { arrayLen: 10, loopRangeS: 100000, loopRangeE: 500000, step: 50000 },
        { arrayLen: 100, loopRangeS: 100000, loopRangeE: 500000, step: 50000 },
        { arrayLen: 1000, loopRangeS: 100000, loopRangeE: 500000, step: 50000 },
    ];
    for (const setting of settings) {
        console.log(`length: ${setting.arrayLen}`);
        const array = generatePrimitiveArray(setting.arrayLen, 10);

        const titles = funcsForPrimitive.map(x => x.name).join(",");
        console.log(`loop count,${titles}`);
        for (let i = setting.loopRangeS; i <= setting.loopRangeE; i += setting.step) {
            const times = test(array, funcsForPrimitive, i);
            const data = times.join(", ");
            console.log(`${i}, ${data}`);
        }
        console.log();
    }
}

measure();

The value range is set to 0 – 9. The same array is used in the loop for all functions to compare the performance precisely. If you want to try it yourself you can clone my repository or just copy and paste the code. You can change the range if you change the second argument value of generatePrimitiveArray function.

BlogPost/src/simple-code/one-file/distinct.ts at master · yuto-yuto/BlogPost

Contribute to yuto-yuto/BlogPost development by creating an account on GitHub.

github.com

I tried the following code in order to make it faster.

async function testAsync<T>(array: T[], funcs: UniqFunc<T>[], loopCount = 1) {
    const promises = funcs.map((func) => execute(array, func, loopCount));
    const times = await Promise.all(promises);
    return times.map(x => Math.round(x));
}

async function execute<T>(array: T[], func: UniqFunc<T>, loopCount: number) {
    const start = performance.now();
    for (let i = 0; i < loopCount; i++) {
        const result = func(array);
    }
    return performance.now() - start;
}

However, it didn’t improve it because promise works on a single thread. It can improve the performance for I/O-related work for example but not for CPU-intensive work. To improve the performance for CPU-intensive work we need another thread. We can make it faster by worker thread but I don’t do it here.

You might want to check this post if you are not familiar with Promise.

async/await with Promise in TypeScript

Using promise makes the code much faster. This post explains the basic and advanced usage.

www.technicalfeeder.com

2020.10.14

Array Length 10

The vertical line shows time (ms). uniqByReduce is top and second is uniqByForEach.

Array Length 10 loop 10000 to 200000

The result for the loop count of less than 200000 looks not good. I tried it again with a smaller loop count increment.

The difference is small. Let’s see the result with the log version.

Top is uniqByForEach but 2nd to 4th are similar. They are uniqByReduce, uniqByForOf and uniqByFilter.

Array Length 100

uniqForObject is too slow to compare. Top is uniqForEach and second is uniqByReduce.

Array Length 1000

Wow, uniqBySetWithSpread or uniqBySetWithArrayFrom is top here! There are almost the same. Next is uniqByMap

Conclusion

We learned many ways to remove duplicated values from an array. We need to use a library such as lodash to compare two objects deeply but we can easily implement primitive values without a library.

uniqForEach, uniqByReduce, uniqByFilter or uniqByForOf is good enough for most cases. Using Set object is the best if you need to work with a big array and need to consider the performance.

Check the following post if you also want to know how to remove an element.

TypeScript Remove elements from an object array

Remove method doesn't exist on Array interface. So we need to implement it ourselves. This article explains how to remove elements from number/string/object array.

www.technicalfeeder.com

2022.11.23