Альтернатива std :: find, которая работает быстрее - PullRequest
Новая
       42

Альтернатива std :: find, которая работает быстрее

0 голосов
/ 05 мая 2020

У меня есть код, который находит новые слова в контейнере и добавляет их к частной переменной класса dict. Функцию Learner::Learn необходимо оптимизировать, чтобы она работала быстрее. Элементы в векторе dict могут повторять друг друга, но 'newWords' всегда должен возвращать количество новых (не повторяющихся) слов. 

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Learner {
private:
  vector<string> dict;

public:
  int Learn(const vector<string>& words) {
    int newWords = 0;
    for (const auto& word : words) {
      if (find(dict.begin(), dict.end(), word) == dict.end()) {
        ++newWords;
        dict.push_back(word);
      }
    }
    return newWords;
  }

Я пробовал этот способ, но время выполнения то же самое: 

class Learner {
 private:
  vector<string> dict;

 public:
  int Learn(const vector<string>& words) {
    std::size_t index = dict.size();
    dict.resize(dict.size() + words.size());
    vector<string>::iterator nth = dict.begin() + index;
    int newWords = 0;
    for (const auto& word : words) {
      if (find(dict.begin(), dict.end(), word) == dict.end()) {
        ++newWords;
        *nth++ = word;
      }
    }
    return newWords;
  }

Я должен как-то избегать использования метода push_back().

Ответы [ 2 ]

2 голосов
/ 05 мая 2020

Если вы всегда сохраняете words отсортированным, вы можете использовать двоичный поиск для общего времени выполнения O (n log n), но вам нужно сдвинуть весь вектор, чтобы вставить что-то посередине. (что вернет его к O (n ^ 2))

Вы должны переключиться на другой контейнер для значительного улучшения:

  • std::set (O (log n) поиск, O (журнал n) вставка)
  • std::map (поиск O (журнал n), O (журнал n) вставка)
  • std::unordered_set (поиск O (1), O (1) вставка)
1 голос
/ 05 мая 2020

Tr ie - эффективная альтернатива, но не в стандартном формате, поэтому вам придется написать его самостоятельно или использовать внешнюю библиотеку.

В стандартном формате std::set / std::map и неупорядоченные версии (std::unordered_set / std::unordered_map) могут помочь

...