@mrpropper

Почему код на C++ и Python соизмеримо медлительны? Как исправить?

def main():
    n = int(input())
    input1 = list(input().split())
    output = []
    input1.reverse()
    for i in input1:
        if i not in output:
            output.append(i)

    print(len(output))
    output.reverse()
    for i in output:
        print(i, end = ' ')

main()

Аналогичный код на C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool checkel(vector<int> mas,int el)
{
    for (int i:mas)
        if (i == el)
            return true;
    return false;
}

int main()
{
    int n;
    cin >> n;
    int* mas = new int[n];
    for (int i=0;i<n ;i++ ) {
        cin >> mas[i];
    }
    vector<int> vec;
    for (int i=n-1;i>=0 ;i--) {
        if (!checkel(vec,mas[i])) {
            vec.push_back(mas[i]);
        }
    }

    cout << vec.size() << endl;
    reverse( vec.begin(), vec.end() );
    for (int i:vec)
        cout << i << ' ';
    return 0;
}

Они показывали соизмеримо плохие результаты на скорость. От пайтона я ожидал, но от крестов...
Или может это из-за задержки вывода (в крестах)? Как его можно оптимизировать?
  • Вопрос задан
  • 389 просмотров
Решения вопроса 2
zagayevskiy
@zagayevskiy
Android developer at Yandex
Возможно, дело в неоптимальном алгоритме. В худшем случае у тебя будет квадратичная сложность. Перестань гулять по внутреннему списку постоянно, и думаю, станет быстрее. Ну, и не надо рнверсить массивы, просто обходи их в обратном порядке.
Также посмотри, как олимпиадники настраивают ввод-вывод, это может влиять.
Ответ написан
@Andy_U
Попробуйте так:

from typing import List


def func(input1: List[str]) -> List[str]:
    seen = set()
    return [x for x in input1[::-1] if not (x in seen or seen.add(x))][::-1]


if __name__ == '__main__':
    inp = ['1', '2', '3', '2', '1']
    print(func(inp))
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
Frontend777
@Frontend777
Ubuнтер, php разраб, Wordпрессер, человек
По-моему python не медленный
Вот си да.....
Ответ написан
@k-morozov
Код на С++:
1. передавай вектор в функцию по ссылке, в цикле for попробуй ссылку - хотя там int профит вряд ли будет
2. если нужно просто вывести результат - то модно из reverse
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы