search
LoginSignup
10
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

posted at

[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の所有権を維持したまま、重複を削除した別の集合を作るスマートな方法はどうするのがいいのだろうか
    • 未解決

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
What you can do with signing up
10
Help us understand the problem. What are the problem?