What would you use for `n to n` relations in python?

after fiddling around with dictionaries, I came to the conclusion, that I would need a data structure that would allow me an n to n lookup. One example would be: A course can be visited by several students and each student can visit several courses.

What would be the most pythonic way to achieve this? It wont be more than 500 Students and 100 courses, to stay with the example. S开发者_开发百科o I would like to avoid using a real database software.

Thanks!

Since your working set is small, I don't think it is a problem to just store the student IDs as lists in the Course class. Finding students in a class would be as simple as doing

course.studentIDs

To find courses a student is in, just iterate over the courses and find the ID:

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

There's other ways you could do it. You could have a dictionary of studentIDs mapped to courseIDs or two dictionaries that - one mapped studentIDs:courseIDs and another courseIDs:studentIDs - when updated, update each other.

The implementation I wrote out the code for would probably be the slowest, which is why I mentioned that your working set is small enough that it would not be a problem. The other implentations I mentioned but did not show the code for would require some more code to make them work that just aren't worth the effort.

It depends completely on what operations you want the structure to be able to carry out quickly.

If you want to be able to quickly look up properties related to both a course and a student, for example how many hours a student has spent on studies for a specific course, or what grade the student has in the course if he has finished it, and if he has finished it etc. a vector containing n*m elements is probably what you need, where n is the number of students and m is the number of courses.

If on the other hand the average number of courses a student has taken is much less than the total number of courses (which it probably is for a real case scenario), and you want to be able to quickly look up all the courses a student has taken, you probably want to use an array consisting of n lists, either linked lists, resizable vectors or similar – depending on if you want to be able to with the lists; maybe that is to quickly remove elements in the middle of the lists, or quickly access an element at a random location. If you both want to be able to quickly remove elements in the middle of the lists and have quick random access to list elements, then maybe some kind of tree structure would be the most suitable for you.

Most tree data structures carry out all basic operations in logarithmic time to the number of elements in the tree. Beware that some tree data structures have an amortized time on these operators that is linear to the number of elements in the tree, even though the average time for a randomly constructed tree would be logarithmic. A typical example of when this happens is if you use a binary search tree and build it up with increasingly large elements. Don't do that; scramble the elements before you use them to build up the tree in that case, or use a divide-and-conquer method and split the list in two parts and one pivot element and create the tree root with the pivot element, then recursively create trees from both the left part of the list and the right part of the list, these also using the divide-and-conquer method, and attach them to the root as the left child and the right child respectively.

I'm sorry, I don't know python so I don't know what data structures that are part of the language and which you have to create yourself.

I assume you want to index both the Students and Courses. Otherwise you can easily make a list of tuples to store all Student,Course combinations: [ (St1, Crs1), (St1, Crs2) .. (St2, Crs1) ... (Sti, Crsi) ... ] and then do a linear lookup everytime you need to. For upto 500 students this ain't bad either.

However if you'd like to have a quick lookup either way, there is no builtin data structure. You can simple use two dictionaries:

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

For a given student s, looking up courses is now students[s]; and for a given course c, looking up students is courses[c].

For something simple like what you want to do, you could create a simple class with data members and methods to maintain them and keep them consistent with each other. For this problem two dictionaries would be needed. One keyed by student name (or id) that keeps track of the courses each is taking, and another that keeps track of which students are in each class.

defaultdicts from the 'collections' module could be used instead of plain dicts to make things more convenient. Here's what I mean:

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()

Which when run produces the following output:

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']