Multimap を Rust でも使う（と、クレートの選び方）

先日仕事で、Rust を使用してとあるアプリケーションを作っていたところ、Guava の Multimap のようなデータ構造がほしいと思う場面がありました。

Guava の Multimap というのは、Java のライブラリ Guava に存在する HashMap の value 側がリストやベクタなどの複数要素を格納できる構造になっている Map です。具体的には下記のようなシグネチャなのですが、値側の実体はベクタとして管理される（つまり実質、HashMap<String, List<String>>）というものです。詳しいチュートリアルはこちらにあり、下記では Java コードをこの記事より引用させていただいております。

String key = "a-key";
Multimap<String, String> map = ArrayListMultimap.create();

map.put(key, "firstValue");
map.put(key, "secondValue");

// この時点で、{key, ["firstValue", "secondValue"]} という感じのマップができあがっている。

assertEquals(2, map.size());

Rust ではクレートを探すとだいたいのものはすでに誰かが作ってくれています。ということで、探してみました。「multimap」という名前では複数件該当しましたが、下記のクレートがよさそうに感じました。

github.com

この記事は Multimap の紹介ではあるものの、クレートを普段どう選んでいるかを少しメモしておく記事にもしておきたいと思っています。参考になれば幸いです。

私的クレートの選び方
Multimap を使ってみる
まとめ

私的クレートの選び方

さて、クレートを選ぶときに少し迷うのが、「ではこのクレートの評判はどうなのか」という点でしょう。クレートの評判を決める基準は今のところほぼないと思いますが、私は次のような点を見ながら使用を検討するテーブルにあげるかどうかを決めています。

GitHub のスター数
crates.io でのダウンロード数
どういう人（たち）が作っているか
README や doc を読んで使い方がイメージできるか

GitHub のスター数は少し迷う水準でした。24スターだったためです。スターはたしかに安心材料あるいは不安材料になり得ます。Rust を使っているときは、個人的には100件以上のスターがついていると少し安心できる感があります。

一方で、crates.io でのダウンロード数はかなりの数がありますね。2021年3月26日時点では 3,528,280 件のダウンロードが確認できます。GitHub のスターこそ少ないものの、かなり幅広いユーザーに使われてきた「枯れた」クレートなのだと判断できました。

Rust ではこのように、GitHub のスター数は多くはないものの、Rust ユーザーにはかなり多く使われているクレートが存在するように思います。

今回は確認しませんでしたが、作者を見に行くこともあります。私は、Organization で管理されているクレートはより優先して使いたいと思います。会社単位や組織単位で管理されているクレートは、長続きしそうな感じがするからです。作者を確認しに行く気持ちは、食料品をスーパーで買うときに、生産者の顔が見えると安心感を覚えるあれに近いと思います。

doc を読んで使い方がイメージできないものは、詰まったときにいろいろ困ってしまいます。他に代替のクレートが存在した場合には、doc に example がなく使い方がイメージできないものは切ってしまうことがあります。

README などを読む限りでは、私が使いたいと思っていた機能がおおよそ揃っていそうで使いたかったので、最後の決め手として実装を読んで判断しようと思いました。詳しくは書きませんが、実装を読んだ限り非常にシンプルに HashMap をラップした実装で、これなら安心して使えそうと思い使用の判断に至りました。

みなさんはどう選んでいますか？

Multimap を使ってみる

ようやく本題に入るわけですが、Multimap を使ってみましょう。実際にアプリケーションに書いたコードはお見せできませんが、別の例で使い方を見ていきたいと思います。

ベクタから MultiMap を作る

今回の題材は通貨間の価格を記録するものとします。USD/JPY や JPY/USD の値を保持しているベクタが存在しており、そのベクタは順不同で CurrencyRate というデータをもっているものとします。最終的には、通貨ペア CurrencyPair をキーとし、値にレート CurrencyRate.rate のベクタをもつ MultiMap が生成されることを想定しています。

コードは次のようになります。

#![allow(dead_code)]

use chrono::{DateTime, Utc};
use multimap::MultiMap;

#[derive(PartialEq, Eq, Hash)]
enum CurrencyKind {
    Usd,
    Jpy,
}

#[derive(PartialEq, Eq, Hash)]
struct CurrencyPair {
    base: CurrencyKind,
    quote: CurrencyKind,
}

impl CurrencyPair {
    fn usd_jpy() -> CurrencyPair {
        CurrencyPair {
            base: CurrencyKind::Usd,
            quote: CurrencyKind::Jpy,
        }
    }

    fn jpy_usd() -> CurrencyPair {
        CurrencyPair {
            base: CurrencyKind::Jpy,
            quote: CurrencyKind::Usd,
        }
    }
}

struct CurrencyRate {
    currency_pair: CurrencyPair,
    rate: f64,
    datetime: DateTime<Utc>,
}

impl CurrencyRate {
    fn usd_jpy(rate: f64) -> CurrencyRate {
        CurrencyRate {
            currency_pair: CurrencyPair::usd_jpy(),
            rate,
            datetime: Utc::now(),
        }
    }

    fn jpy_usd(rate: f64) -> CurrencyRate {
        CurrencyRate {
            currency_pair: CurrencyPair::jpy_usd(),
            rate,
            datetime: Utc::now(),
        }
    }
}

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);

    let jpy_usd = currency_rate_map.get_vec(&CurrencyPair::jpy_usd()).unwrap();
    assert_eq!(*jpy_usd, vec![0.0092, 0.0095, 0.0093]);
}

最終的には、

CurrencyPair { base: CurrencyKind::Usd, quote: CurrencyKind::Jpy } というキーに対しては [106.0, 106.3, 106.4] が入っている。
CurrencyPair { base: CurrencyKind::Jpy, quote: CurrencyKind::Usd } というキーに対しては [0.0092, 0.0095, 0.0093] が入っている。

という結果が得られます。

要素を追加する

要素を追加するにはマップの変数束縛を可変にし、insert メソッドを呼び出すことで可能です。値側の配列に値が追加されます。

// 先ほどの例から main 関数部分だけを抜き出した

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let mut currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);

    let jpy_usd = currency_rate_map.get_vec(&CurrencyPair::jpy_usd()).unwrap();
    assert_eq!(*jpy_usd, vec![0.0092, 0.0095, 0.0093]);

    // insert をしてみる
    currency_rate_map.insert(CurrencyPair::usd_jpy(), 110.0);
    let new_usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    // 110.0 という値をベクタに追加できていることがわかる
    assert_eq!(*new_usd_jpy, vec![106.0, 106.3, 106.4, 110.0]);
}

insert_many_from_slice メソッドを呼び出すとスライスをごそっと追加することもできます。

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let mut currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);

    let jpy_usd = currency_rate_map.get_vec(&CurrencyPair::jpy_usd()).unwrap();
    assert_eq!(*jpy_usd, vec![0.0092, 0.0095, 0.0093]);

    // スライスをごそっと追加する
    currency_rate_map
        .insert_many_from_slice(CurrencyPair::usd_jpy(), &[110.0, 110.2, 110.3, 110.4]);
    let new_usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();

    // スライスで追加した分が末尾に増えている
    assert_eq!(
        *new_usd_jpy,
        vec![106.0, 106.3, 106.4, 110.0, 110.2, 110.3, 110.4]
    );
}

要素を取得する

get をすると、キーに該当する配列から最初の値への参照だけを取得することができます。ここは少し注意が必要かもしれません。

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get(&CurrencyPair::usd_jpy()).unwrap();
    // キーに対応する値のベクタの先頭を取得する
    assert_eq!(*usd_jpy, 106.0);
}

MultiMap を使用する場合、キーで値のベクタを全部引けると嬉しいはずです。これは先ほどから紹介しておりますが、get_vec というメソッドで取得できます。

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);
}

可変な参照を取得したい場合には、HashMap と同様に get_mut がある他、get_vec_mut もあります。

Entry → orInsert

HashMap にある entry と or_insert のベクタ版も存在します。これは、値が1つもなかったらデフォルト値を設定する操作をするメソッドです。

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let mut currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);

    currency_rate_map
        .entry(CurrencyPair::usd_jpy())
        .or_insert_vec(vec![0.0, 999.9]);

    // 今回はすでに値が入っており、0と999.9が入ることはない。
    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);
}

なぜイテレータから、いろいろ複雑そうな Multimap にスッと復元できるのか

下記のコードは見慣れない方もいたかもしれません。

let base_currency_rate: MultiMap<CurrencyKind, f64> = mixed_currency_chart
        .into_iter()
        .map(|elem| (elem.base_currency_kind, elem.rate))
        .collect();

なぜ Vec からイテレータを取り出し、それを MultiMap に的確に collect できるのでしょうか？

その答えは FromIterator というトレイトにあります*1。MultiMap 用に用意された実装の中で、MultiMap への詰め直し作業を行っています。

impl<K, V, S> FromIterator<(K, V)> for MultiMap<K, V, S>
    where K: Eq + Hash,
          S: BuildHasher + Default
{
    fn from_iter<T: IntoIterator<Item = (K, V)>>(iterable: T) -> MultiMap<K, V, S> {
        let iter = iterable.into_iter();
        let hint = iter.size_hint().0;

        let mut multimap = MultiMap::with_capacity_and_hasher(hint, S::default());
        for (k, v) in iter {
            multimap.insert(k, v);
        }

        multimap
    }
}

MultiMap の insert メソッドは、通常の HashMap の insert メソッドとは異なります。Entry::Occupied と Entry::Vacant を用いて判定を行う点は共通していますが*2、その後は get_vec_mut や insert_vec といった MultiMap 固有のメソッドを呼び出しています。

    pub fn insert(&mut self, k: K, v: V) {
        match self.entry(k) {
            Entry::Occupied(mut entry) => {
                entry.get_vec_mut().push(v);
            }
            Entry::Vacant(entry) => {
                entry.insert_vec(vec![v]);
            }
        }
    }

これにより、下記のコードから MultiMap がきれいに生成できています。

let base_currency_rate: MultiMap<CurrencyKind, f64> = mixed_currency_chart
        .into_iter()
        .map(|elem| (elem.base_currency_kind, elem.rate))
        .collect();

ちなみに Vec から一度イテレータを取り出して map してキーと値のタプルを作り、それを collect するという技法は、Rust の標準ライブラリに用意されている HashMap でも使うことができます。

この記法を応用すると、読み取りさせたいだけの HashMap に可変性を与えることなくマップを生成できます。下記は HashMap に FromIterator<(K, V)> が実装されていることを利用した HashMap 生成のコードです。

let map: HashMap<i32, &str> = vec![(1, "one"), (2, "two"), (3, "three")].into_iter().collect();

まとめ

MultiMap を使うと、値にベクタをもつ構造をシンプルに表現できる上、挿入などの操作も大変楽に行える。

*1:FromIterator トレイトのドキュメント→https://doc.rust-lang.org/std/iter/trait.FromIterator.html

*2:この記事が詳しいです→RustのHashMapはentryが便利 https://keens.github.io/blog/2020/05/23/rustnohashmaphaentrygabenri/ 。ただし、この Entry は MultiMap 向けに独自に実装されているものです。

Don't Repeat Yourself

Don't Repeat Yourself (DRY) is a principle of software development aimed at reducing repetition of all kinds. -- wikipedia