Как ускорить программу?

Question

[Vapekreng]

Решаю задачу https://informatics.mccme.ru/moodle/mod/statements...
Не проходит по времени выполнения. Вот мое решение:

def get_data():
    f = open('input.txt', 'r')
    text = f.read()
    f.close()
    _count_of_people, _count_of_actions, _actions = process_data(text)
    _queue = get_init_queue(_count_of_people)
    return _count_of_people, _count_of_actions, _actions, _queue


def process_data(text):
    data = text.split()
    _count_of_people = int(data[0])
    _count_of_actions = int(data[1])
    _actions = data[2:]
    return _count_of_people, _count_of_actions, _actions


def get_init_queue(_count_of_people):
    _queue = list()
    for i in range(1, _count_of_people + 1):
        _queue.append(str(i))
    return _queue


def get_answer(_count_of_actions, _actions, _queue):
    for i in range(_count_of_actions):
        action = actions[i]
        index = _queue.index(action)
        _queue.pop(index)
        _queue.append(action)
    return _queue


def set_answer(_queue):
    f = open('output.txt', 'w')
    text = ' '.join(_queue)
    f.write(text)
    f.close()


count_of_people, count_of_actions, actions, queue = get_data()
answer = get_answer(count_of_actions, actions, queue)
set_answer(answer)

Какие будут советы по алгоритму?

Comments

[Vapekreng]

Ссылка на условие во второй строке...

Answer 1

[tsarevfs]

Можно решать асимптотически быстрее если не заниматься симуляцией процесса.
Идея в том, что тот кто выходил подышать позже точно окажется после того кто выходил раньше или совсем не выходил.

spoiler

fin = open('input.txt', 'r')

n, _, *actions = (int(v) for v in fin.read().split())

nToLastPos = {n : i for (i, n) in enumerate(actions)}

res = sorted(range(1, n + 1),
			 key=lambda v: nToLastPos.get(v, -1))

fout = open('output.txt', 'w')
fout.write(' '.join((str(a) for a in res)))

Из советов по python коду:
1. Не храните размер отдельно от списка. Его всегда можно получить с помощью len(arr)
2. По возможности не используйте for i in range(len(arr)). Вместо этого for value in arr или for i, value in enumerate(arr)
3. Генераторы списков или словарей очень полезны.
4. Распакова списков в переменные тоже очень удобная тема.

Comments

[Vapekreng]

Благодарю, ваш код прошел все тесты и быстрее моего в 5-11 раз, буду разбираться

[tsarevfs]

Vapekreng, у вас каждый action будет занимать O(n) времени. Суммарно O(n*t).
Мое решение строит словарь (который реализован как hash map) за O(n) потом сортирует за стандартные O(n*log(n)), поскольку запрос в словаре работает за O(1).

Answer 2

[Дмитрий Шицков]

Какой-то слегка перегруженный у вас код

params1 = 4,5
params2 = 2,3,1,2,1

queue = [i for i in range(1,params1[0]+1)]

for num in params2:
  queue.remove(num)
  queue.append(num)

print(queue)

Comments

[Vapekreng]

Насчет перегруженного кода своя специфика - готовлю 10-й класс к олимпиаде. Программирование у них первый год, только-только списки прошли, так что стараюсь писать развернутые решения. Кроме того в задачах много общего - немалую часть можно переносить из одной в другую практически без изменений. Ну и плюс, намного проще отладка.
По поводу решения - данные берутся из input.txt и записываются в output.txt и их может быть очень много. Простые тесты проходит на ура, а вот длинные не тянет.