javascript - .includes() algorithm and speed? - Stack Overflow

admin管理员组

文章数量:1340513

I'm interested to know what algorithm the .includes() method uses? Does it use a modularized hash like rabin karp?

I'm somewhat hesitant to use .includes() without knowing more about its methodology and speed. The documentation I've found doesn't go into specifics when discussing it (e.g. )

I'm interested to know what algorithm the .includes() method uses? Does it use a modularized hash like rabin karp?

I'm somewhat hesitant to use .includes() without knowing more about its methodology and speed. The documentation I've found doesn't go into specifics when discussing it (e.g. https://developer.mozilla/en/docs/Web/JavaScript/Reference/Global_Objects/String/includes)

• javascript
• hash
• string-search

Share Improve this question Follow edited Nov 12, 2016 at 18:10 Babra Cunningham asked Nov 12, 2016 at 17:41 Babra CunninghamBabra Cunningham 2,96722 gold badges2626 silver badges5353 bronze badges 4

• I always thought it used indexOf underneath it, but I'm not sure... – Luan Nico Commented Nov 12, 2016 at 17:55
• 2 It's most likely just syntactic sugar, and uses the same methods as indexOf under the hood, but how it's actually implemented is up to the vendors. – adeneo Commented Nov 12, 2016 at 17:57
• 2 The implementation is undefined. You're asking for an analysis of the source of every JavaScript engine. Some will perform better and some will perform worse than you expect. – LetterEh Commented Nov 12, 2016 at 17:59
• check out the polyfill in the link you mention above -- it shows a sample implementation (somewhat naive): developer.mozilla/en/docs/Web/JavaScript/Reference/… – Clark Commented Nov 12, 2016 at 18:03

Add a ment  | 

2 Answers 2

Sorted by: Reset to default 7

Given that different engines could implement .includes in different ways, it may be difficult to make blanket statements regarding implementation. However it should be possible to get an idea of it's speed by doing some benchmarking (as testing is likely the only way to be sure).

Using node 7.0 I tried testing three different functions:
1. includes(), passing in a sequential array
2. a basic for loop, passing in a sequential array
3. has(), passing in a precreated set from a sequential array

The results I obtained suggested the length of the array itself didn't seem to matter(as hoped), but how far the desired number was from the start did. For finding numbers at indexes <20 or so, the for loop seems slightly faster (by perhaps ~15%?). For larger indexes includes() over takes the for loop (being ~2-3x times faster by index 500 seemingly). However .has() is vastly faster for finding numbers at later indexes (~25-30x faster by index 800) and the size of the indexes seems to have little impact on its speed (but creating the set takes time).

Admittedly these are somewhat limited tests and many factors could impact them. One interesting result was that if a set was created from the passed in array (and not some other array), even if the set wasn't passed into the functions, it seemed to increase the speed of includes, and decrease the speed of the for loop function slightly. Some type of caching which somehow benefits .includes() I'd assume?

The Rabin-Karp algorithm is a string searching algorithm, but you've linked the Array includes() algorithm, which, unlike a string search, is not sequence-dependent. The ECMA specification describes its behavior in a way that dictates implementation: it applies SameValueZero to each element in ascending order. Given that description, any normal algorithm will be O(n) time and O(1) memory.

String.indexOf, on the other hand, doesn't have such a picky specification, and V8 uses a Boyer-Moore-Horspool string search implementation.

本文标签： javascriptincludes() algorithm and speedStack Overflow