returning unique array with Set.

[u/Chawki_]

[u/robotsympathizer]

I saw this as a solution to a Leetcode problem where the challenge was to remove duplicates from a sorted array of integers.

[u/ScottRatigan → u/robotsympathizer]

This would kind of be missing the point of what the questions was asking then. Having a sorted array hints at the type of solution they're looking for. In terms of space complexity, this would require 2 full lists of data whereas an optimal solution would have just 1. If the list was unsorted, you'd need an interim data structure anyway and I guess this would be fine.

I guess my point is, in the real world, this code is fine for reasonably sized arrays but for leetcode it's missing the point.

[u/HeinousTugboat → u/ScottRatigan]

I'd love to see actual performance benchmarks for this. Set can be more aggressively optimized than Array can by the JIT compiler. Even though on an abstract level, it may have more space complexity, the compiler/runtime will likely do that work for you and do it faster.

Point is, I'd argue that in JavaScript specifically, deferring to Set is likely the more correct answer.

[u/gigastack → u/HeinousTugboat]

I was curious so I made a quick test:

var arr = [...Array(1000000)].map(() => Math.floor(Math.random() * 1000)).sort();

function setMethod() {
    var t0 = performance.now();
    var set = [...new Set(arr)]
    var t1 = performance.now();
    console.log('set ms:', t1 - t0);
    return set
}

function leetMethod() {
    var t0 = performance.now();
    var set = [arr[0]];
    var lastVal = arr[0];
    for(let i = 1; i < arr.length; i++) {
        var val = arr[i];
        if (val !== lastVal) {
            set.push(val);
            lastVal = val;
        }
    }
    var t1 = performance.now();
    console.log('leet ms', t1 - t0);
    return set
}

var set = setMethod();
var leet = leetMethod();

console.log('set len:', set.length);
console.log('leet len:', leet.length);

Edit: my original post had the leet method as slightly faster. But it is actually dramatically faster. Here's the output I'm getting:

set ms: 68
leet ms: 7

...but in fairness, on the front-end, I'd use the set method for readability. But leetcode is more about getting hired than anything.

[u/HeinousTugboat → u/gigastack]

That's interesting. I'm guessing you're using a slightly older browser and/or one that has a crappy Set implementation. On my MBP in Firefox Dev:

set ms: 15 
leet ms 163

Edit: Even more interesting.. when I run it in the console, it's an order of magnitude faster. When I toss it on JSBench.me, it flips and the array becomes an order of magnitude faster. If I had to guess, once the code heats up the compiler (at least Spidermonkey's, I guess) rewrites the Array.

[u/gigastack → u/HeinousTugboat]

I ran the test in the latest version of Chrome. In Firefox, I'm seeing the set implementation 10x faster than the for loop, just like you are posting. Interesting.

[u/gigastack → u/[deleted]]

It's a 6 or 7 year old Windows 10 desktop. I keep it around for games but do dev work on my much newer MacBook.

I'm going to print out this comment to show my wife, lol. Christmas is just around the corner.

[u/robotsympathizer → u/ScottRatigan]

I know, that's why it was funny.

[u/littlebluebrown → u/robotsympathizer]

I guess you watched the tech sith video.

[u/robotsympathizer → u/littlebluebrown]

Nope

[u/dhudhudhadha → u/robotsympathizer]

Then?

[u/__ibowankenobi__]

now go do that with objects.

[u/Chawki_ → u/__ibowankenobi__]

what you mean, returning unique objects?

[u/__ibowankenobi__ → u/Chawki_]

aha, that wouldn't work would it.

[u/Ebola300 → u/__ibowankenobi__]

You could assign to object keys and then return the result of Objext.keys()

[u/[deleted] → u/Ebola300]

Error: "Objext" is undefined

[u/dhudhudhadha → u/Ebola300]

What?

[u/Ebola300 → u/dhudhudhadha]

Typo. Another way to find uniques in an array is to add them to an object as a property the get all the keys using Object.keys(). Since an object cannot have duplicate keys, you always get unique values.

[u/all_things_code]

Shallow copy.

arr2 = [5,4,[6,5],4,3,[6,5]];
[... new Set(arr2)]
//the inner arrays make it out

[u/[deleted] → u/all_things_code]

Those inner arrays are not the same though. Two arrays or two objects, even if they have the same contents, are distinct values from one another. It would be extremely bad if this didn't happen.

[u/all_things_code → u/[deleted]]

Close. They are references (think memory addresses). They have different memory addresses. Therefore, not the same or equal. I believe the great JS ninja /u/senocular stated it thus:

"Comparing two objects (no matter if with == or ===) will always use identity comparison, not value comparison. They would only be equal if they were references to the same object."

[u/[deleted] → u/all_things_code]

Thanks, I appreciate it, but I know that, and my comment is not 'close', it's just slightly less precise given that your original comment seemed to indicate a fairly low level of understanding of value and reference.

[u/all_things_code → u/[deleted]]

Close. I was more right. :-D

[u/YojG → u/all_things_code]

What

[u/arkdelkaos → u/YojG]

https://imgur.com/a/inUqFIR
As you can see both [6,5] sub inner arrays are listed after the Set.

[u/eggtart_prince → u/all_things_code]

Deep object/array copying is too expensive. I don't think there is any native function or class that deep copies.

[u/all_things_code → u/eggtart_prince]

On my phone, but theres a neat way where you stringify the array, then later de-stringify it. Deep copy achieved, low overhead.

[u/JustJeezy]

Which site generates code snippets that look like this??