Функция C++ возвращает результат очень медленно, намного медленнее, чем функционально эквивалентный код Python

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

{"apple", "bapple", "banana", "cherry", "bananaman", "sweetherrypie", "sweet", "b"}

Он должен вывести сжатый массив строк (в любом порядке):

{"apple", "cherry", "sweet", "b"}

Это сделано для того, чтобы уменьшить количество ключевых слов, которые алгоритм сопоставления должен пройти в рамках личного учебного проекта (если строка содержала «банан», она также будет содержать «b», поэтому «банан» не нужен и его можно отбросить).

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

Первоначально я написал для этого код Python:

def deduplicate_keywords(keywords):
    def inner_loop(unique_keywords, keyword):
        for unique_keyword in unique_keywords:
            # Check if the current keyword includes any of the unique keywords
            if unique_keyword in keyword:
                return  # Match so it is not added to unique keywords
        # If the keyword does not include any of the shorter keywords, add it to unique_keywords
        unique_keywords.append(keyword)
        return

    # Remove duplicates and sort the keywords by length in ascending order
    keywords = sorted(set(keywords), key=len)
    unique_keywords = []

    for keyword in keywords:
        inner_loop(unique_keywords, keyword)
    return unique_keywords

И тест производительности для измерения его производительности:

class TestDeduplicateKeywords(unittest.TestCase):
    def test_performance_intensive_case(self):
        keywords = [
            "abcdef",
            "def",
            "ghidef",
            "jkl",
            "mnop",
            "qrst",
            "uvwxyz",
            "ghijkl",
            "abcdefgh",
            "ijklmnop",
            "mnopqrstuv",
            "rstuvwx",
            "mnopqrstuvwx",
            "uvwx",
        ]

        # Extending the list to make it very long and complex
        base_keywords = keywords[:]
        for i in range(200000):
            base_keywords.extend([f"{k}{i}" for k in keywords])
            base_keywords.extend([f"{i}{k}" for k in keywords])
            base_keywords.extend([f"{i}{k}{i}" for k in keywords])

        keywords = base_keywords

        old_function_time = 0
        new_function_time = 0

        for repeat in range(100): 
            # This loop (not present in the C++ code) is used to loop it multiple times to find an average
            start_time = time.time()
            result = deduplicate_keywords(keywords)
            end_time = time.time()
            old_function_time = (
                repeat * old_function_time + (end_time - start_time)
            ) / (repeat + 1)
            start_time = time.time()
            result = deduplicate_keywords_new(keywords) 
            # Above is a function that can be edited to check whether changes speed up the code
            end_time = time.time()
            new_function_time = (
                repeat * new_function_time + (end_time - start_time)
            ) / (repeat + 1)

        # As the list is extended with numbers, the result will be unique non-redundant keywords
        expected_result = ["def", "jkl", "mnop", "qrst", "uvwx"]

        self.assertEqual(set(result), set(expected_result))
        print(
            f"Test performance_intensive_case for old function took {old_function_time} seconds\n"
            f"Test performance_intensive_case for new function took {new_function_time} seconds\n"
        )

        if old_function_time < new_function_time:
            print(f"Old is faster than new")
        else:
            print(f"New is faster than old")


if __name__ == "__main__":
    unittest.main()

Это было слишком медленно для моих нужд на 5.677098312377932 seconds на моем слабом ноутбуке (когда я запускал 100 раз, чтобы найти среднее время), как указано в журнале консоли:

.Test performance_intensive_case for old function took 5.677098312377932 seconds

Поэтому я попробовал написать то же самое на C++, чтобы посмотреть, получу ли я прирост производительности. Это было настолько медленнее, что я добавил в саму функцию некоторый временной код, чтобы увидеть, где происходит замедление. Вот функция:

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <chrono>
#include <cassert>

std::vector<std::string> deduplicate_keywords(const std::vector<std::string> &keywords)
{
    auto t_start = std::chrono::steady_clock::now();
    auto inner_loop = [](std::vector<std::string> &unique_keywords, const std::string &keyword)
    {
        for (const auto &unique_keyword : unique_keywords)
        {
            if (keyword.find(unique_keyword) != std::string::npos)
            {
                return; // Match so it is not added to unique keywords
            }
        }
        // Otherwise, add it to unique_keywords
        unique_keywords.push_back(keyword);
    };

    // Remove duplicates using a set
    auto t1 = std::chrono::steady_clock::now();
    std::cout << "started old function!" << std::endl;
    std::set<std::string> unique_set(keywords.begin(), keywords.end());
    auto t2 = std::chrono::steady_clock::now();
    std::cout << "removed duplicates in " << std::chrono::duration<double>(t2 - t1).count() << " seconds" << std::endl;

    // Convert set back to vector and sort by length
    auto t3 = std::chrono::steady_clock::now();
    std::vector<std::string> sorted_keywords(unique_set.begin(), unique_set.end());
    std::sort(sorted_keywords.begin(), sorted_keywords.end(), [](const std::string &a, const std::string &b)
              { return a.length() < b.length(); });
    auto t4 = std::chrono::steady_clock::now();
    std::cout << "Sorted by length in " << std::chrono::duration<double>(t4 - t3).count() << " seconds" << std::endl;

    // Filter out redundant keywords
    auto t5 = std::chrono::steady_clock::now();
    std::vector<std::string> unique_keywords;
    for (const auto &keyword : sorted_keywords)
    {
        inner_loop(unique_keywords, keyword);
    }
    auto t6 = std::chrono::steady_clock::now();
    std::cout << "Filtered in " << std::chrono::duration<double>(t6 - t5).count() << " seconds" << std::endl;

    auto t_end = std::chrono::steady_clock::now();
    auto total_time = std::chrono::duration<double>(t_end - t_start).count();
    std::cout << "Total function time: " << total_time << " seconds" << std::endl;

    return unique_keywords;
}

Наряду с тестом производительности:

using Time = std::chrono::steady_clock;
void test_performance_intensive_case()
{
    std::cout << "Keywords generation start." << std::endl;
    std::vector<std::string> keywords = {
        "abcdef", "def", "ghidef", "jkl", "mnop", "qrst", "uvwxyz",
        "ghijkl", "abcdefgh", "ijklmnop", "mnopqrstuv", "rstuvwx",
        "mnopqrstuvwx", "uvwx"};

    // Extending the list to make it very long and complex
    std::vector<std::string> base_keywords = keywords;
    for (int i = 0; i < 200000; ++i)
    {
        for (const auto &k : keywords)
        {
            base_keywords.push_back(k + std::to_string(i));
            base_keywords.push_back(std::to_string(i) + k);
            base_keywords.push_back(std::to_string(i) + k + std::to_string(i));
        }
    }

    auto keywords_extended = base_keywords;
    std::cout << "Keywords generated!" << std::endl;
    std::set<std::string> expected_result = {"def", "jkl", "mnop", "qrst", "uvwx"};

    // One time variable declaration for "for loop"
    // The total times are use to confirm that timing itself had no negative impact on the times
    double old_function_time = 0;
    double new_function_time = 0;
    double total_test_time = 0;
    double total_test_time_new = 0;
    double average_old_time = 0;
    double average_new_time = 0;
    Time::time_point start_time_total;
    Time::time_point start_time;
    Time::time_point end_time;
    Time::time_point end_time_total;
    Time::time_point start_time_total_new;
    Time::time_point start_time_new;
    Time::time_point end_time_new;
    Time::time_point end_time_total_new;
    std::cout << "vars declared and loop of code about to start" << std::endl;
    for (int repeat_no = 0; repeat_no < 5; ++repeat_no) // Loop to calculate average.
    {
        start_time_total = Time::now();
        start_time = Time::now();
        std::vector<std::string> result_old = deduplicate_keywords(keywords_extended);
        end_time = Time::now();
        old_function_time = std::chrono::duration<double>(end_time - start_time).count();
        end_time_total = Time::now();
        total_test_time = std::chrono::duration<double>(end_time_total - start_time_total).count();
        assert(std::set<std::string>(result_old.begin(), result_old.end()) == expected_result);
        average_old_time = (repeat_no * average_old_time + old_function_time) / (repeat_no + 1);
        std::cout << "Current average old time: " << average_old_time << " seconds" << std::endl;
        std::cout << "Old function time: " << old_function_time << " seconds" << std::endl;
        std::cout << "Total test case time: " << total_test_time << " seconds" << std::endl;

        start_time_total_new = Time::now();
        start_time_new = Time::now();
        std::vector<std::string> result_new = deduplicate_keywords_new(keywords_extended); // same as in the python code, useful for comparison
        end_time_new = Time::now();
        new_function_time = std::chrono::duration<double>(end_time_new - start_time_new).count();
        end_time_total_new = Time::now();
        total_test_time_new = std::chrono::duration<double>(end_time_total_new - start_time_total_new).count();
        assert(std::set<std::string>(result_new.begin(), result_new.end()) == expected_result);
        average_new_time = (repeat_no * average_new_time + new_function_time) / (repeat_no + 1);
        std::cout << "Current average new time: " << average_new_time << " seconds" << std::endl;
        std::cout << "New function time: " << new_function_time << " seconds" << std::endl;
        std::cout << "Total test case time: " << total_test_time_new << " seconds" << std::endl;
    }

    std::cout << "End of intense function runs." << std::endl;
    std::cout << "Average old function time: " << average_old_time << " seconds" << std::endl;
    std::cout << "Average new function time: " << average_new_time << " seconds" << std::endl;

    std::cout << "Test performance intensive case for old function took " << average_old_time
              << " seconds but new function took " << average_new_time << " seconds" << std::endl;

    if (average_old_time < average_new_time)
    {
        std::cout << "Old is faster than new" << std::endl;
    }
    else if (average_old_time == average_new_time)
    {
        std::cout << "They take the same time" << std::endl;
    }
    else
    {
        std::cout << "New is faster than old" << std::endl;
    }
}

int main() {
    test_performance_intensive_case();
    return 0;
}

Это вывело на терминал (сокращенно, удалив журналы для пустой на данный момент функции deduulate_keywords_new) следующее:

started old function!
removed duplicates in 9.64173 seconds
Sorted by length in 3.36138 seconds
Filtered in 0.366933 seconds
Total function time: 21.0037 seconds
old function time: 405.213 seconds
Total test case time: 405.213 seconds

Помимо общего снижения скорости, журналы показывают, что возврат функции (return unique keywords) занимает очень много времени. Об этом можно судить по тому факту, что std::cout << "old function time: " << old_function_time << " seconds" << std::endl; существует вне функции, и поэтому единственное, что может вызвать замедление, — это оператор return в исходном коде. Почему это? И что я могу сделать, чтобы остановить это? Я новичок в программировании и разработке на C++, поэтому было бы здорово, если бы ваши объяснения были подробными и полными.

Компиляция и другие факторы

Флаги компиляции, которые я использовал, были -g -O3 -std=c++17. Казалось бы, это не является причиной части проблемы, однако, похоже, так оно и было. Поскольку я не так часто использую C++, я остановился на использовании VSCode и использовал расширение C/C++ с задачей сборки, содержащей эти аргументы. Я сделал это для удобства использования — теперь я мог просто нажать одну кнопку, и код скомпилировался и запустился. Оказывается, поскольку я нажал эту кнопку, код запускался в полуотладочном режиме, без каких-либо функций отладки, но код выполнялся одинаково медленно. Это привело к ужасным временам. Эта проблема была в основном решена за счет запуска кода вручную через терминал.

Итак, урок усвоен... при кодировании на C++ в VSCode не ускоряйте тестирование кода, нажимая кнопку запуска, просто сначала создайте, а затем запустите исполняемый файл через терминал.

Это действительно дало значительное ускорение. Теперь код работает почти так же быстро, но все же медленнее, чем код Python, как можно увидеть в этом новом журнале консоли:

started old function!
removed duplicates in 3.2457 seconds
Sorted by length in 1.83285 seconds
Filtered in 0.327369 seconds
Total function time: 5.60095 seconds
old function time: 6.46725 seconds
Total test case time: 6.46725 seconds

Эффекты запуска повторов и просмотра диспетчера задач

Теперь, когда время выполнения моего кода сократилось до разумного размера, я решил выполнить 100 повторов кода C++, чтобы получить точную картину времени выполнения моего кода. Оказывается, мой первоначальный код был чем-то необычным с точки зрения времени выполнения, и наиболее показательное время, которое я мог получить, было:

Average old function time: 5.96633 seconds

Как видите, 5,96633 секунды — это больше, чем 5,7 секунды, которые потребовался коду Python. Почему этот разрыв все еще существует? И как мне переписать код, чтобы он работал быстрее? На первый взгляд код в обоих случаях кажется логически идентичным.