Engineering Note

プログラミングなどの技術的なメモ

多重リスト構造 (Pythonによるアルゴリズムとデータ構造)

multi

本記事は、ソフトバンクパブリッシングから発行されている「定本 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

 

データの登録および参照などの操作が非常に簡単にできます。

 

参考書籍

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)