JavaScript 배열에서 요소를 찾는 효과적인 방법

StackOverflow https://stackoverflow.com/questions/642046

문제

타이틀이있는 배열을 사용하고 있습니다. 각 타이틀 색인은 주어진 제목에 대해 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에 액세스 할 수 있습니다.

return titles_id[title]+1;

CPU, 메모리 등을 고려할 때 가장 효과적인 것은 무엇입니까?

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

감사합니다 Wille

도움이 되었습니까?

해결책

선형 검색 접근법에는 a가 있습니다 복잡성 O (n)의, 그리고 나는 연관 배열 접근법의 최악의 사례는 아마도 O (log n), ( 베스트 JS 엔진이 해시를 사용하고 충돌이 없으면 사례 O (1). JS 엔진이 일반적으로 구현되는 방식에 따라 다릅니다. 연관 배열/객체, 그러나 당신은 그것이 O (n)을 이길 것이라고 확신 할 수 있습니다.

따라서 두 번째 접근 방식은 더 빠르지 만 물론 더 많은 메모리를 사용할 것입니다. 이것은 매우 전형적인 것입니다 거래, 더 빠른 속도를 얻지 만 더 많은 메모리를 사용하면 그 거래를할지 여부를 결정할 수 있습니다.

다른 팁

저장해야 할 키 값 쌍의 수를 고려하는 것도 중요합니다. ~ 50 미만 (구현에 따라)이라면 해시 값을 계산하고 충돌 해결 비용으로 인해 해시 테이블 조회를 수행하는 것만 큼 선형 검색을 수행하는 것이 효율적입니다. Google Chrome V8 JavaScript 엔진은 객체에서 속성을 직접 조회 할 수있는 모든 객체의 일종의 캐시 버전을 유지하므로 해시 테이블로 객체 클래스를 사용하는 것이 더 빠를 수 있습니다. '이 캐시 된 버전 생성 비용이 작은 목록의 이점보다 더 크게할지 확실하지 않습니다.

첫 번째 메소드에서 배열의 기능을 사용할 수 있습니다.

아래는 Mozilla Developer의 정보입니다.https://developer.mozilla.org/en/core_javaScript_1.5_Reference:Objects:Array:indexof

indexof는 ECMA-262 표준에 대한 JavaScript 확장입니다. 따라서 표준의 다른 구현에는 존재하지 않을 수 있습니다. 스크립트의 시작 부분에 다음 코드를 삽입하여 기본적으로 지원하지 않는 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;
   };
}

JavaScript 배열은 인덱스에 "Why-Birds-Fly"라는 제목과 같은 값을 사용할 수 있습니다.

exmaple : var title = "왜 버드-파리";

var titlearray [] = new Array ();

titlearray [title] = id;

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

return titlearray [title];

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top