[Rust] Vectorをuniqueしたい

検証環境

OS: macOS High Sierra 10.13.3
Rust: rustc 1.26.0-nightly (c08480fce 2018-03-23)

要素がプリミティブ型の場合

例えば、

let a = vec![1,2,3,1,2,3];

の重複削除したい。
HashSet を使えば簡単に実現できそう。

let uniq: HashSet<i32> = a.into_iter().collect();
println!("{:?}", uniq); // => {2, 3, 1}

要素がプリミティブな型じゃない場合

例えば、

struct Person {
    name: String,
    age: u32,
}

みたいなやつ
これをHashSetで扱おうとすると、そのままでは出来ない。

ドキュメントを読んでみると

As with the HashMap type, a HashSet requires that the elements implement the Eq and Hash traits.

と書いてある。
つまり、EqトレイトとHashトレイトを実装しろ。と。

This can frequently be achieved by using #[derive(PartialEq, Eq, Hash)].

とも、ちゃんと書いてある。
つまり、こうすればいいということですかね。
(最初、ここを見ずにそれぞれのトレイトを実装し、あとになって気づいた…)

#[derive(Debug, PartialEq, Eq, Hash)]
struct Person {
    name: String,
    age: u32,
}

※ Debug は関係ない

let people = vec![
    Person{name: "test1".into(), age: 10 },
    Person{name: "test2".into(), age: 20 },
    Person{name: "test3".into(), age: 30 },
    Person{name: "test1".into(), age: 10 },
    Person{name: "test2".into(), age: 10 },
];

let uniq: HashSet<Person> = people.into_iter().collect();
println!("{:?}", uniq); // => {Person { name: "test2", age: 20 }, Person { name: "test2", age: 10 }, Person { name: "test3", age: 30 }, Person { name: "test1", age: 10 }}

という感じになる。

問題点

1個問題がある。
into_iter は move が発生する

let uniq: HashSet<Person> = people.into_iter().collect();
println!("{:?}", uniq);

println!("{:?}", people);

ってやると

  --> src/main.rs:44:22
   |
41 |     let uniq: HashSet<Person> = people.into_iter().collect();
   |                                 ------ value moved here
...
44 |     println!("{:?}", people);
   |                      ^^^^^^ value used here after move
   |
   = note: move occurs because `people` has type `std::vec::Vec<Person>`, which does not implement the `Copy` trait

コンパイルエラー。

あとからpeopleを使える方法を考えてみた。

まずは、愚直にcloneしてみよう。
PersonのderiveにCloneトレイトを追加する。

#[derive(Debug, PartialEq, Eq, Hash, Clone)]
struct Person {
    name: String,
    age: u32,
}

cloneしてみる

let uniq: HashSet<Person> = people
    .iter()
    .map(|x| x.clone())
    .collect();
println!("{:?}", uniq);

println!("{:?}", people);

コンパイルは通った。

ただ、これだと全部cloneするので無駄な気がする。
で、こうしてみた。

let uniq: HashSet<Person> = people
    .iter()
    .collect::<HashSet<&Person>>()
    .iter()
    .map(|x| (*x).clone())
    .collect();

こうすれば、参照のHashSetにしてからcloneするので、cloneの回数は減るのではないか、と。
(でも、これはこれで、やりたいことの割に複雑で、気持ちよくない)

ベンチマーク

前者と後者でベンチマークを取ってみた

#[cfg(test)]
mod tests {
    use super::*;
    use test::Bencher;

    #[bench]
    fn all_clone(b: &mut Bencher) {
        let people = vec![
            Person{name: "test1".into(), age: 10 },
            Person{name: "test2".into(), age: 20 },
            Person{name: "test3".into(), age: 30 },
            Person{name: "test1".into(), age: 10 },
            Person{name: "test2".into(), age: 10 },
        ];
        b.iter(||{
            let uniq: HashSet<Person> = people
                .iter()
                .map(|x| x.clone())
                .collect();
        });
    }

    #[bench]
    fn tmp_hashset_clone(b: &mut Bencher) {
        let people = vec![
            Person{name: "test1".into(), age: 10 },
            Person{name: "test2".into(), age: 20 },
            Person{name: "test3".into(), age: 30 },
            Person{name: "test1".into(), age: 10 },
            Person{name: "test2".into(), age: 10 },
        ];
        b.iter(||{
            let uniq: HashSet<Person> = people
                .iter()
                .collect::<HashSet<&Person>>()
                .iter()
                .map(|x| (*x).clone())
                .collect();
        });
    }
}

test tests::all_clone         ... bench:         565 ns/iter (+/- 15)
test tests::tmp_hashset_clone ... bench:         762 ns/iter (+/- 45)

全部cloneしない方が速いという予測はハズレでした。
後者の方が遅い。
なるほど…

まとめ

• Vec -> HashSetにすれば、重複は除去できる
• 元のVectorの所有権を維持したまま、重複を削除した別の集合を作るスマートな方法はどうするのがいいのだろうか
  • 未解決