Rustで正直原因不明なStackOverFlowが発生する（曖昧でごめんなさい。遺伝的アルゴリズム用のTraitを作り、試している際に発生しました）

下記のコードにおいて、mainでstack overflowが発生します。

dna_lenやgroup_sizeが2のときでも発生しているので、原因究明が難しく、next_generation()内のcrossover()で発生してそうということしかつかめませんでした。

曖昧ですが、考えられそうなエラー原因はありますか？

lib.rs

rust
1pub mod genetic_algorithm_traits {
2    extern crate rand;
3
4    use rand::Rng;
5
6    pub trait Gene<T: Ord> {
7        fn cross_prob(&self) -> f64;
8        fn mutate_prob(&self) -> f64;
9        fn eval(&self) -> T;
10        fn crossover(&self, rhs: &Self, rng: &mut impl Rng) -> Self;
11        fn mutate(&mut self, rng: &mut impl Rng);
12    }
13
14    pub trait Group {
15        fn select(&self, rng: &mut impl Rng) -> Self;
16        fn next_generation(&self, rng: &mut impl Rng) -> Self;
17    }
18}

main.rs

rust
1extern crate genetic_algorithm;
2use genetic_algorithm::genetic_algorithm_traits::{Gene, Group};
3use rand::prelude::{SliceRandom, StdRng};
4use rand::{Rng, SeedableRng};
5use std::iter::FromIterator;
6
7#[derive(Clone, Debug)]
8pub struct DnaVec {
9    dna: Vec<i8>,
10}
11
12impl FromIterator<i8> for DnaVec {
13    fn from_iter<T: IntoIterator<Item = i8>>(iter: T) -> Self {
14        iter.into_iter().collect()
15    }
16}
17
18impl Gene<isize> for DnaVec {
19    fn cross_prob(&self) -> f64 {
20        0.75
21    }
22
23    fn mutate_prob(&self) -> f64 {
24        0.005
25    }
26
27    fn eval(&self) -> isize {
28        let mut a = 0isize;
29        for &d in &self.dna {
30            a += d as isize;
31        }
32        a
33    }
34
35    fn crossover(&self, rhs: &Self, rng: &mut impl Rng) -> Self {
36        if rng.gen::<f64>() < self.cross_prob() {
37            let len = self.dna.len();
38            let i = rng.gen_range(0, len - 1);
39            let j = rng.gen_range(i + 1, len);
40
41            self.dna
42                .iter()
43                .zip(rhs.dna.iter())
44                .enumerate()
45                .map(|(index, (&a, &b))| {
46                    if index < i {
47                        a
48                    } else if index < j {
49                        b
50                    } else {
51                        b
52                    }
53                })
54                .collect()
55        } else {
56            self.clone()
57        }
58    }
59
60    fn mutate(&mut self, rng: &mut impl Rng) {
61        let prob = self.mutate_prob();
62        for a in self.dna.iter_mut() {
63            if rng.gen::<f64>() < prob {
64                *a += rng.gen::<i8>()
65            }
66        }
67    }
68}
69
70pub struct Nums {
71    nums: Vec<DnaVec>,
72}
73
74impl FromIterator<DnaVec> for Nums {
75    fn from_iter<T: IntoIterator<Item = DnaVec>>(iter: T) -> Self {
76        iter.into_iter().collect()
77    }
78}
79
80impl Group for Nums {
81    fn select(&self, rng: &mut impl Rng) -> Self {
82        let tournament_size = 3;
83        let n = self.nums.len();
84
85        (0..n)
86            .map(|_| {
87                self.nums
88                    .choose_multiple(rng, tournament_size)
89                    .max_by_key(|dna_vec| dna_vec.eval())
90                    .unwrap()
91                    .clone()
92            })
93            .collect()
94    }
95
96    fn next_generation(&self, rng: &mut impl Rng) -> Self {
97        let n = self.nums.len();
98        let mut a = self.nums.clone();
99        let b = a.split_off(n / 2);
100
101        let mut nums = a
102            .iter()
103            .zip(b.iter())
104            .flat_map(|(i, j)| vec![i.crossover(j, rng), j.crossover(i, rng)])
105            .collect::<Vec<_>>();
106
107        nums.iter_mut().for_each(|d| d.mutate(rng));
108
109        Self { nums }
110    }
111}
112
113fn main() {
114    let mut rng = StdRng::seed_from_u64(1000);
115
116    let dna_len = 2;
117    let group_amount = 2;
118
119    let mut nums = Vec::with_capacity(group_amount);
120    for _ in 0..group_amount {
121        let mut dna = Vec::with_capacity(dna_len);
122        for _ in 0..dna_len {
123            dna.push(rng.gen::<i8>())
124        }
125        nums.push(DnaVec { dna });
126    }
127
128    let mut group = Nums { nums };
129
130    for generation in 0..100 {
131        let top = group.nums.iter().max_by_key(|d| d.eval()).unwrap();
132        println!(
133            "generation: {} score: {} {:?}",
134            generation,
135            top.eval(),
136            top.dna
137        );
138
139        group = group.next_generation(&mut rng);
140    }
141}

行動規範の内容に同意します

回答1件

ベストアンサー

TL;DR:
DnaVecに対するFromIterator<i8>の実装が原因です。
実装を以下のように直せば解決します。

impl FromIterator<i8> for DnaVec {
    fn from_iter<T: IntoIterator<Item = i8>>(iter: T) -> Self {
        Self {
            dna: iter.into_iter().collect(),
        }
    }
}

提示されたコードにおいて、DnaVecに対するFromIterator<i8>の実装は以下のようになされています。

impl FromIterator<i8> for DnaVec {
    fn from_iter<T: IntoIterator<Item = i8>>(iter: T) -> Self {
        iter.into_iter().collect()
    }
}

ところで、Iterator::collectの実装は以下のようになっています。

fn collect<B: FromIterator<Self::Item>>(self) -> B
where
    Self: Sized,
{
    FromIterator::from_iter(self)
}

この2つから考えると、あなたの実装は以下のような機構と同じ動作をしています。

impl FromIterator<i8> for DnaVec {
    fn from_iter<T: IntoIterator<Item = i8>>(iter: T) -> Self {
        FromIterator::from_iter(iter.into_iter())
    }
}

これは無限再帰になるため、スタックオーバーフローを引き起こします。

コードから少し離れて、より概念的に説明します。
FromIteratorは「ある型のオブジェクトをイテレータから作るためのメソッドfrom_iterを提供する」トレイトです。
Iterator::collectは「ある型のオブジェクトをイテレータから生成する」メソッドです。
つまり、Iterator::collectはFromIterator::from_iterの糖衣構文のようなものなのです。
したがって、ある型TのFromIteratorの実装に際して、Tを返すようなcollectを使うことはできません。

今回のコードでは、Iterator<i8>を受け取って、Vec<i8>を内包する構造体を作りたいわけです。
それには以下のように、イテレータからVec<i8>を作って構造体を作るのがよいでしょう。

impl FromIterator<i8> for DnaVec {
    fn from_iter<T: IntoIterator<Item = i8>>(iter: T) -> Self {
        Self {
            dna: iter.into_iter().collect(),
        }
    }
}

投稿2020/07/30 16:35