자바 스크립트 배열에서 요소를 찾는 효과적인 방법

Question

제목이있는 배열을 사용하고 있습니다. 각 titles 인덱스는 해당 제목에 대한 html을 포함하는 데이터베이스의 id에 해당합니다.

제목 중 하나가 포함 된 문자열이 있다고 가정 해 보겠습니다.

title = "why-birds-fly"; 
titles[] // an array which contains all the titles 

내가 할 수있는 해당 ID를 얻을 수있는 문자열 "제목"을 사용하려면 : 내가 사용할 수있는 또 다른 방법은 정확 제목 배열과 함께 연관 배열을 만드는 것입니다

for (i = 0; i < titles.length-1; i++) { 
    if (titles[i] == title) 
    return i+1; 
} 

제목의 반대편. 즉, 문자열을 인덱스로 사용하여 숫자를 반환합니다.

titles_id {blah:0,why-birds-fly:1,blah2:2} 

그때로 ID에 액세스 할 수 있습니다 : 등, CPU, 메모리를 고려하여 가장 효과적인 것이 무엇

return titles_id[title]+1; 

를?

또한 내 논리가 잘못되었는지 알려주세요.

감사 빌렘

Answer 1

는 선형 검색 방법은 O (N)의 complexity을 가지고, 내가 연관 배열 방법에 대한 최악의 경우 아마 O (로그 n)합니다 (최고의 경우라고 생각 어쩌면 JS 엔진이 해시를 사용하고 충돌이없는 경우 O (1)). JS 엔진이 일반적으로 associative arrays/objects을 구현하는 방법에 따라 다르지만 O (n)을 이길 수 있는지 확인할 수 있습니다.

따라서 두 번째 방법은 빠르지 만 더 많은 메모리를 사용합니다. 이것은 전형적으로 trade off이며, 더 많은 속도를 얻지 만 더 많은 메모리를 사용하며, 그 거래를 할 것인지 결정할 수 있습니다.

Answer 2

자바 스크립트 배열은 제목에 "why-birds-fly"와 같은 값을 사용할 수 있습니다.

예시 : var title = "why-birds-fly";

var TitleArray [] = new Array();

TitleArray [title] = id;

는 그런 다음 제목으로 ID에 직접 액세스 할 수 있습니다

반환 TitleArray [제목]

Answer 3

저장할 필요가있는 키 값 쌍의 수를 고려하는 것도 중요합니다. ~ 50 미만 (구현에 따라 다름)의 경우 선형 검색을 수행하면 해시 값을 계산하고 충돌을 해결하는 비용 때문에 해시 테이블 조회를 수행하는 것만 큼 효율적입니다. 예외는 Google 크롬 v8 자바 스크립트 엔진이 개체의 속성을 직접 조회 할 수 있도록 캐시 된 버전의 모든 개체를 유지하므로 개체 클래스를 해시 테이블로 사용하는 것이 더 빠를 수 있지만 캐시 된 버전을 만드는 데 드는 비용이 작은 목록의 이점보다 중요한지 확실하지 않습니다.

Answer 4

첫 번째 방법으로 Array의 indexOf 함수를 사용할 수 있습니다.다음은

모질라 개발자의 정보입니다 : https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference:Objects:Array:indexOf

같이 IndexOf는 ECMA-262 표준에 자바 스크립트 확장; 표준의 다른 구현에는 존재하지 않을 수도 있습니다. 스크립트 시작 부분에 다음 코드를 삽입하여이를 지원하면 기본적으로 지원하지 않는 ECMA-262 구현에서 indexOf를 사용할 수 있습니다. 이 알고리즘은 Firefox와 SpiderMonkey에서 사용 된 알고리즘입니다.

if (!Array.prototype.indexOf) 
{ 
    Array.prototype.indexOf = function(elt /*, from*/) 
    { 
    var len = this.length >>> 0; 

    var from = Number(arguments[1]) || 0; 
    from = (from < 0) 
     ? Math.ceil(from) 
     : Math.floor(from); 
    if (from < 0) 
     from += len; 

    for (; from < len; from++) 
    { 
     if (from in this && 
      this[from] === elt) 
     return from; 
    } 
    return -1; 
    }; 
}