Главная » C++ » Неожиданно плохое время выполнения функции конкатенации строк

Неожиданно плохое время выполнения функции конкатенации строк

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

size_t str_size(const char *str) {
return std::strlen(str);
}

size_t str_size(const std::string &str) {
return str.size();
}

template <typename T>
size_t accumulated_size(const T& last) {
return str_size(last);
}

template <typename T, typename... Args>
size_t accumulated_size(const T& first, const Args& ...args) {
return str_size(first) + accumulated_size(args...);
}

template <typename T>
void append(std::string& final_string, const T &last) {
final_string += last;
}

template <typename T, typename... Args>
void append(std::string& final_string, const T& first, const Args& ...args) {
final_string += first;
append(final_string, args...);
}

template <typename T, typename... Args>
std::string join(const T& first, const Args& ...args) {
std::string final_string;

final_string.reserve(accumulated_size(first, args...));
append(final_string, first, args...);

return std::move(final_string);
}

Я проверил join метод против типичной встроенной функции конкатенации C ++ с использованием operator+= а также operator+ из std::string Класс на довольно большое количество строк. Как и почему мой метод дает худшие результаты с точки зрения времени выполнения по сравнению с обычным operator+= или же operator+ подход?

Я использую следующий класс для измерения времени:

class timer {
public:
timer() {
start_ = std::chrono::high_resolution_clock::now();
}

~timer() {
end_ = std::chrono::high_resolution_clock::now();
std::cout << "Execution time: " << std::chrono::duration_cast<std::chrono::nanoseconds>(end_ - start_).count() << " ns." << std::endl;
}

private:
std::chrono::time_point<std::chrono::high_resolution_clock> start_;
std::chrono::time_point<std::chrono::high_resolution_clock> end_;
};

Я сравниваю следующий способ:

#define TEST_DATA "Lorem", "ipsum", "dolor", "sit", "ame", "consectetuer", "adipiscing", "eli", "Aenean",\
"commodo", "ligula", "eget", "dolo", "Aenean", "mass", "Cum", "sociis", "natoque",\
"penatibus", "et", "magnis", "dis", "parturient", "monte", "nascetur", "ridiculus",\
"mu", "Donec", "quam", "feli", ", ultricies", "ne", "pellentesque", "e", "pretium",\
"qui", "se", "Nulla", "consequat", "massa", "quis", "eni", "Donec", "pede", "just",\
"fringilla", "ve", "aliquet", "ne", "vulputate", "ege", "arc", "In", "enim", "just",\
"rhoncus", "u", "imperdiet", "", "venenatis", "vita", "just", "Nullam", "ictum",\
"felis", "eu", "pede", "mollis", "pretiu", "Integer", "tincidunt"
#define TEST_DATA_2 std::string("Lorem") + "ipsum"+ "dolor"+ "sit"+ "ame"+ "consectetuer"+ "adipiscing"+ "eli"+ "Aenean"+\
"commodo"+ "ligula"+ "eget"+ "dolo"+ "Aenean"+ "mass"+ "Cum"+ "sociis"+ "natoque"+\
"penatibus"+ "et"+ "magnis"+ "dis"+ "parturient"+ "monte"+ "nascetur"+ "ridiculus"+\
"mu"+ "Donec"+ "quam"+ "feli"+ ", ultricies"+ "ne"+ "pellentesque"+ "e"+ "pretium"+\
"qui"+ "se"+ "Nulla"+ "consequat"+ "massa"+ "quis"+ "eni"+ "Donec"+ "pede"+ "just"+\
"fringilla"+ "ve"+ "aliquet"+ "ne"+ "vulputate"+ "ege"+ "arc"+ "In"+ "enim"+ "just"+\
"rhoncus"+ "u"+ "imperdiet"+ ""+ "venenatis"+ "vita"+ "just"+ "Nullam"+ "ictum"+\
"felis"+ "eu"+ "pede"+ "mollis"+ "pretiu"+ "Integer"+ "tincidunt"
int main() {
std::string string_builder_result;
std::string normal_approach_result_1;
std::string normal_approach_result_2;

{
timer t;
string_builder_result = join(TEST_DATA);
}

std::vector<std::string> vec { TEST_DATA };
{
timer t;
for (const auto & x : vec) {
normal_approach_result_1 += x;
}
}

{
timer t;
normal_approach_result_2 = TEST_DATA_2;
}
}

Мои результаты:

  • Время выполнения: 11552 нс (join подход).
  • Время выполнения: 3701 нс (operator+=() подход).
  • Время выполнения: 5898 нс (operator+() подход).

Я собираю с: g++ efficient_string_concatenation.cpp -std=c++11 -O3

2

Решение

operator+ имеет ссылку на значение слева std::string, += код, который вы написали, не намного лучше, чем длинная цепочка +,

это + можно использовать экспоненциальное перераспределение, начиная с 10 или около того. При коэффициенте роста 1,5, который составляет около 9 распределений и перераспределений.

Рекурсия может сбить с толку или замедлить ход событий. Вы можете это исправить:

template <typename... Args>
void append(std::string& final_string, const Args&... args) {
using unused=int[];
(void)unused{0,(void(
final_string += args
),0)...};
}

что устраняет эту рекурсию, и аналогично:

template <typename... Args>
size_t accumulated_size(const Args& ...args) {
size_t r = 0;
using unused=int[];
(void)unused{0,(void(
r += str_size(args)
),0)...};
return r;
}

но, возможно, не стоит посещать столько строк, чтобы рассчитать их длину, чтобы сохранить 8 перераспределений.

4

Другие решения

Пожалуйста, не разбирайтесь со строками для этого.

Используйте строковые потоки или создайте свой собственный StringBuilder, как этот: https://www.codeproject.com/Articles/647856/Performance-Improvement-with-the-StringBuilde

Специализированные сборщики строк рекомендуются благодаря интеллектуальному управлению выделениями (иногда они поддерживают список кусочков строк, иногда — предсказание роста). Распределение — это сложная и очень трудоемкая операция.

-1

Источник
Web-Answers © 2024 Наверх