Реализация кода на C++ работает медленнее, чем на Python

Question

Реализация кода на C++ работает медленнее, чем на Python

Рейтинг: 2Ответов: 1Опубликовано: 14.05.2023

Написал две одинаковые программы на Python и C++ и заметил, что Python быстрее, но почему? Обе программы деают следующее: вы вводите строку, из символов которой буду создаваться все возможные вариации, длины которых варьируются от 4 до n символов, где n - длина введенной строки. Создается директория, с указанным пользователем названием, в которой создаются несколько файлов с названиями comb_i.txt, где i - длина вариаций, который записаны в файле.

Код на Python:

import os
import itertools

s = input('Введите пароль: ')
chars = set(s)
n = input('Введите имя: ')
os.mkdir(f'Passes_{n}')

for i in range(4, len(s) + 1):
    with open(f'Passes_{n}/comb_{i}.txt', 'w') as file:
        for combo in itertools.permutations(chars, i):
            file.write("".join(combo) + "\n")
print('Все пароли сгенерированы')

Код на C++:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <unordered_set>
#include <sys/stat.h> // Для создания директории
#include <filesystem> // Для работы с файловой системой
#include <sstream> // Для преобразования числа в строку

using namespace std;
namespace fs = std::filesystem;

void generate_permutations(string& current_input, unordered_set<string>& variations, int start_index, int length) {
    if (start_index == length) {
        variations.insert(current_input.substr(0, length));
        return;
    }
    for (int i = start_index; i < current_input.length(); ++i) {
        swap(current_input[start_index], current_input[i]);
        generate_permutations(current_input, variations, start_index + 1, length);
        swap(current_input[start_index], current_input[i]);
    }
}

int main() {
    string user_input;
    cout << "Введите пароль: ";
    cin >> user_input;

    string folder_name;
    cout << "Введите название папки: ";
    cin >> folder_name;

    
    if (!fs::exists(folder_name)) {
        fs::create_directory(folder_name);
    }

    
    for (int i = 4; i <= user_input.length(); ++i) {
        unordered_set<string> variations;
        string current_input = user_input;
        sort(current_input.begin(), current_input.end());
        generate_permutations(current_input, variations, 0, i);

        
        string file_name = folder_name + "/comb_" + to_string(i) + ".txt";
        ofstream file(file_name, ios::out | ios::binary);
        if (file.is_open()) {
            stringstream ss;
            for (const auto& variation : variations) {
                ss << variation << '\n'; 
            }
            file << ss.str();
            file.close();
        }
    }

    cout << "Все пароли сгенерированы" << endl;
    return 0;
}

Замеры для C++:

$ time ./a.out  
Введите пароль: qwertyuiop
Введите название папки: Testcpp
Все пароли сгенерированы

real    18,06s
user    11,33s
sys 0,25s
cpu 64%

Замеры для Python:

$ time python3 passs.py  
Введите пароль: qwertyuiop
Введите имя: Testpy
Все пароли сгенерированы

real    11,21s
user    2,75s
sys 0,13s
cpu 25%

python c# производительность файлы

Источник: Stack Overflow на русском

Answer 1

▲ 4Принят

Во-первых, программы на Питоне и на C++ дают разные результаты если на вход дана строка с не уникальными символами. В такой ситуации их просто нельзя сравнивать. Везде дальше я буду работать только с уникальными символами.

Во-вторых, чтобы было удобно сравнивать я избавлюсь от файлового вывода. Вот так:

import itertools


s = input()
for i in range(4, len(s) + 1):
    for p in itertools.permutations(s, i):
        print(''.join(p))

#include <algorithm>
#include <iostream>
#include <unordered_set>

using namespace std;

void generate_permutations(string& current_input, unordered_set<string>& variations, int start_index, int length) {
    if (start_index == length) {
        variations.insert(current_input.substr(0, length));
        return;
    }
    for (int i = start_index; i < static_cast<int>(current_input.length()); ++i) {
        swap(current_input[start_index], current_input[i]);
        generate_permutations(current_input, variations, start_index + 1, length);
        swap(current_input[start_index], current_input[i]);
    }
}

int main() {
    string s;
    cin >> s;
    
    for (int i = 4; i <= static_cast<int>(s.length()); ++i) {
        unordered_set<string> variations;
        string current_input = s;
        sort(current_input.begin(), current_input.end());
        generate_permutations(current_input, variations, 0, i);
        
        for (const auto& variation : variations) {
            cout << variation << '\n'; 
        }
    }
}

Сравнение за одну минуту показывает что результаты одинаковые:

$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror -Wwrite-strings -Wconversion -O3 permutations.cpp 

$ time diff <(echo 0123456789 | python permutations.py | sort) <(echo 0123456789 | ./a.out | sort)

real  0m38.229s
user  0m54.528s
sys   0m1.072s

Теперь сравниваем время работы. Шесть секунд Питон, восемь - С++:

$ time echo 0123456789 | python permutations.py | wc -l
9863280

real  0m5.695s
user  0m5.788s
sys   0m0.080s

$ time echo 0123456789 | ./a.out | wc -l
9863280

real  0m8.144s
user  0m7.916s
sys   0m0.168s

Причина медлительности C++ в накоплении результатов в unordered_set. Зачем это делать? Если все символы уникальны, то и все результаты будут уникальны.

Убираем хеш-таблицу:

#include <algorithm>
#include <iostream>

using namespace std;

void generate_permutations(string& current_input, int start_index, int length) {
    if (start_index == length) {
        cout << current_input.substr(0, length) << '\n';
        return;
    }
    for (int i = start_index; i < static_cast<int>(current_input.length()); ++i) {
        swap(current_input[start_index], current_input[i]);
        generate_permutations(current_input, start_index + 1, length);
        swap(current_input[start_index], current_input[i]);
    }
}

int main() {
    string s;
    cin >> s;
    
    for (int i = 4; i <= static_cast<int>(s.length()); ++i) {
        generate_permutations(s, 0, i);
    }
}

Я проверил через diff что результат не изменился. Время C++ теперь в семь раз лучше чем у Питона. Не плохо для столь простой реализации:

$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror -Wwrite-strings -Wconversion -O3 permutations-2.cpp 

$ time echo 0123456789 | ./a.out | wc -l
9863280

real  0m0.761s
user  0m0.844s
sys   0m0.056s

Реализация кода на C++ работает медленнее, чем на Python

Ответы