Узкое место при сравнении строк

Question

Это дополнительный вопрос к Char * vs String Speed ​​в C ++ . Я объявил следующие переменные:

std::vector<std::string> siteNames_;
std::vector<unsigned int> ids_;
std::vector<std::string> names_;

Я называю эту функцию десятки тысяч раз, и это является главным узким местом. Есть ли более эффективный способ сравнения строк? Ответ должен быть кросс-платформенным.

unsigned int converter::initilizeSiteId(unsigned int siteNumber){
    unsigned int siteId = 0;
    for (unsigned int i = 0; i < ids_.size(); i ++){
        if (siteNames_[siteNumber].compare(names_[i]) == 0){
            siteId = ids_[i];
            break; // Once found, will stop searching and break out of for loop
        }
    }
    if (siteId == 0)
        std::cerr << "Could not find ID for site number " << siteNumber << std::endl;

    return siteId;
}

Answer 1

Используйте взамен карту или неупорядоченную карту . Тогда вы можете сделать это:

std::map<string, int>names_;
// ...

unsigned int converter::initilizeSiteId(unsigned int siteNumber){
    unsigned int siteId = 0;
    std::map<string, int>::iterator i = names_.find(siteNames_[siteNumber]);
    if (i != names_.end()){
        siteId = i->second;
    }
    else (siteId == 0)
        std::cerr << "Could not find ID for site number " << siteNumber << std::endl;

    return siteId;
}

Это будет выполняться за время O (log n), а не за O (n), которое вы имели раньше.

Существуют и другие варианты, если у вас есть отсортированный список, например бинарный поиск .

Answer 2

Если вы часто просматриваете только несколько разных siteNumber и вызываете его достаточно много раз, возможно, стоит внедрить кеш для хранения последних siteNumber: s. Хотя, поскольку вы работаете только в памяти, а не с диска, я в этом сомневаюсь.