범위 검색에 사용할 데이터 구조는 무엇입니까?

도서를 카탈로그하는 간단한 프로그램을 만들려고합니다. 예를 들어 이런 식으로 뭔가가 :범위 검색에 사용할 데이터 구조는 무엇입니까?

struct book{ 
    string author; 
    string title; 
    int catalogNumber; 
}

궁극적으로, 나는 범위를 기반으로 제목 검색을 수행 할 수 있어야합니다. 따라서 사용자는 제목이 "aa"이지만 "be"로 시작하는 책의 결과를 표시하도록 지정할 수 있습니다. 이상적으로, 검색 평균의 경우는 대수입니다.

나를 도와 줄 수있는 STL이 있습니까? 그렇지 않으면이 문제를 해결하는 가장 좋은 방법은 무엇입니까?

감사합니다.

출처

2012-03-20 Jay Kim

std::set에 저장할 수 있으며 std::lower_bound 및 std::upper_bound을 사용하여 범위를 찾을 수 있습니다 (대수이어야합니다). 이를 수행하려면 관심있는 분야 (이 경우 title)에서 작동하려면 operator<을 정의해야합니다. 당신이 (거의) 항상 키와 제목을 치료하는 경우

, 당신은 다음과 같이 정의 info와 더불어, std::map<std::string, info>를 사용하는 것을 선호 있습니다

struct info { 
    string author; 
    int catalogNumber; 

    info(string a, int c) : author(a), catalogNumber(c) {} 
};

이 같은 몇 가지 작업을 좀 더 쉽게들을 수 있습니다 :

books["Moby Dick"] = info("Herman Melville", 1234);

당신은 제목이나 (예를 들어) 저자 검색을 지원 부스트 bimap 또는 multi_index 같은 것을 사용하는 것을 고려하십시오. 그것은 가치가 무엇인지에 대한

, 나는 또한 string를 사용하는 대신 카탈로그 번호에 대한 int에 심각한 생각을 것입니다. 표준 번호 체계 (예 : Dewey 십진수, 의회 도서관, ISBN) 중 거의 대부분이 int에 매우 잘 저장됩니다.

출처

2012-03-20 15:23:21

+1 카탈로그 번호가 포인트! –

정렬 된 벡터로 더 나은 성능을 얻으려면 (Scott Meyers, Effective STL을 통해) 주목할 가치가 있습니다. 일반적으로 조회를 삽입 삽입하지 않습니다. 즉, 벡터를 정기적으로 다시 정렬해야하기 때문에 잃어 버리지 않으면 벡터가 더 작아지고 더 현지화된다는 사실로부터 얻을 수 있습니다. – Chowlett

std::set에 요소를 넣을 수 있습니다. 문제는 아마 사용자가 저자뿐만 아니라 제목별로 검색 할 수 있기를 바랍니다. 해결책은 단지 두 세트를 유지하는 것입니다. 그러나 데이터가 변경되면 유지 보수가 까다로울 수 있으며 두 배의 공간이 필요합니다.

언제든지 Trie과 같은 것을 쓸 수 있지만 데이터가 변경되어 로그 검색 시간을 유지하기가 어려울 수 있습니다. 어떤 종류의 Self-balancing binary search tree도 구현할 수 있지만, 그게 바로 set 인 것입니다 - Red-black tree입니다. 하나를 쓰는 것은 쉬운 일이 아니다, 그러나 ...

업데이트 : 당신은 모든 것을 해시와 Rabin-Karp string search algorithm의 형태를 구현,하지만 당신은 당신이 그것을 할 경우 가능한 충돌이 있다는 것을 알고 있어야 할 수 있습니다. 이중 해싱 및/또는 양호한 해싱 함수를 사용하여 하나의 확률을 줄일 수 있습니다.

출처

2012-03-20 15:23:15

그것은 내가 생각하고 있던 것이 었습니다 ... 두 세트. 나는 더 나은 아직 무언가가있을 것이라는 점을 희망하고 있었다! 감사합니다! –

당신은 trie [여기 확장 @smarinov 제안] 사용할 수 있습니다

공통 접두어로 해당 단어의 집합을 찾기는 나타내는 노드에 도달 할 때까지 그냥 트라이에 포인터를 수행 트라이에 farily 쉽게 바람직한 공통 접두사. 이 노드는 원하는 공통 접 두부를 포함하는 트 리입니다.당신의 예에서

, 당신이 필요합니다 : |S| 공통 접두어의 길이이고이 영업 이익에 대한 기대

range("aa","be") = prefix("a") + (prefix("b[a-e]")

복잡성은 O(|S|)입니다. 비교 연산은 문자열의 길이에 따라 다르므로 알고리즘은 실제로 O(|S| * logn) 인 알고리즘이 더 좋지 않을 것으로 예상됩니다.

출처

2012-03-20 15:33:01 amit

범위 검색에 사용할 데이터 구조는 무엇입니까?

답변

관련 문제