C++에서 문자열 개체 배열을 검색하는 가장 효율적인 방법은 무엇입니까?

Question

나는이 주제에 대한 좀 더 많은 정보를 찾고 있었고, 내가 찾던 답을 찾지 못하는 것 같아 도움을 얻을 수 있기를 바랍니다!

과제 중 일부는 문자열 배열 (주소록)을 검색하고 전체 또는 부분 일치 항목이 있으면 일치 항목을 반환하는 프로그램을 작성하는 것입니다. strstr() 함수를 for 루프를 통해 실행하고 배열에 사용자 입력 키워드를 실행 한 결과에 대한 포인터를 설정하여 (아래 참조) C- 문자열 배열을 사용하여 쉽게 수행 할 수 있습니다.

제 질문은 String 객체를 사용하면 어떻게 할 수 있습니까? 나는 또한 하나 이상의 가능한 일치가 있다는 것을 고려할 필요가있다. 이것이이 프로그램을 작업하는 가장 효율적인 방법입니까? 이미 작업 버전을 제출 했으므로 동일한 작업을 수행하는 다른 방법에 대해서 궁금합니다. 당신이 말할 수

#include <iostream> 
#include <cstring> 
using namespace std; 

int main() 
{ 

    bool isFound = false;   // Flag to indicate whether contact is found 
    const int SIZE = 11;   // Size of contacts array 
    const int MAX = 50;   // Maximum characters per row 
    char contacts[SIZE][MAX] = { 
           "Jig Sawyer, 555-1223", 
           "Michael Meyers, 555-0097", 
           "Jason Vorhees, 555-8787", 
           "Norman Bates, 555-1212", 
           "Count Dracula, 555-8878", 
           "Samara Moran, 555-0998", 
           "Hannibal Lector, 555-8712", 
           "Freddy Krueger, 555-7676", 
           "Leather Face, 555-9037", 
           "George H Bush, 555-4939", 
           "George W Bush, 555-2783" 
           }; 
    char *ptr = NULL;    // Pointer to search string within contacts 
    char input[MAX];    // User search input string 


    // Get the user input 
    cout << "Please enter a contact to lookup in the address book: "; 
    cin.getline(input,MAX); 

    // Lookup contact(s) 
    for (int i=0; i<SIZE; i++) 
    { 
    ptr = strstr(contacts[i], input); 
    if (ptr != NULL) 
     { 
     cout << contacts[i] << endl; 
     isFound = true; 
     } 
    } 

    // Display error message if no matches found 
    if (!contactFound) 
    cout << "No contacts found." << endl; 

    return 0; 
} 

, 나는 공포 영화 :

Answer 1

대신 문자열 검색에 정규 표현식을 사용하는 것이 좋습니다. 이제 a lot of info out there이 있습니다. 레코드의 하위 범위 (word2Search)를 일치시키려는 간단한 예제를 제공 할 것입니다 (이 예제를 복잡하게 만들지 않기 위해 하드 코드했습니다).

또한 배열을 정렬하는 전처리 단계 (주석에 이미 언급 된 기술)를 사용하고 있습니다.두 가지주의 다음 정렬은 빠른 검색 방법, 즉 이진 검색을 가능하게하기위한 것입니다

• 당신이 찾고있는 단어의 시작 부분에없는 경우

• (여기 lower_boundupper_bound로 구현) 레코드를 검색 할 때 유효 범위 (여기서는 itite)를 찾을 수 없으므로 레코드를 정렬 할 필요가 없습니다 (예 : 숫자를 검색 할 경우 사전 순으로 정렬됩니다. 문자열 간의 비교이므로로 시작하는 문자열 사이에 555을 배치하는 것이 좋지 않습니다. 코멘트에 79,443,210 J 등)

설명 :

이

int main() 
{ 
    // 1. Minor change - an array of strings is used 
    string contacts[] = { 
     "Jig Sawyer, 555-1223", 
     "Michael Meyers, 555-0097", 
     "Jason Vorhees, 555-8787", 
     "Norman Bates, 555-1212", 
     "Count Dracula, 555-8878", 
     "Samara Moran, 555-0998", 
     "Hannibal Lector, 555-8712", 
     "Freddy Krueger, 555-7676", 
     "Leather Face, 555-9037", 
     "George H Bush, 555-4939", 
     "George W Bush, 555-2783" 
    }; 
    // 2. The array is sorted to allow for binary search 
    sort(begin(contacts), end(contacts)); 
    // 3. Example hard coded a word to search 
    string word2Search = "George"; 
    // 4. A regular expression is formed out of the target word 
    regex expr(word2Search); 
    // 5. Upper and lower bounds are set for the search 
    char f = word2Search[0]; 
    std::string val1(1, f); 
    std::string val2(1, ++f); 
    // 6. Perform the search using regular expressions 
    for (auto it(lower_bound(begin(contacts), end(contacts), val1)), 
     ite(lower_bound(begin(contacts), end(contacts), val2)); it != ite; ++it) 
    { 
     if (regex_search(it->begin(), it->end(), expr)) { 
      cout << *it << endl; 
     } 
    } 

    return 0; 
} 

Answer 2

당신은 정말 정렬 구성 요소로 각 문자열을 깰 필요를 좋아한다. 구조에 대해 아직 모르는 경우 더 많은 배열을 사용할 수 있습니다. 이렇게하면 검색 속도를 높이는 "색인"테이블을 작성할 수 있습니다.

가장 효율적인 방법은 데이터의 양과 데이터의 구성에 따라 결정됩니다.

작은 데이터 세트의 경우 다른 검색 방법의 시간 차이는 대개 무시할 수 있습니다. 프로그램의 다른 일부 항목은 입력 또는 출력과 같이 더 오래 걸립니다.

문자열 데이터의 경우 대부분의 시간은 한 문자열의 각 문자를 다른 문자열과 비교하는 데 소비됩니다. 인덱스 이동과 같은 다른 작업은 무시할 수 있습니다.

검색 방법 간의 비교가 이미 수행되었으므로 웹에서 "성능 문자열 검색 비교"를 검색하십시오.