本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、連結リストのまとめとして多重リスト構造(Multi List Structure)について学んでいきます。
多重リスト構造とは
通常の連結リストや循環リストでは、次のセルへのポインタを保持し、これを辿っていくことで、リスト全体にアクセスすることができました。
また双方向リストでは、その前のセルへのポインタも保持することで、リストへの挿入や削除などの操作が容易になりました。
今回の多重リスト構造(Multi List Structure)では、2個以上のポインタを保持させ、同時に複数のリストにアクセスすることが可能となります。
書籍では大学における学生の成績を管理することを例として説明しています。
例えば、100人の学生がいて、100科目の授業のうち10科目をそれぞれ履修すると考えます。
各科目ごとの学生の成績をsizeof(short) = 2バイトで考えると、通常のリストでは、100人 × 100科目 × 2バイト= 20,000バイトのメモリが必要です。
しかし、多重リスト構造では、100人 × 10科目 × 2バイト = 2,000バイトのメモリで済むため、配列の場合は90%が無駄な空間(疎な配列)となってしまいます。
また、学生および科目のそれぞれの方向からリストにアクセスできるので、後の集計なども手軽に行うことができます。
なお、計算量の観点からみると、配列では学生数が増加するのに比例して疎な配列となるため、処理に時間を要し、多重リスト構造のほうが有利になると思います。
Pythonで多重リスト構造を作ってみる
それでは、Pythonで多重リスト構造を実装してみます。
# multi_list_structure.py subjects = ["math", "english"] students = ["foo", "bar", "hoge"] class Point: def __init__(self, point): self.stdlink = None self.sbjlink = None self.student = None self.subject = None self.point = point class Student: def __init__(self, name): self.stdlink = None self.name = name class Subject: def __init__(self, name): self.sbjlink = None self.name = name class Class: def __init__(self, students, subjects): self.students = [Student(name) for name in students] self.subjects = [Subject(name) for name in subjects] def add(self, student_id, subject_id, point): try: new = Point(point) new.stdlink = self.students[student_id].stdlink self.students[student_id].stdlink = new new.sbjlink = self.subjects[subject_id].sbjlink self.subjects[subject_id].sbjlink = new new.student = self.students[student_id] new.subject = self.subjects[subject_id] except IndexError: print("student_id or subject_id is wrong.") return def print_score(self, student_id): try: print("{}\t: ".format(self.students[student_id].name), end="") score = self.students[student_id].stdlink while score: print("{}=>{}".format(score.subject.name, score.point), end=" ") score = score.stdlink print() except IndexError: print("student_id or subject_id is wrong.") return c = Class(students, subjects) scores = { 0: [90, 80], 1: [70, 90], 2: [60, 75], } for k, v in scores.items(): for i, score in enumerate(v): c.add(k, i, score) for id in range(len(students)): c.print_score(id)
動作確認
それでは上記で作成したスクリプトを実行してみます。
> python multi_list.py foo : english=>80 math=>90 bar : english=>90 math=>70 hoge : english=>75 math=>60
データの登録および参照などの操作が非常に簡単にできます。