Как повысить эффективность этой функции во время выполнения?

Question

Я пытаюсь написать оптимальный код (хорошая эффективность времени выполнения) для удаления повторяющихся слов в предложении.

Например, входная строка Jack Juliet Juliet Jill Jack Romeo Jack Jill функции должна возвращать Jack Juliet Jill Romeo

Вот мой код:

std::string removeDuplicateWords(const std::string& str)
{
    std::stringstream ss (str);
    std::unordered_set<std::string> string_history;
    std::string current_string, output_string;
    ss >> current_string;
    string_history.insert(current_string);
    output_string += current_string;
    while(ss >> current_string) {
        if(string_history.find(current_string) == string_history.end()) {
            output_string += " " + current_string;
            string_history.insert(current_string);
        }
    }
    return output_string;
}

Answer 1

В этом примере повышение производительности не имеет большого смысла, если для обработки требуется всего около 10 слов, используйте более простой код. Однако есть несколько способов улучшить производительность.

Прежде всего, вы не хотите проверять наличие элемента в наборе. insert возвращает вам пару iterator-bool, где первый - это итератор для элемента с ключом (существующим или новым), а второй - логическое значение, указывающее, произошла ли вставка.

      if (string_history.insert(current_string).second)
          output_string += " " + current_string;

Это упрощает код и повышает производительность. Как уже указывалось в комментариях, использование std::move имеет смысл, однако, если вы используете его со вставкой, вам понадобится итератор для удержания перемещенного объекта. В этом случае это не поможет, как в случаях с единым входом.

Второе, что требует больше кода, это удалить std::stringstream. Потоки дают некоторые накладные расходы. Вместо этого вы можете лучше принять std::string_view и использовать подстроку logi c, чтобы разрезать его на части. Это предотвращает создание новых строковых объектов и устраняет накладные расходы из потоков. Вам нужен C ++ 17 (или библиотека, обеспечивающая это).

Наконец, вы можете зарезервировать output_string в начале, вы знаете максимальный размер (он же размер str). Это может предотвратить перераспределение, если вы окажетесь вне диапазона SSO.

Answer 2

Улучшения:

• Вам не нужно проверять, существует ли строка, потому что unordered_set делает это за вас.

• current_string перемещено потому что он нам больше не нужен.

  std::string removeDuplicateWordsImproved( const std::string& str )
  {
      std::stringstream ss (str);
      std::unordered_set<std::string> string_history;
      std::string current_string, output_string;
  
      while( ss >> current_string )
          string_history.insert( std::move( current_string ) );
  
      for ( auto& word : string_history )
          output_string.append( std::move( word ) ).push_back( ' ' );
  
      output_string.erase( output_string.size() - 1 );
  
      return output_string;
  }