사전 처리 된 큰 텍스트 파일에서 행을 검색하십시오.

Question

데이터 파일이 100,000 개 이상 포함되어 있으며, 각 행에는 키와 값을 쉼표로 분리 한 두 개의 필드 만 있습니다. 모든 키는 고유입니다. 이 파일에서 키 값을 쿼리하고 싶습니다. 맵에로드하는 것은 너무 많은 메모리를 소비하므로 (임베디드 장치에서 코드가 실행 됨) DB가 관련되는 것을 원하지 않기 때문에 문제가되지 않습니다.

public long findKeyOffset(RandomAccessFile raf, String key) 
      throws IOException { 
     int blockSize = 8192; 
     long fileSize = raf.length(); 
     long min = 0; 
     long max = (long) fileSize/blockSize; 
     long mid; 
     String line; 
     while (max - min > 1) { 
      mid = min + (long) ((max - min)/2); 
      raf.seek(mid * blockSize); 
      if (mid > 0) 
       line = raf.readLine(); // probably a partial line 
      line = raf.readLine(); 
      String[] parts = line.split(","); 
      if (key.compareTo(parts[0]) > 0) { 
       min = mid; 
      } else { 
       max = mid; 
      } 
     } 
     // find the right line 
     min = min * blockSize; 
     raf.seek(min); 
     if (min > 0) 
      line = raf.readLine(); 
     while (true) { 
      min = raf.getFilePointer(); 
      line = raf.readLine(); 
      if (line == null) 
       break; 
      String[] parts = line.split(","); 
      if (line.compareTo(parts[0]) >= 0) 
       break; 
     } 
     raf.seek(min); 
     return min; 
    } 

내가 이것보다 더 나은 해결책이 있다고 생각 : 내가 지금까지 할 것은 즉, 다음 전처리 된 파일에 아래와 같은 이진 검색을 사용하여 라인을 정렬 전처리 내 PC에있는 파일입니다. 누군가가 내게 깨달음을 줄 수 있습니까?

Answer 1

데이터는 변경 불가능하며 키는 고유합니다 (질문에 언급 된대로).

간단한 해결책 : 줄 번호가있는 키를 매핑하는 해싱 코드를 작성하십시오.

이것은 정렬을 그대로두고 해싱 알고리즘이 말하는 순서대로 파일에 데이터를 쓰는 것을 의미합니다.

키를 쿼리하면 키를 해시하고 특정 줄 번호를 얻은 다음 값을 읽습니다.

이론적으로 문제에 대한 O (1) 해결책이 있습니다.

---

해싱 알고리즘의 충돌이 적은지 확인하십시오.하지만 정확한 사례에 따라 충돌이 발생하지 않도록해야합니다. 예 : 3 개의 키는 동일한 행 번호에 매핑되므로 3 개의 키를 모두 같은 줄에 쓰고 충돌 키가 검색되면 해당 행에서 3 개의 항목을 모두 읽습니다. 그런 다음 전체 라인에서 선형 (일명 O (3) 일명 일정 시간) 검색을 수행하십시오.

Answer 2

쉬운 알고리즘은 특정 제약 조건에 대한 성능을 최적화하기 :

1. 하자 N 될 원래, 불변, 정렬 된 파일의 행 수.
2. k < n을 숫자로 지정하십시오 (이상적인 숫자는 나중에 논의 할 것입니다).
3. 파일을 k 개의 파일로 나눕니다. 각 파일의 줄 수는 거의 같습니다 (각 파일에는 n/k 줄이 있습니다). 파일은 F1 ... Fk라고합니다. 원본 파일을 그대로 유지하려는 경우 F1 ... Fk를 파일의 줄 번호로 간주하여 세그먼트로 잘라냅니다.
4. k 행으로 P라는 새 파일을 만듭니다. 각 줄은 Fi의 첫 번째 키입니다.
5. 키를 찾을 때 먼저 O (logk)을 사용하여 P를 통한 이진 검색으로 이동해야하는 파일/세그먼트 (F1 ... Fk)를 찾으십시오. 그런 다음 해당 파일/세그먼트로 이동하여 검색하십시오.
6. k가 충분히 크면 Fi (n/k)의 크기가 HashMap에로드되고 O (1)으로 키를 검색 할 수있을만큼 충분히 작습니다. 여전히 실용적이지 않은 경우 O (log (n/k))의 이진 검색을 수행하십시오.

전체 검색은 것 O (logk) + O 원래 해결책 O (logn)에 개선이 (로그 (N/K)).

특정 Fi 파일/세그먼트를 HashMap에로드 할 수있을만큼 커야하고 기기의 공간을 채우기에 너무 크지 않은 k를 찾으십시오. 가장 균형 잡힌 k it sqrt (n)은 솔루션을 O (log (sqrt (n)))에서 실행하지만 꽤 큰 P 파일 일 수 있습니다. O (1) 검색을 위해 HashMap에 P와 Fi를로드 할 수있는 k를 얻는다면 이것이 최상의 솔루션이 될 것입니다.

Answer 3

어떨까요?

#include <iostream> 
#include <fstream> 
#include <boost/algorithm/string.hpp> 
#include <vector> 

using namespace std; 

int main(int argc, char *argv[]) 
{ 
    ifstream f(argv[1],ios::ate); 
    if (!f.is_open()) 
     return 0; 
    string key(argv[2]),value; 

    int max = f.tellg(); 
    int min = 0,mid = 0; 
    string s; 
    while(max-min>1) 
    { 
     mid = min + (max - min)/2; 
     f.seekg(mid); 
     f >> s; 
     std::vector<std::string> strs; 

     if (!f) 
     { 
      break; 
     } 
     if (mid) 
     { 
      f >> s; 
     } 
     boost::split(strs, s, boost::is_any_of(",")); 
     int comp = key.compare(strs[0]); 
     if (comp < 0) 
     { 
      max = mid; 
     } 
     else if (comp > 0) 
     { 
      min = mid; 
     } 
     else 
     { 
      value = strs[1]; 
      break; 
     } 
    } 
    cout<<"key "<<key; 
    if (!value.empty()) 
    { 
     cout<<" found! value = "<<value<<endl; 
    } 
    else 
    { 
     cout<<" not found..."<<endl; 
    } 

    f.close(); 
    return 0; 
}