최소 조회 시간 복잡성이있는 좋은 방법 제안

Question

3 개의 식별자 필드와 하나의 값 필드가있는 구조가 있습니다. 나는이 물건들의 목록을 가지고있다. 비유하자면 식별자 필드는 객체에 대한 기본 키와 같습니다. 이 3 개의 필드는 객체를 고유하게 식별합니다.

Class 
{ 
    int a1; 
    int a2; 
    int a3; 
    int value; 
}; 

나는이 데이터 형식의 1000 개체 목록을 가지고 있습니다. a1, a2 및 a3의 특정 값을 가진 개체가 있는지 확인하고 해당 값을 반환하는지 확인하는 조회 함수에 a1, a2 및 a3 값을 전달하여 이러한 ID 키 값의 특정 값을 확인해야합니다. 최상의 검색 시간을 얻기 위해 이것을 구현하는 가장 효과적인 방법은 무엇입니까?

내가 생각할 수있는 한 가지 해결책은 길이가 1000 인 3 차원 행렬을 사용하여 그 값을 채우는 것입니다. 조회 시간은 O (1)입니다. 그러나 단점이 있습니다. 1. 배열의 길이를 알아야합니다. 2. 높은 신원 필드 (예 : 20)의 경우, 메모리에 과도한 잔량이 될 20 개의 차원 행렬이 필요합니다. 실제로 구현하려면 23 개의 ID 필드가 있어야합니다.

이 데이터를 저장하는 좋은 방법을 제안하면 시간이 가장 많이 걸릴 것입니까?

Answer 1

모든 ID 필드를 포함하는 키 클래스를 만들고 적절한 equals 함수 및 해시 메서드를 정의한 다음 해시 맵을 사용하여 키 클래스에서 관련 값으로 매핑합니다. 이것은 예상되는 사건에서 조회 당 O (1)의 시간 복잡성을 제공 할 것이며 관찰 된 실제 키 조합의 수에 비례 한 공간 만 필요합니다 (일반적으로 두 번 숫자입니다. 시간/공간에 대한 상수를 조정할 수 있음). 모든 가능한 키 조합에 비례하는 공간이 아니라 오히려 원하는 것입니다.

Answer 2

해시 테이블 (지도)을 사용하십시오. "a1-a2-a3"이 될 키를 만들고 H (key) = data에 데이터를 저장하십시오.

Answer 3

간단히 키별로 배열을 정렬하고 이진 검색을 사용합니다.

int compare_entry(ENTRY *k1, ENTRY *k2) {  
    int d = k1->a1 - k2->a1; 
    if (d == 0) { 
     d = k1->a2 - k2->a2; 
     if (d == 0) { 
      d = k1->a3 - k2->a3; 
     } 
    } 
    return d; // >0 is k1 > k2, 0 if k1 == k2, <0 if k1 < k2 
} 

// Derived from Wikipedia 
int find(ENTRY *list, int size, ENTRY *value) { 
    int low = 0; 
    int n = size - 1; 
    int high = n; 
    while (low < high) { 
     int mid = low + (high - low)/2 
     int cmp = compare_entry(&list[mid], value); 
     if (cmp < 0) { 
      low = mid + 1; 
     } else { 
      high = mid; 
     } 
    } 
    if (low < n) { 
     int cmp = compare_entry(&list[low], value); 
     if (cmp == 0) { 
      return low; // found item at 'low' index 
     } 
    } else { 
     return -1; // not found 
    } 
} 

물론 최악의 경우

(안된), 당신은이 일을 통해 실행 무엇을, 10 배, 실제로 키 비교하여 비교의 모든 일을 끝낸다. 그렇다면 85 개의 정수 연산 (덧셈, 뺄셈, 1 쉬프트)이 있습니까?

a1-a3의 범위가 0-100이면 키를 a1 * 10000 + a2 * 100 + a3으로 만들 수 있으며 단일 비교를 수행하고 최악은 63 정수 연산입니다. 또한 전체 배열은 대부분의 최신 프로세서에서 캐시에 맞습니다. 그리고 그것은 메모리 효율적입니다.

완벽한 해시 또는 다른 희소 한 매트릭스로 메모리를 구울 수 있습니다. 완벽한 해시를 사용하더라도 해시 계산 자체가 비싸다는 점을 감안할 때이 시간과 경쟁 할 수 있습니다. 이것은 분명히 메모리 버스를 더 세게 때린다.