.includes() 알고리즘 및 속도?

Question

.includes() 메소드가 사용하는 알고리즘을 알고 싶습니다. 그것은 rabin karp와 같은 모듈화 된 해시를 사용합니까?

.includes()를 사용하는 방법과 속도에 대해 알지 못해서 다소 주저합니다. 내가 찾은 문서는 논의 할 때 구체적인 내용이 아닙니다 (예 : https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/String/includes)

Answer 1

다른 엔진이 .includes를 다른 방식으로 구현할 수 있다고 가정하면 구현과 관련하여 포괄적 인 설명을하기가 어려울 수 있습니다. 그러나 일부 벤치마킹을 통해 속도에 대한 아이디어를 얻을 수 있어야합니다 (테스트가 유일한 확실한 방법이기 때문에).
3. 가지고 순차적 배열()에 전달 루프
2. 기본 순차 배열을 전달
1. 포함(), 전달 : I 세 가지 기능을 테스트 시도 노드 7.0을 사용

순차적 배열의 미리 만들어진 세트

내가 얻은 결과는 어레이 자체의 길이가 중요하지 않은 것으로 보였지만 (원하는대로) 원하는 숫자가 처음부터 얼마나 길 었는지를 제안했습니다. 인덱스 < 20에서 숫자를 찾으려면 for 루프가 약간 더 빨라질 것입니다 (아마도 ~ 15 %?). 더 큰 인덱스가 들어있는 경우에 for()는 for 루프를 사용합니다 (인덱스 500으로 보이는 것보다 ~ 2-3 배 빠름). 그러나 .has()는 이후 색인에서 숫자를 찾기 위해 훨씬 빠르며 (색인 800으로 ~ 25-30x 더 빠름) 색인의 크기는 속도에 거의 영향을 미치지 않습니다 (그러나 세트를 만들려면 시간이 필요함). 분명히 이것들은 다소 제한적인 테스트이며 많은 요인들이 그것들에 영향을 미칠 수 있습니다. 하나의 흥미로운 결과는 집합이 전달 된 배열 (다른 배열이 아닌)에서 만들어지면 집합이 함수로 전달되지 않더라도 포함 속도가 빨라지는 것처럼 보였습니다. for 루프 기능. 어떤 식 으로든 .includes()를 사용하는 캐싱의 일부 유형은 좋을까요?

Answer 2

Rabin-Karp 알고리즘은 문자열 검색 알고리즘이지만 문자열 검색과 달리 배열 includes() 알고리즘을 연결했습니다 , 서열 - 의존적이지 않다. ECMA specification은 이 구현을 지시하는 방식으로 동작을 설명합니다. 각 요소에 SameValueZero를 오름차순으로 적용합니다. 그 설명을 감안할 때, 어떤 일반적인 알고리즘도 O (n) 시간과 O (1) 메모리가 될 것입니다. 반면에, String.indexOf은 그러한 까다로운 규격을 가지지 않으며, V8 uses a Boyer-Moore-Horspool string search 구현을 갖는다.