Nice article. Could you please elaborate more on this sentence: "...Looking up a Set in JavaScript is constant time, O(1)...".
As far as I know if you implement Set using hash-table you could reduce most of the operations to the O(1) in an average-case but O(n) in the worst-case. Moreover in ECMAScript2015 specification for the Set.prototype.has it says:
.
4. Let entries be the List that is the value of Sās [[SetData]] internal slot.
5. Repeat for each e that is an element of entries,
If e is not empty and SameValueZero(e, value) is true, return true.
.
So I'm not sure that we could say that Set.prototype.has is an O(1) time complexity.
Thanks š. Yes, in the worst case the look-up time can be O(N). I was using Big O notation, where a Set look-up can be reduced down to O(1). I assumed that Chromium would be using an optimal data structure even though the spec only mandates sublinear access time.
Map object must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection.
(Last time I checked) indexOf uses linear search to check for an element. So it's like doing a for loop and checking every element until it's found. It doesn't benefit from the fast look-up time of a hashtable.
I learned the benefits and use cases of different data-structures by reading a book called Grokking Algorithms and watching Introduction to Algorithms on the MIT website (MIT Course Number 6.006). Textbooks can help as well as programming puzzle websites like hackerrank and leetcode where you can test the performance of your code and read peoples' discussions of solutions. Looking up (and learning) what 'Big O' is helps too!
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Nice article. Could you please elaborate more on this sentence: "...Looking up a Set in JavaScript is constant time, O(1)...".
As far as I know if you implement
Setusinghash-tableyou could reduce most of the operations to theO(1)in an average-case butO(n)in the worst-case. Moreover in ECMAScript2015 specification for theSet.prototype.hasit says:So I'm not sure that we could say that
Set.prototype.hasis an O(1) time complexity.Thanks š. Yes, in the worst case the look-up time can be
O(N). I was using Big O notation, where a Set look-up can be reduced down toO(1). I assumed that Chromium would be using an optimal data structure even though the spec only mandatessublinear access time.I know I'm late to the party, but thanks for this reply, as you provide some links that make me understand why it "should be around O(1)" ^
If you reach this reply, how do you know/learn how to use the Set instead of doing a nested loop ?
Edit : what if in the first exemple; instead of the nested tab, we use jewels.indexOf(S[i]) !== -1 ? Exactly like using jewels.has(S[i]) ?
(Last time I checked)
indexOfuses linear search to check for an element. So it's like doing a for loop and checking every element until it's found. It doesn't benefit from the fast look-up time of a hashtable.I learned the benefits and use cases of different data-structures by reading a book called Grokking Algorithms and watching Introduction to Algorithms on the MIT website (MIT Course Number 6.006). Textbooks can help as well as programming puzzle websites like hackerrank and leetcode where you can test the performance of your code and read peoples' discussions of solutions. Looking up (and learning) what 'Big O' is helps too!