Back in early 2016, when I had just changed from an ACMer to a FEer, THERE were almost no JS apis to remember.

When looking at training the students can write Array. The prototype. Slice. Call (…) Such a long list of code do not know what to use, I can only secretly exclaim

At that time, I was so sweet and innocent that I couldn’t even remember the API, and of course I didn’t know its time complexity.

Until!! The timeline goes back to 2018.

That day, my elder brother happily pointed to a code in a book and said to me, “Look, its time complexity can be optimized from O(m * n) to O(m + N)!”

Then I took a look at what he called O(m + n) and, uh, uh, uh, isn’t that big violence??

Although the work does not have what use, but as an algorithm wang, decided to learn some really interesting algorithms with my brother.

After thinking about it, HDU does not support js to do the problem, so it is a little cruel to throw it to the elder brother (like you will use C++ to do the problem……).

So I opened LeetCode, started with the easy one, and chose the one with the highest pass rate… Well… Start simple…

You have a map of jewels, and you look at the map and see how many of these stones are jewels. What about literary and artistic views? If you are not literary and artistic, read the question by yourself…

With such a high pass rate, it is obvious that there is no pit in the title. I looked at a string of code written smoothly with the eyes of an old mother. It was a natural AC.

let numJewelsInStones = function(J, S) {
    return S.split("").filter(item => J.includes(item)).length;
};
Copy the code

After the senior also AC, we looked at each other’s code

(There’s nothing to see!)

Thought the way to achieve the same, did not think of my brother said, you this is not cheating with JS thinking yao.

Taking a look at his brother’s code, he realized a map by himself seriously, and then walked through it again to find it.

Seriously thought about my previous writing C++ thinking

Then, nothing came to mind.

What is split’s time complexity? Includes is O (n). In a perturbed mood, I went to look at the list of runtime, 60ms, beat 96%, looks not slow ah…

Originally this simple topic may be so turn over the page, but this list it mianmianmianzhizhong led me, so peak turn around, onto another road……

This number one guy, this is what he wrote

How come the indexOf is 8ms faster than includes?

At this point, please edit the comparison between 16 years and 18 years. Two years later, I still can’t tell the exact time complexity of this API.

Okay, WELL, I don’t know if someone big knows.

I randomly in a certain degree on the search, EMmm, no?? Well, rubbish, Google would have found it.

Emmm? Why not?

…

…

…

Thinking back to the days when seniors were telling us about the time complexity of classic apis in the lab, I decided to look at the underlying implementation to figure it out!

When I made this decision, I even felt that I could not find the sharing theme!

All right, all right.

So go see the implementation! Perhaps in a spirit of naivety, I decided to see V8 in action.

The V8 source code is available on Github and is available on github

(function(global, utils, extrasUtils) {
    "use strict"; %CheckIsBootstrapping(); // ------------------------------------------------------------------- // Imports var GlobalArray = global.Array; ... ... var ArrayIndexOf = GlobalArray.prototype.indexOf; var ArrayJoin = GlobalArray.prototype.join; var ArrayPop = GlobalArray.prototype.pop; ... utils.SetUpLockedPrototype(InternalArray, GlobalArray(), ["indexOf", ArrayIndexOf,
      "join", ArrayJoin,... ] );Copy the code

After the joy, the question is: where did global come from?

After two minutes of thinking about a messy C++ project, I decided to clone the code! (Inner OS: Just do a global search.)

After half a day, finally download a good project I search ~

Search again ~

So, after a few searches and a few reviews, I chose to open the ecMA-262 documentation.

Looking at some familiar documents…

Why is it familiar? Because the big guy organized a wave of activities to translate ECMA-262 documents before, I signed up happily and finished the seventh chapter of ECMA-262 with tears streaming down my face. Please give me a thumbs up, Boots

The article was posted on zhongcheng translation, speaking of which, it has to be said that Zhongcheng translation is really good, especially suitable for some inexperienced people who also want to exercise their English translation ability. I, Meow Meow, my real name is Amway…

Okay, back to the point, there’s a quote in the document that says this

The includes method intentionally differs from the similar indexOf method in two ways. First, it uses the SameValueZero algorithm, instead of Strict Equality Comparison, allowing it to detect NaN array elements. Second, it does not skip missing array elements, instead treating them as undefined.

After a close look at the SameValueZero method and Strict Equality Comparison, it doesn’t seem to make any difference.

At this point, I went back to LeetCode, copied the first code, pasted it, and submitted it.

Okay, bye. The fall!