Что бы вы использовали для `n to n` отношений в python?

Question

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

Каким будет самый питонский способ достичь этого?Это не будет более 500 студентов и 100 курсов, чтобы остаться на примере.Поэтому я хотел бы избежать использования реального программного обеспечения для баз данных.

Спасибо!

Answer 1

Это полностью зависит от того, какие операции вы хотите, чтобы структура могла выполнять быстро.

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

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

Большинство данных дереваСтруктуры выполняют все основные операции за логарифмическое время с количеством элементов в дереве.Помните, что некоторые структуры данных дерева имеют амортизированное время для этих операторов, которое является линейным по отношению к числу элементов в дереве, даже если среднее время для случайно построенного дерева будет логарифмическим.Типичный пример того, когда это происходит, если вы используете бинарное дерево поиска и строите его из все более крупных элементов.Не делай этого;скремблируйте элементы перед тем, как использовать их для построения дерева в этом случае, или используйте метод «разделяй и властвуй» и разбивайте список на две части и один элемент сводки и создайте корень дерева с элементом сводки, а затем рекурсивно создайте деревьякак из левой части списка, так и из правой части списка, они также используют метод «разделяй и властвуй» и присоединяют их к корню как левый и правый дочерние элементы соответственно.

Iизвините, я не знаю python, поэтому я не знаю, какие структуры данных являются частью языка и которые вы должны создать самостоятельно.

Answer 2

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

course.studentIDs

Чтобы найти курсы, на которых учится студент, просто итерируйте курсы и найдите ID:

studentIDToGet = "johnsmith001"
studentsCourses = list()
for course in courses:
    if studentIDToGet in course.studentIDs:
        studentsCourses.append(course.id)

Есть и другие способыВы могли бы сделать это.У вас может быть словарь студентов идентификаторов, сопоставленных с courseID, или два словаря, которые - один сопоставленный studentID: courseIDs и другой courseID: studentIDs - при обновлении обновляют друг друга.

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

Answer 3

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

defaultdicts из модуля 'коллекций' можно использовать вместо простого dicts, чтобы сделать вещи более удобными. Вот что я имею в виду:

from collections import defaultdict

class Enrollment(object):
    def __init__(self):
        self.students = defaultdict(set)
        self.courses = defaultdict(set)

    def clear(self):
        self.students.clear()
        self.courses.clear()

    def enroll(self, student, course):
        if student not in self.courses[course]:
            self.students[student].add(course)
            self.courses[course].add(student)

    def drop(self, course, student):
        if student in self.courses[course]:
            self.students[student].remove(course)
            self.courses[course].remove(student)
        # remove student if they are not taking any other courses
        if len(self.students[student]) == 0:
            del self.students[student]

    def display_course_enrollments(self):
        print "Class Enrollments:"
        for course in self.courses:
            print '  course:', course,
            print ' ', [student for student in self.courses[course]]

    def display_student_enrollments(self):
        print "Student Enrollments:"
        for student in self.students:
            print '  student', student,
            print ' ', [course for course in self.students[student]]

if __name__=='__main__':

    school = Enrollment()

    school.enroll('john smith', 'biology 101')
    school.enroll('mary brown', 'biology 101')
    school.enroll('bob jones', 'calculus 202')

    school.display_course_enrollments()
    print
    school.display_student_enrollments()

    school.drop('biology 101', 'mary brown')
    print
    print 'After mary brown drops biology 101:'
    print
    school.display_course_enrollments()
    print
    school.display_student_enrollments()

Который при запуске выдает следующий вывод:

Class Enrollments:
  course: calculus 202   ['bob jones']
  course: biology 101   ['mary brown', 'john smith']

Student Enrollments:
  student bob jones   ['calculus 202']
  student mary brown   ['biology 101']
  student john smith   ['biology 101']

After mary brown drops biology 101:

Class Enrollments:
  course: calculus 202   ['bob jones']
  course: biology 101   ['john smith']

Student Enrollments:
  student bob jones   ['calculus 202']
  student john smith   ['biology 101']

Answer 4

Я предполагаю, что вы хотите проиндексировать как студентов, так и курсы.В противном случае вы можете легко составить список кортежей для хранения всех комбинаций Student, Course: [(St1, Crs1), (St1, Crs2) .. (St2, Crs1) ... (Sti, Crsi) ...], а затемделать линейный поиск каждый раз, когда вам нужно.Для 500 студентов это тоже неплохо.

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

courses = { crs1: [ st1, st2, st3 ], crs2: [ st_i, st_j, st_k] ... } 
students = { st1: [ crs1, crs2, crs3 ], st2: [ crs_i, crs_j, crs_k] ... } 

Для данного студента, поиск курсов теперь является студентами [s];и для данного курса c поиск студентов - это курсы [c].