Как обработать ошибку времени или ограничения памяти при создании словаря из пользовательского ввода в Python?

Question

Я пытаюсь решить проблему в программировании HW. Пользователь вводит имена или первые буквы имен. Чем больше имя повторяется, тем больше у человека друзей. Программа должна выводить человека с наибольшим количеством друзей (если есть люди с таким же количеством друзей, любой из них может быть выходом). Слово «END» на входе не должно учитываться. Длина пользовательского ввода не указана, но задание говорит следующее:

"Пожалуйста, обработайте 50 000 друзей или менее в течение 6 секунд. Если вы выполняете O (n ^ 2) обработку с использованием списка без использования dict, возможно, вы ошиблись в ответе, превышающем ограничение по времени?".

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

#!/usr/bin/env python

friendships = {}
count = 0

while True:
    try:
    names = input()

    if names != 'END':

        if not friendships.get(names):
             friendships[names] = 1
        else:
            friendships[names] += 1 

    if names == '':
        break

except EOFError:
    print('ERROR')

max_key = max(friendships, key = friendships.get)
print(max_key, friendships[max_key])

Автоматический грейдер продолжает показывать [ОШИБКА: превышен лимит времени или превышен лимит памяти (я не могу сказать, какой именно)]. Как я могу указать, что «50000 друзей или меньше должны быть обработаны в течение 6 секунд»?

Answer 1

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

#!/usr/bin/env python3

'''
friendship program
'''

def main():
    '''
    a func
    '''
    friendships = {}

    try:
        while True:
            name = input()

            if name not in ['END', '']:
                if name not in friendships:
                    friendships[name] = 1
                else:
                    friendships[name] += 1
            else:
                break

    except EOFError as ex:
        print('ERROR ' + str(ex))

    max_key = max(friendships, key=friendships.get)
    print(max_key, friendships[max_key])

main()

Хотя вышеописанное не должно иметь проблем при обработке 50000 имен за 6 секунд, вы можете попробовать сделать то же самое на другом языке (если у вас нетиспользовать Python, который есть) и посмотреть, поможет ли это.Пример C ++:

#include <iostream>
#include <unordered_map>
#include <algorithm>

int main() {
    std::unordered_map<std::string, unsigned long> friends;
    std::string name;
    while(std::cin >> name) {
        if(name == "END" || name.size() == 0) break;
        ++friends[name];
    }
    auto max_it = std::max_element(
        friends.begin(), friends.end(),
        [](const auto& a, const auto& b) { return a.second < b.second; });

    std::cout << max_it->first << " " << max_it->second << "\n";
}

Answer 2

Чтобы узнать, не исчерпана ли ваша память, используйте библиотеку memory_profiler. Вы можете использовать декоратор @profile, который будет выводить информацию об использовании памяти на строку в ваш стандартный вывод.

Я не думаю, что вы даже можете запустить цикл for от 1 до 50000 за 6 секунд, но хорошим подходом для начала будет поиск диктофона для заданного имени входа и приращения, если поиск будет успешным, иначе, добавить пару KV.

Answer 3

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

Но я могу увидеть одну проблему:

names = input()

Любой желает ввести 50000 имен за шесть секунд! Даже если вы могли бы, грейдер позволяет интерактивный ввод?

Вместо этого вы должны предварительно создать списки друзей, вероятно, в виде текстового файла, и прочитать их в.