LoginSignup
1
0
お題は不問！Qiita Engineer Festa 2024で記事投稿！
Qiita Engineer Festa20242024年7月17日まで開催中！
@namn1125(namnium)in株式会社ゆめみ

Rust 100 Ex 🏃【26/37】 HashMap・順序・BTreeMap ～Rustの辞書型～

Last updated at Posted at 2024-07-17

前の記事

全記事一覧

100 Exercise To Learn Rust 演習第26回になります。配列・イテレータ周りが多かった6章も今回が最後です！

今回の関連ページ

[06_ticket_management/15_hashmap] HashMap (いわゆる辞書型)

問題はこちらです。

lib.rs (長いのでTODO周辺のみ抜粋)
// TODO: Replace `todo!()`s with the correct implementation.
//  Implement additional traits on `TicketId` if needed.

use std::collections::HashMap;
use std::ops::{Index, IndexMut};
use ticket_fields::{TicketDescription, TicketTitle};

#[derive(Clone)]
pub struct TicketStore {
    tickets: HashMap<TicketId, Ticket>,
    counter: u64,
}

#[derive(Clone, Copy, Debug, PartialEq)]
pub struct TicketId(u64);

#[derive(Clone, Debug, PartialEq)]
pub struct Ticket {
    pub id: TicketId,
    pub title: TicketTitle,
    pub description: TicketDescription,
    pub status: Status,
}

// ...省略...

impl TicketStore {
    pub fn new() -> Self {
        Self {
            tickets: todo!(),
            counter: 0,
        }
    }

    pub fn add_ticket(&mut self, ticket: TicketDraft) -> TicketId {
        let id = TicketId(self.counter);
        self.counter += 1;
        let ticket = Ticket {
            id,
            title: ticket.title,
            description: ticket.description,
            status: Status::ToDo,
        };
        todo!();
        id
    }

    // Index<TicketId> for TicketStore に関わる
    pub fn get(&self, id: TicketId) -> Option<&Ticket> {
        todo!()
    }

    // IndexMut<TicketId> for TicketStore に関わる
    pub fn get_mut(&mut self, id: TicketId) -> Option<&mut Ticket> {
        todo!()
    }
}
テストを含めた全体
lib.rs
// TODO: Replace `todo!()`s with the correct implementation.
//  Implement additional traits on `TicketId` if needed.

use std::collections::HashMap;
use std::ops::{Index, IndexMut};
use ticket_fields::{TicketDescription, TicketTitle};

#[derive(Clone)]
pub struct TicketStore {
    tickets: HashMap<TicketId, Ticket>,
    counter: u64,
}

#[derive(Clone, Copy, Debug, PartialEq)]
pub struct TicketId(u64);

#[derive(Clone, Debug, PartialEq)]
pub struct Ticket {
    pub id: TicketId,
    pub title: TicketTitle,
    pub description: TicketDescription,
    pub status: Status,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TicketDraft {
    pub title: TicketTitle,
    pub description: TicketDescription,
}

#[derive(Clone, Debug, Copy, PartialEq, Eq)]
pub enum Status {
    ToDo,
    InProgress,
    Done,
}

impl TicketStore {
    pub fn new() -> Self {
        Self {
            tickets: todo!(),
            counter: 0,
        }
    }

    pub fn add_ticket(&mut self, ticket: TicketDraft) -> TicketId {
        let id = TicketId(self.counter);
        self.counter += 1;
        let ticket = Ticket {
            id,
            title: ticket.title,
            description: ticket.description,
            status: Status::ToDo,
        };
        todo!();
        id
    }

    pub fn get(&self, id: TicketId) -> Option<&Ticket> {
        todo!()
    }

    pub fn get_mut(&mut self, id: TicketId) -> Option<&mut Ticket> {
        todo!()
    }
}

impl Index<TicketId> for TicketStore {
    type Output = Ticket;

    fn index(&self, index: TicketId) -> &Self::Output {
        self.get(index).unwrap()
    }
}

impl Index<&TicketId> for TicketStore {
    type Output = Ticket;

    fn index(&self, index: &TicketId) -> &Self::Output {
        &self[*index]
    }
}

impl IndexMut<TicketId> for TicketStore {
    fn index_mut(&mut self, index: TicketId) -> &mut Self::Output {
        self.get_mut(index).unwrap()
    }
}

impl IndexMut<&TicketId> for TicketStore {
    fn index_mut(&mut self, index: &TicketId) -> &mut Self::Output {
        &mut self[*index]
    }
}

#[cfg(test)]
mod tests {
    use crate::{Status, TicketDraft, TicketStore};
    use ticket_fields::test_helpers::{ticket_description, ticket_title};

    #[test]
    fn works() {
        let mut store = TicketStore::new();

        let draft = TicketDraft {
            title: ticket_title(),
            description: ticket_description(),
        };
        let id = store.add_ticket(draft.clone());
        let ticket = &store[id];
        assert_eq!(draft.title, ticket.title);
        assert_eq!(draft.description, ticket.description);
        assert_eq!(ticket.status, Status::ToDo);

        let ticket = &mut store[id];
        ticket.status = Status::InProgress;

        let ticket = &store[id];
        assert_eq!(ticket.status, Status::InProgress);
    }
}

TicketStore の定義部に今回の問題要旨が詰まっています。

Rust
#[derive(Clone)]
pub struct TicketStore {
    tickets: HashMap<TicketId, Ticket>,
    counter: u64,
}

Ticket を保存しておくフィールド tickets が Vec<Ticket> から HashMap<TicketId, Ticket> に変わっています！

前々回 にて「 O(N) アクセスになっている件は次回以降の話題」と話しましたが、今回がその話題になります。ハッシュテーブル を用いることで、 tickets へのアクセス(理想)時間計算量を O(1) にしましょう！

解説

改変するところが多いですが、難しい部分はないです。 TicketId には Eq トレイト及び Hash トレイトを実装する必要があるため、その記述の追加と、その他は HashMap に存在するメソッドに既存の実装を差し替える形になります。

lib.rs (超抜粋)
+ use std::hash::Hash;

- #[derive(Clone, Copy, Debug, PartialEq)]
+ #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct TicketId(u64);

// 以降は todo!() 埋め

impl TicketStore {
    pub fn new() -> Self {
        Self {
            tickets: HashMap::new(),
            counter: 0,
        }
    }

    pub fn add_ticket(&mut self, ticket: TicketDraft) -> TicketId {
        let id = TicketId(self.counter);
        self.counter += 1;
        let ticket = Ticket {
            id,
            title: ticket.title,
            description: ticket.description,
            status: Status::ToDo,
        };
        self.tickets.insert(id, ticket);
        id
    }

    pub fn get(&self, id: TicketId) -> Option<&Ticket> {
        self.tickets.get(&id)
    }

    pub fn get_mut(&mut self, id: TicketId) -> Option<&mut Ticket> {
        self.tickets.get_mut(&id)
    }
}

Eq トレイトは、語弊を恐れずに言うと(マサカリ要素)、「 a == b なら b == a が成り立つ」、みたいな、 PartialEq の実装が直感に反しないものになっていること1を保証するよ、というマーカートレイトです。 Hash トレイト は今回の場合 TicketId を何かしらのハッシュ関数に掛けられることを示します。この両トレイトを実装していないと、ハッシュテーブルのキーとなる型になる資格はありません！ハッシュテーブルの仕組みを考えると当然に見えますね。

そしてこの両トレイトを意図通り実装していても多分抜ける HashMap のキーの必要条件に「要素が『等しい』なら、ハッシュ同士を比較しても『等し』くなければならない」というものがあります2。まぁ Eq トレイトを要求している時点で「変な実装はするなよ」という牽制になっているでしょうから気にする必要はないかもしれませんが、例えば「比較に際して構造体が持つ特定のフィールドを無視する」といったことをすると(それでも対称律等は守られるはずです。)、ハッシュの実装にて全フィールドを見るようにしてしまっている場合結果に不整合が出ることになります。こういったヘンテコな実装が必要な場合、 PartialEq の手動実装と Hash の手動実装は不整合が起きないように気を配る必要がありそうです。

[06_ticket_management/16_btreemap] 順序・BTreeMap (順序付き辞書型)

問題はこちらです。

lib.rs (重要な部分のみ抜粋)
// TODO: Replace `todo!()`s with the correct implementation.
//  Implement `IntoIterator` for `&TicketStore`. The iterator should yield immutable
//  references to the tickets, ordered by their `TicketId`.
//  Implement additional traits on `TicketId` if needed.

use std::collections::BTreeMap;
use std::ops::{Index, IndexMut};
use ticket_fields::{TicketDescription, TicketTitle};

#[derive(Clone)]
pub struct TicketStore {
    tickets: BTreeMap<TicketId, Ticket>,
    counter: u64,
}

// ...省略...

#[cfg(test)]
mod tests {
    use crate::{Status, TicketDraft, TicketId, TicketStore};
    use ticket_fields::test_helpers::{ticket_description, ticket_title};

    #[test]
    fn works() {
        // ...省略...

        let ids: Vec<TicketId> = (&store).into_iter().map(|t| t.id).collect();
        let sorted_ids = {
            let mut v = ids.clone();
            v.sort();
            v
        };
        assert_eq!(ids, sorted_ids);
    }
}
問題ソースコード全体
lib.rs
// TODO: Replace `todo!()`s with the correct implementation.
//  Implement `IntoIterator` for `&TicketStore`. The iterator should yield immutable
//  references to the tickets, ordered by their `TicketId`.
//  Implement additional traits on `TicketId` if needed.

use std::collections::BTreeMap;
use std::ops::{Index, IndexMut};
use ticket_fields::{TicketDescription, TicketTitle};

#[derive(Clone)]
pub struct TicketStore {
    tickets: BTreeMap<TicketId, Ticket>,
    counter: u64,
}

#[derive(Clone, Copy, Debug, PartialEq)]
pub struct TicketId(u64);

#[derive(Clone, Debug, PartialEq)]
pub struct Ticket {
    pub id: TicketId,
    pub title: TicketTitle,
    pub description: TicketDescription,
    pub status: Status,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TicketDraft {
    pub title: TicketTitle,
    pub description: TicketDescription,
}

#[derive(Clone, Debug, Copy, PartialEq, Eq)]
pub enum Status {
    ToDo,
    InProgress,
    Done,
}

impl TicketStore {
    pub fn new() -> Self {
        Self {
            tickets: todo!(),
            counter: 0,
        }
    }

    pub fn add_ticket(&mut self, ticket: TicketDraft) -> TicketId {
        let id = TicketId(self.counter);
        self.counter += 1;
        let ticket = Ticket {
            id,
            title: ticket.title,
            description: ticket.description,
            status: Status::ToDo,
        };
        todo!();
        id
    }

    pub fn get(&self, id: TicketId) -> Option<&Ticket> {
        todo!()
    }

    pub fn get_mut(&mut self, id: TicketId) -> Option<&mut Ticket> {
        todo!()
    }
}

impl Index<TicketId> for TicketStore {
    type Output = Ticket;

    fn index(&self, index: TicketId) -> &Self::Output {
        self.get(index).unwrap()
    }
}

impl Index<&TicketId> for TicketStore {
    type Output = Ticket;

    fn index(&self, index: &TicketId) -> &Self::Output {
        &self[*index]
    }
}

impl IndexMut<TicketId> for TicketStore {
    fn index_mut(&mut self, index: TicketId) -> &mut Self::Output {
        self.get_mut(index).unwrap()
    }
}

impl IndexMut<&TicketId> for TicketStore {
    fn index_mut(&mut self, index: &TicketId) -> &mut Self::Output {
        &mut self[*index]
    }
}

#[cfg(test)]
mod tests {
    use crate::{Status, TicketDraft, TicketId, TicketStore};
    use ticket_fields::test_helpers::{ticket_description, ticket_title};

    #[test]
    fn works() {
        let mut store = TicketStore::new();

        let n_tickets = 5;

        for i in 0..n_tickets {
            let draft = TicketDraft {
                title: ticket_title(),
                description: ticket_description(),
            };
            let id = store.add_ticket(draft.clone());
            let ticket = &store[id];
            assert_eq!(draft.title, ticket.title);
            assert_eq!(draft.description, ticket.description);
            assert_eq!(ticket.status, Status::ToDo);

            let ticket = &mut store[id];
            ticket.status = Status::InProgress;

            let ticket = &store[id];
            assert_eq!(ticket.status, Status::InProgress);
        }

        let ids: Vec<TicketId> = (&store).into_iter().map(|t| t.id).collect();
        let sorted_ids = {
            let mut v = ids.clone();
            v.sort();
            v
        };
        assert_eq!(ids, sorted_ids);
    }
}

先程は HashMap にしていた部分を BTreeMap (B木3式のマップ) に差し替えた問題となっています！

Rust
#[derive(Clone)]
pub struct TicketStore {
    tickets: BTreeMap<TicketId, Ticket>,
    counter: u64,
}

解説

先程の問題とほぼ同じです！ TicketId に対して Hash の代わりに PartialOrd, Ord を付ける点と、 IntoIterator トレイトを実装している点が異なります。

lib.rs
- #[derive(Clone, Copy, Debug, PartialEq)]
+ #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct TicketId(u64);

// HashMap のエクササイズと同様の改変を加えた上で、更にIntoIteratorについて

use std::array::IntoIter;

impl<'a> IntoIterator for &'a TicketStore {
    type Item = &'a Ticket;
    type IntoIter = Values<'a, TicketId, Ticket>;

    fn into_iter(self) -> Self::IntoIter {
        self.tickets.values()
    }
}

二分探索等で要素にアクセスするようになるがゆえに、ハッシュ値を取らないため Hash がなくなっています。平均アクセス時間計算量が O(1) からは離れましたが、順番を維持したまま要素を保存し、かつ高速にアクセスできるということで配列とハッシュテーブルの良いとこ取りになっていますね！ HashMap と合わせて使いこなせるようになりたいデータ構造です。

では次の問題に行きましょう！

次の記事: 【27】 スレッド・'staticライフタイム ～並列処理に見るRustの恩恵～

  1. 本来なら数学の二項関係とかの話をするべきなのかもしれませんが、正直「数学的な関係を満たしている」というのもそれはそれで誤りな理解な気がしていて、あえて「直感に反しない」という表現にしました。マサカリはコメント欄へ ↩

  2. 筆者はbookを誤読していましたが、逆(ハッシュが同一でも全体は等しくない)は別に問題ないようです。 ↩

  3. 競プロ雑魚なので間違った理解をしているかもしれませんが、二分探索とかがしやすい木と認識していました。 ↩

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0