C++ 복잡한 룩업 테이블

Question

나는 약 400.000 개의 "items"을 가지고있다. 각 "항목"은 16 개의 이중 값으로 구성됩니다.

런타임에는 항목을 서로 비교해야합니다. 그러므로 나는 그들의 이중 가치를 누그러 뜨리고있다. 이것은 꽤 많은 시간을 필요로합니다.

나는 몇 가지 테스트를 실시했으며, 어떤 항목을 비교해도 상관없이 가능한 반환 값은 40.000에 불과하다는 것을 알았습니다.

런타임시 실제 계산을 수행하지 않고도 이들 값을 쉽게 검색 할 수 있도록이 값을 조회 테이블에 저장하고 싶습니다.

내 질문은 어떻게 효율적으로 조회 테이블에 데이터를 저장하는 것입니다.

문제는 내가 룩업 테이블을 작성하는 경우, 그것은이 같은 예를 들어, 놀라 울 정도로 큰 얻을 수 있다는 것입니다 :

item-id, item-id, compare return value 

1 1 499483,49834 
1 2 -0.0928 
1 3 499483,49834 
(...) 

그것은 약 1 억 2 천만 조합 요약 것이다. 실제 응용 프로그램에 비해 너무 커 보인다.

하지만 어떻게 피할 수 있을지는 잘 모르겠습니다.

누구든지 멋진 아이디어를 공유 할 수 있습니까?

대단히 감사합니다!

Answer 1

정확하게 이해한다고 가정하면 400K 가능성이있는 두 개의 입력이 있으므로 400K * 400K = 160B 항목 ... 순차적으로 색인이 생성되었다고 가정하고 2 옥텟을 허용하는 방식으로 40K 가능성을 저장했다면 각각, 당신은 대략 300GB의 테이블 크기를보고 있습니다 ... 그것은 오늘날의 일상적인 컴퓨팅을 넘어서는 것입니다. 그래서, 당신은 400K 아이템들 사이에 어떤 상관 관계가 있는지를 조사 할 것입니다. 만약 그렇다면, 여러분이 그 상관 관계에 어떤 종류의 함수를 할당 할 수 있다면 40K 중 어떤 것에 대한 단서 (읽기 : 해시 함수)를 줄 수 있습니까? 결과가 나타날 수 있거나 결과가 발생할 수 있습니다. 명확하게 해쉬 함수와 룩업은 처음에 곱셈을하는 것보다 짧아야합니다. 또는 특정 시나리오에서 결과를 파악하는 것과 같은 지능형 축소와 비교 시간을 줄일 수도 있습니다. 또는 정수 수학 또는 부울 비교를 사용하여 수학의 일부를 최적화 할 수 있습니다. 몇 가지 생각 ...

Answer 2

속도를 높이려면 가능한 모든 답변을 계산하고 각 답변에 입력을 저장해야합니다.

그런 다음 답변을 모두 고유하므로 답변을 키로 사용하는 일종의 조회 표를 만든 다음 그 결과를 얻을 수있는 모든 입력을 저장하는 것이 좋습니다.

시각화를 돕기 위해 :

'테이블'테이블이 있다고 가정 해보십시오. 내부 테이블에는 키가 있고 그 키와 연관된 값이 있습니다. 당신이하는 일은 키에 어떤 형식의 형식이든지 대답을 입력하게하는 것입니다 (키는 모든 대답 일 것입니다). 이제 400k 입력에 고유 한 식별자를 각각 지정하십시오. 그런 다음 특정 키와 연관된 하나의 값으로 곱하기에 대한 고유 식별자를 저장합니다. 같은 대답을 다시 계산할 때, 그 키를 계산할 수있는 또 다른 입력 집합으로 추가하면됩니다.

예 :

Table<AnswerType, vector<Input>> 

정의 입력과 같은 하나 '입력'이있을 수 있습니다 어디

struct Input {IDType one, IDType two} 

ID의 12384, (128), 객체가 곱한 12,384 128에 의해 확인 된 것을 의미하는 것 답을주십시오.

그래서, 당신 조회에, 당신처럼 보이는 뭔가를해야합니다 :

AnswerType lookup(IDType first, IDType second) 
{ 
    foreach(AnswerType k in table) 
    { 
     if table[k].Contains(first, second) 
      return k; 
    } 
} 

// Defined elsewhere 
bool Contains(IDType first, IDType second) 
{ 
    foreach(Input i in [the vector]) 
    { 
     if((i.one == first && i.two == second) || 
      (i.two == first && i.one == second) 
      return true; 
    } 
} 

나는이 없습니다 실제 C++ 코드를 알고 그것의 단지 의사 코드로 의미, 그리고 같은 거친 컷입니다 -하지만 시작하는 장소 일 수 있습니다.

아마 foreach가 선형 검색으로 제한 될 수 있지만 '포함'메서드는 입력 저장 방법을 정렬하여 이진 검색을 실행할 수 있습니다.

모두 O (n^2) 시간에 실행되는 한 번만 실행되는 응용 프로그램과 nlog (n)에서 실행되는 조회가 있습니다. 나는 기억이 어떻게 그것들을 모두 뒤돌아 볼 것인가에 대해 완전히 확신하지 못한다. 물론, 그 뒤에있는 수학에 대해 많이 알지 못하기 때문에, 어떻게하면 키를 정렬 할 수 있다면 선형 검색을 빠르게 할 수있을 것입니다.