Блог

Главная - Вопросы по программированию - Почему я все еще получаю «Прекращено из-за ошибки тайм-аута» даже после использования deque вместо списка?

Почему я все еще получаю «Прекращено из-за ошибки тайм-аута» даже после использования deque вместо списка?

#python #python-3.x #list #timeout #deque

#python #python-3.x #Список #тайм-аут #deque

Вопрос:

Я написал следующий код для вывода количества отдельных слов из входных данных, а также их количества вхождений для каждого отдельного слова в соответствии с их появлением во входных данных.

Я использовал метод добавления и подсчета списка и получил желаемый результат, но некоторые тестовые примеры не выполнялись из-за ошибки тайм-аута.

 n = int(input())
ar = []
for _ in range(n):
    ar.append(input().rstrip())

def wordOrder(n, ar):    
    w_list =[] #list contains the number of repition of words
    u_list =[] #list eliminates the duplicates while maintaining the same order
    for i in ar:
        if i not in u_list:
            u_list.append(i)
            w_list.append(ar.count(i))
       
    return w_list
    
result = wordOrder(n, ar)
print(len(result))
print(*result, sep=' ')

Итак, я попытался использовать deque вместо list, думая, что это может быть связано с проблемой временной сложности O (n) для метода добавления списка. Но я получаю ту же ошибку даже после использования deque.

Мой вопрос в том, связана ли проблема с временной сложностью или с некоторыми другими факторами? Было бы здорово, если бы кто-нибудь мог объяснить, какие методы следует адаптировать, чтобы избежать ошибки тайм-аута.

Пример ввода:

 4
bcdef
abcdefg
bcde
bcdef

Пример вывода:

 3
2 1 1

Комментарии:

1. Вы используете неправильную структуру данных для этой проблемы. Как насчет словаря?

2. deque и list имеют аналогичную производительность для append операций. Вы должны использовать deque , если в вашем коде много appendLeft операций.

3. Кроме того, вы можете получить ошибку тайм-аута, если ваша программа занимает слишком много места.

4. @Shiva Спасибо за предложение. Похоже, я не должен использовать deque в такой ситуации в качестве замены списка.

5. @zenalc Да, я пытался использовать словарь для решения этой проблемы, но порядок, в котором они были расположены, вызвал проблему. Не думал об использовании Counter(), потому что я думал, что там будет та же проблема с порядком. Но Counter() теперь отлично справился с этой проблемой.

Ответ №1:

Этот код отлично работает для меня

 from collections import Counter

a=[]

for i in range(int(input())):

      a.append(input())

x = Counter(a)

print(len(x.keys()))

print(*x.values())

Комментарии:

1. Да, этот код решает проблему. Спасибо за это! Итак, усложняет ли проблему использование метода добавления списка? Кроме того, кажется, что я должен избегать deque, если только он не используется по прямому назначению, например, операция appendLeft. Это так?

2. Счетчик — это подкласс dict. Это неупорядоченная коллекция, в которой элементы и их соответствующее количество хранятся в виде словаря.

3. Что ж, это выглядит довольно простым способом решения этой проблемы. Может быть, мне полезно решить подобные проблемы с кодированием в python.

Ответ №2:

Хотя, к счастью, в этой проблеме работает только Counter() , безопасно использовать OrderedDict(), чтобы сохранить существующий порядок предоставленных входных данных. Следовательно, приведенный ниже код должен нормально работать во всех подобных ситуациях, и он не принес никакой «ошибки тайм-аута», чего я и хотел.

 from collections import Counter, OrderedDict

a=[]

for i in range(int(input())):

      a.append(input())

x = OrderedDict(Counter(a))

print(len(x.keys()))

print(*x.values())