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

Question

[mrpropper]

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;
}

Они показывали соизмеримо плохие результаты на скорость. От пайтона я ожидал, но от крестов...
Или может это из-за задержки вывода (в крестах)? Как его можно оптимизировать?

Comments

[Армянское Радио]

Ну, выложив код, вы все равно нарушили условия конкурса.

[mrpropper]

Армянское Радио, Нет, иначе бы Fless (блогер который поступил в ШАД), его не выложил. Или у Яндекса все равны, но кто-то равнее.
P.s. Очканул я сильно

Answer 1

[Денис Загаевский]

Возможно, дело в неоптимальном алгоритме. В худшем случае у тебя будет квадратичная сложность. Перестань гулять по внутреннему списку постоянно, и думаю, станет быстрее. Ну, и не надо рнверсить массивы, просто обходи их в обратном порядке.
Также посмотри, как олимпиадники настраивают ввод-вывод, это может влиять.

Comments

[mrpropper]

Про пайтон: Мне кажется, что на списко-подобных структурах данных, гораздо эффективнее использовать цикл foreach, ибо индексная адресация будет отсчитывать каждый элемент.
Про плюсы:Я согласен, что опрометчиво было делать функцию, тем самым создавая O(n^2), но к несчастью времени было все меньше, а с итераторами я знаком плохо. Возможно, стоило реализовать бинарный поиск, но уже ничего не сделаешь)
Если я в чем-то не прав, извините, в частности про архитектуру структур данных)

[Денис Загаевский]

Тимофей, бинарный поиск тебе не поможет, массив-то не отсортирован. Можно попробовать отдельный unordered_set для поиска и вектор для хранения. Я так понял, надо вывести уники в порядке их появления. В джаве я бы посоветовал LinkedHashSet, не знаю, есть ли такая структура в плюсах.

[Andy_U]

Денис Загаевский, Только надо последнее появление запоминать - поэтому автор списки вертел.

Answer 2

[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))

Comments

[mrpropper]

Хорошее решение, но порядок сохранять надо(

[Andy_U]

mrpropper, Он сохраняется.

[Andy_U]

mrpropper, Ну, или покажите такие входные данные, где приведенный мной вариант дает ответ, отличный от вашего.

[mrpropper]

Andy_U, Извините, все еще надо?

[mrpropper]

Andy_U,

1.py - мое
2.py - ваше
Входные данные: [1,2,3,4,10,3,3,3,2,11]

[Andy_U]

mrpropper, 1) А почему у вас числа на входе? Должны быть строки, судя по Вашему исходному коду - вы нигде информацию, вводимую с командной строки, в int не преобразовывали. 2) Я там через пару минут после ответа код чуть подправил (вначале забыл перевернуть исходную строку). Перепроверьте.

[mrpropper]

Andy_U, А смысл))) Питону все равно что сравнивать, извините если не прав, а лишний проход по списку map(int,input1) это увеличение времени. Ввод задуман как строка вида "1 2 3 4 10 3 3 3 2 11".
Я перепроверил, у Вас все верно.

[Andy_U]

mrpropper, Сравнение (длинных) строк может сильно отличаться по времени от сравнения целых чисел на равенство. Та же фигня с вычислением хэш-функций. А так, если не учитывать, что без аннотаций код писать не стоит, чтобы исключить глупые ошибки, да.

[mrpropper]

Andy_U, Большое спасибо, всё учту.

Answer 3

[Артём Варламов]

По-моему python не медленный

Вот си да.....

Comments

[mrpropper]

Python сильно проигрывает в скорости при использовании циклов, вопрос в том что С++ показывает такие же плохие результаты (Не укладывается в время)

Answer 4

[k-morozov]

Код на С++:
1. передавай вектор в функцию по ссылке, в цикле for попробуй ссылку - хотя там int профит вряд ли будет
2. если нужно просто вывести результат - то модно из reverse