LinkedList(PythonとRustで比較)

LinkedListというデータ構造

LinkedListというデータ構造が分子動力学計算の書籍で表れてたので、色々調べて見ました。
本記事ではpythonとrustでlinkedListというデータ構造を実装してみたいと思います。
pythonでは楽だったのですが、rustだと結構しんどかったでｺﾞﾜｽ

そもそもLinkedListとは？

出てくる概念

• Node
  • property
    • value:ノードが保持する値
    • next:次のノードへの参照
  • method
    • change_next:自身のノードが参照しているノードを別のノードへ切り替える
• List
  • property
    • head:リストの先頭ノードへの参照
    • tail:リストの最後尾ノードへの参照
  • method
    • new:インスタンス作成
    • push:先頭にノードを追加
    • pop:最後尾からノードを取り出す
    • remove:特定のノードを削除
    • add:最後尾にノードを追加

概念図

Nodeはプロパティにvalueと次のノードへの参照を持ちます。もし次のノードへの参照がなければ、Noneを参照することとなります。またノード自身のメソッドとして、change_nextというメソッドを待たせます。これによってノードインスタンスがnextを自身のメソッドで変更できるようになります。

Listはプロパティにheadとtailを持ちます。いづれもノードを参照し、headは先頭ノード、tailは最後尾ノードを参照します。
methodはLinkedListに追加したり、削除したりのメソッドです。
削除方法なのですが、あるvalueが与えられたら、そのvalueを所有するノードを削除します。そのためには、削除したいノードの後ろのノードの参照先を削除したノードの後に参照させれば良いです。

pythonでの実装

ではpythonで実装してみましょう。

from typing import Any, Optional
class Node:
    def __init__(self, value: Any) -> None:
        self.value = value
        self.next: Optional[Node] = None

    def change_next(self, next_node: Optional['Node']) -> None:
        self.next = next_node

class LinkedList:
    def __init__(self) -> None:
        self.head: Optional[Node] = None
        self.tail: Optional[Node] = None
        self.size: int = 0

    # listの先頭に追加(例3を追加：[1,2] -> [3,12]
    def push(self, value: Any) -> None:
        new_node = Node(value) # valueを用いて、追加するノードのインスタンスを作成
        # self.headがNoneならlinkedlistは空なので、headもtailもNoneにする
        if self.head is None: 
            self.head = new_node
            self.tail = new_node
        else:
            # そうじゃないならnew_nodeの参照をchange_nextでheadのnodeにする
            # python場合、self.headが参照しているオブジェクト(ノード)が代入される
            new_node.change_next(self.head)
            # self.headを更新
            self.head = new_node
        self.size += 1
    #リストの先頭を取り出す
    def pop(self) -> Any:
        if self.head is None:
            raise IndexError('pop from empty linked list')
        # 先頭ノードの値を取り出す
        value = self.head.value
        # 先頭の参照を元の先頭の参照先のノードへ変更する
        self.head = self.head.next
        self.size -= 1
        return value
    # リストの最後尾に追加(pushと同じ)
    def add(self, value: Any) -> None:
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.change_next(new_node)
            self.tail = new_node
        self.size += 1
    # 特定のvalueを持つ要素を削除、リストの先頭から順にノードを見ていきます。
    def remove(self, value: Any) -> Optional[Any]:
        if self.head is None:
            return None
        if self.head.value == value:
            return self.pop()
        # self.headが参照しているノードを参照する
        current = self.head
        # 現在のノードの参照先ノードがNoneになるまでループさせる
        while current.next is not None:
            # 例外的に、現在ノードの隣のノードの値が,受け取ったvalueと一致する時の処理
            if current.next.value == value:
                # 現在ノードの隣のノードの値をvalue変数に代入
                value = current.next.value
                現在のノードの参照先を参照先の参照先に変更する
                current.change_next(current.next.next)
                self.size -= 1
                return value
            # ifでないなら、現在ノードをその参照先のノードに変更する
            current = current.next
        一つも該当するものがないなら、Noneを返す
        return None

    def __str__(self) -> str:
        vlaues = []
        current = self.head
        while current is not None:
            values.append(str(current.value))
            current = current.next
        return '[' + ', '.join(values) + ']'

    def __repr__(self) -> str:
        return self.__str__()

pythonでの実装は至ってシンプルです。コメントアウトで解説してあります。
pythonでの実装はrustと異なり、所有権などの概念がないため以下のような挙動になることを抑えておくと良いでしょう。

a = 2
b = a
a = 3
print(b)
print(a)

このようにbはaが参照しているオブジェクト2を参照することとなります。したがって、aを変更してもbはaを参照しているわけではないので、bの値は変化しません。

rustでの実装

rustでの実装は複雑です。hand over hand lockingというのも組み込んで実装してみています。完全にはhand over hand lockingではないのですが、ArcやMutexの使い方がわかれば良いと思います。

use std::sync::{Arc, Mutex, MutexGuard};
use std::mem::drop;
use std::mem;
use std::thread;

// Trait 要は Interfaceを定義します
pub trait ListTrait<T: std::fmt::Debug + Copy + PartialEq> {
    fn new() -> Self;
    fn push(&mut self, value: T);
    fn pop(&mut self) -> Option<T>;
    fn add(&mut self, value: T);
    fn remove(&mut self, value: T) -> bool;
}

// Nodeの構造体の定義
#[derive(Debug, Clone)]
struct Node<T: Copy + PartialEq> {
    value: T,
    next: Option<Arc<Mutex<Node<T>>>>
}

// Nodeが持つメソッドを定義
impl <T: Copy + PartialEq> Node<T> {
    fn new(value: T) -> Self {
        Node {
            value: value,
            next: None
        }
    }

    fn change_next(&mut self, next: Option<Arc<Mutex<Node<T>>>> ) {
        self.next = next;
    }
}

//Listの構造体を定義、ここではすべてのPropertyをArcとMutexで括ります
#[derive(Debug)]
pub struct List<T: std::fmt::Debug + Copy + PartialEq> {
    head: Option<Arc<Mutex<Node<T>>>>,
    tail: Option<Arc<Mutex<Node<T>>>>,
    size: Arc<Mutex<usize>>
}

// Listのtraitを実装、TはPartialEq Traitを実装している型。これによって、T型のオブジェクト同士の比較が可能
impl<T: std::fmt::Debug + Copy + PartialEq + std::fmt::Display> ListTrait<T> for List<T> {
    fn new() -> Self {
        List {
            head: None,
            tail: None,
            size: Arc::new(Mutex::new(0))
        }
    }

    fn push(&mut self, value: T) {
        //リストの先頭に追加するNodeを作ります
        let new_node = Arc::new(Mutex::new(Node {
            value,
            next: self.head.take(),
        })); //ここで一つnew_node参照
        // Arc::cloneでnew_nodeをcloneします。この時新たに作成されたノードをself.headも参照します。
        // Arcはこのように複数の参照を持つことができます。
        self.head = Some(Arc::clone(&new_node));
        // size変更用の処理です
        let size = self.size.clone();
        let mut size_guard = size.lock().unwrap();

        if *size_guard == 0 {
            self.tail = Some(Arc::clone(&new_node));
        }
        self.increase_size();
        // したに定義してあるincrease sizeメソッドを使います。traitは外部に公開することを前提に定義するものなので、trait実装部のメソッドにはpub fnなどの記述は必要ありません
        // traitを実装してないけど、内部だけで使用したいメソッドは下の方でimplしてあるpubのついていないメソッドを定義して、それをこの部分で使用しようしています。
    }

    fn pop(&mut self) -> Option<T> {
        let size = self.size.clone();
        let mut size_guard = size.lock().unwrap();
        if *size_guard == 0 {
            return None;
        }

        if *size_guard == 1 {
            self.tail = None;
        }

        match self.head.take() { // takeはunwrapと違って、self.headにNoneが入ります。unwrapはself.head自体が破棄されます。
            None => None,
            Some(old_head) => {
                self.head = old_head.lock().unwrap().next.clone(); // old_headをlockして, old_headのnextをclone()させてself.headに参照させる
                *size_guard -= 1;

                match Arc::try_unwrap(old_head) {
                    Ok(node) => Some(node.into_inner().unwrap().value),
                    Err(_arc) => None,
                }
            }
        }
    }

    fn add(&mut self, value: T) {
        let size = self.size.clone();
        let mut size_guard = size.lock().unwrap();

        let new_node = Arc::new(Mutex::new(Node {
            value,
            next: None,
        }));

        match self.tail.take() {
            // tailがないなら、size0と判断
            None => {
                self.head = Some(Arc::clone(&new_node));
                self.tail = Some(Arc::clone(&new_node));
            }
            Some(prev_tail) => {
                prev_tail.lock().unwrap().next = Some(Arc::clone(&new_node));
                self.tail = Some(Arc::clone(&new_node));
            }
        }
        *size_guard += 1;
    }

    // hand over hand lockingを実装してみた(改善の余地はある)
    fn remove(&mut self, value: T) -> bool {
        let size = self.size.clone();
        let mut size_guard = size.lock().unwrap();

        if *size_guard == 0 {
            return false;
        }

        if *size_guard == 1 {
            self.head = None;
            self.tail = None;
            *size_guard -= 1;
            return true
        }

        // ライフタイムを揃えるために先に、arcとguardをletで定義しておく
        let mut current_arc = self.head.clone();
        let mut next_arc = None;
        let mut current_node;
        let mut current_guard: MutexGuard<'_, Node<T>>;
        let mut next_guard = None;

        loop {
            // option外しして、current_nodeを取得
            // as_refをつけることでcurrent_arcを残して、current_nodeがOptionの中身を参照(補足：可変参照もしたい時はas_ref().as_mut()とかを使う)
            current_node = match current_arc.as_ref() {
                Some(node) => {
                    node
                }
                None => {
                    break;
                }
            };

            // ガードの入れ替え
            current_guard = current_node.lock().unwrap(); // 現在のノードをlock、next_guardがまだ残っているので待機状態
            drop(next_guard); //next_guardを破棄 -> unlock この瞬間にcurrent_guardによりガードされる
            drop(next_arc); // next_arcも破棄
            next_arc = current_guard.next.clone(); // 次のarcをcloneで取得
            next_guard = match next_arc.as_ref() { // next_arcはまだ使用するのでas_ref
                Some(node) => {
                    Some(node.lock().unwrap())
                }
                None => {
                    None
                }
            };

            if let Some(guard) = next_guard.as_ref() {

                if guard.value == value {
                    // next_arcとtailのポインタが一致するなら
                    if Arc::ptr_eq(next_arc.as_ref().unwrap(), self.tail.as_ref().unwrap()) {
                        self.tail = current_arc.clone();
                    }

                    (*current_guard).change_next(guard.next.clone());
                    *size_guard -= 1;
                    return true;
                }
            } else {
                break;
            }
            drop(current_guard); // dropによってガードを破棄する
            current_arc = next_arc.clone(); // cloneすることで新たにnext_arcのインスタンスを作る
        }
        false
    }
}

impl<T: std::fmt::Debug + Copy + PartialEq> List<T> {
    fn decrease_size(&mut self) {
        let size = self.size.clone();
        let mut size_guard = size.lock().unwrap();
        if *size_guard <= 0 {
            *size_guard = 0;
            return ();
        } else {
            *size_guard -= 1;
        }
    }

    fn increase_size(&mut self) {
        let size = self.size.clone();
        let mut size_guard = size.lock().unwrap();
        if *size_guard <= 0 {
            *size_guard = 0;
            return ();
        } else {
            *size_guard += 1;
        }
    }
}

fn main() {
    let shared_list = Arc::new(Mutex::new(List::<i32>::new()));

    let mut handles = vec![];

    for i in 0..3 {
        let list_clone = Arc::clone(&shared_list);

        let handle = thread::spawn(move || {
            let mut list = list_clone.lock().unwrap();

            list.add(i * 10);
            println!("Thread {}: Added {}", i, i * 10);
        });

        handles.push(handle);
    }

    {
        let list_clone = Arc::clone(&shared_list);

        let handle = thread::spawn(move || {
            let mut list = list_clone.lock().unwrap();

            let value_to_remove = 20;
            if list.remove(value_to_remove) {
                println!("Remove Thread: Removed {}", value_to_remove);
            } else {
                println!("Remove Thread: Value {} not found", value_to_remove);
            }
        });

        handles.push(handle);
    }

    for handle in handles {
        handle.join().unwrap();
    }

    let list = shared_list.lock().unwrap();
    println!("Final List: {:?}", *list);
}

ArcとMutexについて

• Arc
  • Arcは一つのデータの所有権を複数のインスタンスで共有できます
  • 複数threadで一つの変数を共有して使用したいとき
• Mutex
  • Mutexが排他ロックを提供するので、Arc<Mutex<...>> とすることで、あるデータを複数のインスタンスから安全に変更できます
  • これも複数スレッドから一つの変数にアクセスし、その変数に変更を加えるとき。あるthreadAが変数aに変更を加えるとき、別のthreadBが変更を加えようとすると変更に衝突が起きてしまいます。これを防ぐためにMutexという変数の変更をロックする仕組みがあります。

use std::sync::{Arc, Mutex, MutexGuard};
use std::mem::drop;

fn main() {
    let a = String::from("kurapika");
    let arc = Arc::new(Mutex::new(a));
    let arc2 = Arc::clone(&arc);
    let mut a_guard = arc.lock().unwrap();
    *a_guard = String::from("reorio");
    drop(a_guard); //　ガード破棄
    println!("{:?}", *arc2.lock().unwrap());
}

のように使用します。
図のremove
最初のremoveする時は、最初の図のようにする必要があるので以下のように実装しています。

            if let Some(guard) = next_guard.as_ref() {

                if guard.value == value {
                    // next_arcとtailのポインタが一致するなら
                    if Arc::ptr_eq(next_arc.as_ref().unwrap(), self.tail.as_ref().unwrap()) {
                        self.tail = current_arc.clone(); //基本的にarcはclone()を参照させるようにしています。removeメソッドの外に出ればどうせ余分なarcは破棄されるので
                    }

                    current_guard.next = guard.next.clone(); // guard.nextの参照を奪うことになるので、clone()
                    *size_guard -= 1;
                    return true;
                }
            } else {
                break;
            }

ここではcurrent_guardの次の参照先current_guard.nextを次のnodeのnextに向けます。current_guard.next = guard.next.clone();この部分です。

hand-over-hand-locking
以下の図のように必ずロックが残るようにして変更など加えていく手法です。
ただrustだとライフタイムや所有権がこの手法を実装しづらくしているため少し工夫が必要です。

どうやらrustではArc<Mutex<Node<T>>>のlockを取得した領域がguardのライフタイムとなるようです。(間違っていたら申し訳ない)なので、最初にライフタイムをそろえておきました。予めガードとarc変数の型をloop外で定義しておくことで、1ループ抜けた後でもガードのはきが起こらないようにしています。
しかし、以下のコードでnext_guardが破棄された瞬間にcurrent_guardによるガードが走るようになっているため、ほんの一瞬だけガードがなくなってしまいます。この辺はもっと上手いやり方や実装方法、crate(ライブラリのこと)があると思うので調べてみます。

            current_guard = current_node.lock().unwrap(); // 現在のノードをlock、next_guardがまだ残っているので待機状態
            drop(next_guard); //next_guardを破棄 -> unlock この瞬間にcurrent_guardによりガードされる
            drop(next_arc); // next_arcも破棄
            next_arc = current_guard.next.clone(); // 次のarcをcloneで取得

まとめ

LinkedListはその他の記事でもrustで実装されているので、参考にしてみると理解が深まると思います。rustではhand over hand lockingのようなことをしてみたのですが、完全なるhand over hand lockingにはなっていないように思えます。(できる限り、ガードが0の状態は防いであります。)もっと良い手法や実装方法があればご教授願いたいです。