Студенты второго уровня

Я решил вызов вложенного списка Python на HackerRank.com , передавая все тестовые примеры. Хотя эта проблема, вероятно, может быть решена с помощью короткого сценария с умными однострочками, мой подход состоял в том, чтобы решить его чистым, понятным способом в функциональном стиле.

Вот краткое описание проблемы, см. ссылку выше для полного описания:

  

Распечатайте имя (имена) любого учащегося (ов), имеющего второй низший класс; если есть несколько учеников, закажите их имена в алфавитном порядке и распечатайте их на новой строке.

     

Первая строка содержит целое число, \ $ N \ $, количество студентов.   Последующие строки \ $ 2N \ $ описывают каждого ученика над \ $ 2 \ $ линиями; первая строка содержит имя учащегося, а вторая строка содержит их оценку.

Я до сих пор не использовал вложенные списки, и мне пришлось искать в Интернете хороший бит для частей функций (в частности, get_lowest_grade), и я хотел бы улучшить этот код как можно больше.

def get_students(num_students: int) -> list:
    """Returns a list of names and grades of N students read from stdin
    where each name and respective grade is separated by a new line."""
    students = []
    for s in range(0, num_students):
        name = input()
        grade = float(input())
        students.append([name, grade])
    return students

def get_lowest_grade(students: list) -> float:
    """Returns the lowest grade from a list of students[name, grade]."""
    lowest_grade_student = min(students, key = lambda x: x[1])
    return lowest_grade_student[1]

def get_lowest_grade_students(students: list) -> list:
    """Returns the students with the lowest grade 
    from a list of students[name, grade]."""
    return [s for s in students if s[1] == get_lowest_grade(students)]

def exclude_lowest_grade_students(students: list) -> list:
    """Returns a list of students with the lowest graded students excluded
    from a list of students[name, grade]."""
    return [s for s in students if s[1] != get_lowest_grade(students)]

def get_student_names_sorted_alpha(students: list) -> list:
    """Returns a list of names sorted alphabetically from a list of students[name, grade]"""
    names = [s[0] for s in students]
    return sorted(names)

def main():
    num_students = int(input())
    students = get_students(num_students)
    lowest_excluded = exclude_lowest_grade_students(students)
    second_lowest = get_lowest_grade_students(lowest_excluded)
    for name in get_student_names_sorted_alpha(second_lowest):
        print(name)

if __name__ == '__main__':
    main()
8 голосов | спросил Phrancis 26 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 26 Sep 2016 18:50:48 +0300 2016, 18:50:48

3 ответа


5

Ваш код выглядит хорошо и хорошо документирован.

Однако многие детали могут быть улучшены.

  • num_students = int(input()) можно перемещать в get_students, чтобы ваш код имел дело с вводом в одном месте.

  • , хотя проблема говорит о списках, может быть более идиоматично использовать список кортежей вместо списка. Я настоятельно рекомендую отличную статью Ned Batchelder «Списки против тупиков» , чтобы узнать больше о это.

  • 0 как первый аргумент range не требуется, поскольку это значение по умолчанию. Поэтому вы можете переписать: for s in range(0, num_students): как for s in range(num_students): .

  • Подчеркивание (_) довольно условно для переменной с используемым значением, чтобы вы могли написать: for _ in range(num_students):

  • Добавление простого выражения print в get_lowest_grade показывает, что функция вызывается чаще, чем требуется. Это реальная проблема, когда у вас много учеников, потому что ваш алгоритм проходит через всех студентов для всех студентов . Ваш алгоритм называется квадратичным или O(n^2). Вы можете получить самый низкий класс раз и навсегда.

Ваш код будет выглядеть так:

def get_students() -> list:
    """Returns a list of names and grades of N students read from stdin
    where each name and respective grade is separated by a new line."""
    return [('Harry', 37.21), ('Berry', 37.21), ('Tina', 37.2), ('Akriti', 41), ('Harsh', 39),
            ('Harry', 37.21), ('Berry', 37.21), ('Tina', 37.2), ('Akriti', 41), ('Harsh', 39),
            ('Harry', 37.21), ('Berry', 37.21), ('Tina', 37.2), ('Akriti', 41), ('Harsh', 39)]
    num_students = int(input())
    students = []
    for s in range(num_students):
        name = input()
        grade = float(input())
        students.append((name, grade))
    return students

def get_lowest_grade(students: list) -> float:
    """Returns the lowest grade from a list of students[name, grade]."""
    lowest_grade_student = min(students, key = lambda x: x[1])
    return lowest_grade_student[1]

def get_students_with_grade(students: list, grade: float) -> list:
    """Returns the students with the lowest grade 
    from a list of students(name, grade)."""
    return [s for s in students if s[1] == grade]

def get_students_without_grade(students: list, grade: float) -> list:
    """Returns a list of students with the lowest graded students excluded
    from a list of students(name, grade)."""
    return [s for s in students if s[1] != grade]

def get_student_names_sorted_alpha(students: list) -> list:
    """Returns a list of names sorted alphabetically from a list of students[name, grade]"""
    names = [s[0] for s in students]
    return sorted(names)

def main():
    students = get_students()
    lowest_grade = get_lowest_grade(students)
    students2 = get_students_without_grade(students, lowest_grade)
    lowest_grade2 = get_lowest_grade(students2)
    second_lowest = get_students_with_grade(students2, lowest_grade2)
    for name in get_student_names_sorted_alpha(second_lowest):
        print(name)

if __name__ == '__main__':
    main()

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

ответил Josay 26 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 26 Sep 2016 22:31:41 +0300 2016, 22:31:41
5

Производительность

В этой функции get_lowest_grade(...) будет вызываться один раз для каждого ученика:

def get_lowest_grade_students(students: list) -> list:
    """Returns the students with the lowest grade
    from a list of students[name, grade]."""
    return [s for s in students if s[1] == get_lowest_grade(students)]

exclude_lowest_grade_students имеет тот же недостаток.

Еще одна проблема с производительностью - это повторное создание списка. Особенно тот, который создает список без самых младших учеников: так как этот список обычно имеет такой же размер, как и оригинал, это пустая трата памяти.

Алгоритм

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

Было бы проще найти второй самый низкий балл, а затем отфильтровать на этот счет.

В качестве последующего упражнения обобщение для поиска k-й самой низкой оценки, без фактического сортировки всего списка, представляет собой интересную проблему для взлома (см. сортировку).

Именованные кортежи

Хотя основной целью упражнения являются вложенные списки, вы можете с благодарностью узнать о named tuples . Используя названные кортежи, вы можете заменить бессмысленные индексы следующим образом:

names = [s[0] for s in students]

с таким кодом:

names = [s.name for s in students]

Чтобы сделать это возможным, вы можете создать Student с именем tuple с помощью:

from collections import namedtuple

Student = namedtuple('Student', ['name', 'score'])

И добавьте учащихся в список students:

students.append(Student(name, grade))

Стиль кодирования

Стиль кодирования почти безупречен, есть только два незначительных нарушения PEP8 :

  • Не должно быть пробелов вокруг параметров ключевых слов, поэтому вместо min(students, key = lambda x: x.score) это должно быть min(students, key=lambda x: x.score)
  • Перед определениями функций должно быть две пустые строки
ответил janos 26 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 26 Sep 2016 22:39:45 +0300 2016, 22:39:45
2

Подобно Janos, я бы предложил использовать collections.namedtuple для Student объект:

from collections import namedtuple

Student = namedtuple("Student", ("name", "grade"))

Это также поможет, как он отметил, определить функцию k-low grade, например:

def get_k_lowest_grade(students, k):
    """Returns the k-lowest grade from a list of Students(name, grade)."""
    grades = set(s.grade for s in students)
    return sorted(grades)[k - 1]

Я бы также сделал get_students_with_grade вернуть генератор, чтобы избежать дублирования памяти и того же для get_student_names_sorted_alpha (вам просто нужно знать, что вы можете перебирать результаты функции ровно один раз):

def get_students_with_grade(students, grade):
    """Returns all students with `grade`
    from a list of Students(name, grade)."""
    return (s for s in students if s.grade == grade)


def get_student_names_sorted_alpha(students):
    """Returns a generator of names sorted alphabetically from a list of Students(name, grade)"""
    yield from sorted(s.name for s in students)

Это делает ваш код main немного короче:

def main():
    students = get_students()
    lowest_grade_2 = get_k_lowest_grade(students, k=2)
    second_lowest = get_students_with_grade(students, lowest_grade_2)
    for name in get_student_names_sorted_alpha(second_lowest):
        print(name)
ответил Graipher 27 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 27 Sep 2016 16:00:57 +0300 2016, 16:00:57

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

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132