为什么我的 Rust 代码对于稍大的值突然几乎冻结？

Question

我正在制作一个有趣的程序来寻找方块的幻方。我有 9 个嵌套的

for_each

循环，对应于正方形的每个 3x3 数字。我使用常量 LIMIT 来设置 SQUARE_NUMBERS 中有多少个平方数。

当 LIMIT 增加到超过 100 时，它开始稍微减慢。一直到 297，它都会稍微减慢，但是一旦 LIMIT 达到 298，它就会突然减慢，当我登录内部循环时，变量

fifth

只是缓慢递增。对于极限 <=297 this program takes at most 23 seconds on my laptop, but LIMIT = 298 I have let run for hours and it hasn't finished.

这是怎么回事？我想知道如果 LIMIT 为 298，所有嵌套循环是否都会导致某种优化无法发生，但如果 LIMIT 为 297，则不会发生。

main.rs

mod square;

use std::{collections::HashMap, process::exit, time::Instant};

use rayon::prelude::*;
use square::{numbers_are_unique, numbers_make_sum, sums_are_equal};

const fn generate_square_numbers<const COUNT: usize>() -> [usize; COUNT] {
    let mut numbers: [usize; COUNT] = [0usize; COUNT];

    let mut counter: usize = 0;
    while counter < COUNT {
        numbers[counter] = (counter + 1) * (counter + 1);
        counter += 1;
    }

    numbers
}

fn get_most_frequent_total(square_numbers: &[usize]) -> usize {
    let total_iterations: usize = square_numbers.len().pow(3);
    let mut current_iteration: usize = 0;

    let mut totals_and_counts: HashMap<usize, usize> = HashMap::new();

    for &first in square_numbers.iter() {
        for &second in square_numbers.iter() {
            for &third in square_numbers.iter() {
                let total: usize = first + second + third;

                *totals_and_counts.entry(total).or_insert(0) += 1;

                current_iteration += 1;
                let progress: f64 = (current_iteration as f64 / total_iterations as f64) * 100.0;

                if current_iteration % (total_iterations / 1000) == 0 {
                    println!("Progress: {:.1}%", progress);
                }
            }
        }
    }

    let mut totals: Vec<(&usize, &usize)> = totals_and_counts.iter().collect();

    totals.sort_by(|a: &(&usize, &usize), b: &(&usize, &usize)| a.1.cmp(b.1));

    totals.last().map(|(&total, _)| total).unwrap()
}

fn main() {
    let start_time: Instant = Instant::now();

    const LIMIT: usize = 297; // this runs just fine with any value <=297
    const SQUARE_NUMBERS: [usize; LIMIT] = generate_square_numbers();

    let most_frequent_total: usize = get_most_frequent_total(&SQUARE_NUMBERS);

    println!("The most frequent total is {most_frequent_total}.");

    SQUARE_NUMBERS.iter().for_each(|first: &usize| {
        SQUARE_NUMBERS.par_iter().for_each(|second: &usize| {
            SQUARE_NUMBERS.iter().for_each(|third: &usize| {
                SQUARE_NUMBERS.iter().for_each(|fourth: &usize| {
                    SQUARE_NUMBERS.iter().for_each(|fifth: &usize| {
                        SQUARE_NUMBERS.iter().for_each(|sixth: &usize| {
                            SQUARE_NUMBERS.iter().for_each(|seventh: &usize| {
                                SQUARE_NUMBERS.iter().for_each(|eighth: &usize| {
                                    SQUARE_NUMBERS.iter().for_each(|ninth: &usize| {
                                        if numbers_make_sum(
                                            *first,
                                            *second,
                                            *third,
                                            *fourth,
                                            *fifth,
                                            *sixth,
                                            *seventh,
                                            *eighth,
                                            *ninth,
                                            most_frequent_total,
                                        ) && sums_are_equal(
                                            *first, *second, *third, *fourth, *fifth, *sixth,
                                            *seventh, *eighth, *ninth,
                                        ) && numbers_are_unique(
                                            *first, *second, *third, *fourth, *fifth, *sixth,
                                            *seventh, *eighth, *ninth,
                                        ) {
                                            println!(
                                                "{:?}",
                                                [
                                                    first, second, third, fourth, fifth, sixth,
                                                    seventh, eighth, ninth
                                                ]
                                            );
                                            exit(0);
                                        }
                                    });
                                });
                            });
                        });
                    });
                });
            });
        });
        println!("{} / {}", (*first as f32).sqrt(), LIMIT);
    });

    let end_time: Instant = Instant::now();

    println!("Elapsed time: {:?}", end_time - start_time);
}

square.rs

#[inline(always)]
pub(crate) fn numbers_make_sum(
    first: usize,
    second: usize,
    third: usize,
    fourth: usize,
    fifth: usize,
    sixth: usize,
    seventh: usize,
    eighth: usize,
    ninth: usize,
    sum: usize,
) -> bool {
    if first + second + third != sum {
        return false;
    }
    if fourth + fifth + sixth != sum {
        return false;
    }
    if seventh + eighth + ninth != sum {
        return false;
    }

    if first + fourth + seventh != sum {
        return false;
    }
    if second + fifth + eighth != sum {
        return false;
    }
    if third + sixth + ninth != sum {
        return false;
    }

    if first + fifth + ninth != sum {
        return false;
    }
    if third + fifth + seventh != sum {
        return false;
    }

    true
}

#[inline(always)]
pub(crate) fn numbers_are_unique(
    first: usize,
    second: usize,
    third: usize,
    fourth: usize,
    fifth: usize,
    sixth: usize,
    seventh: usize,
    eighth: usize,
    ninth: usize,
) -> bool {
    first != second
        && first != third
        && first != fourth
        && first != fifth
        && first != sixth
        && first != seventh
        && first != eighth
        && first != ninth
        && second != third
        && second != fourth
        && second != fifth
        && second != sixth
        && second != seventh
        && second != eighth
        && second != ninth
        && third != fourth
        && third != fifth
        && third != sixth
        && third != seventh
        && third != eighth
        && third != ninth
        && fourth != fifth
        && fourth != sixth
        && fourth != seventh
        && fourth != eighth
        && fourth != ninth
        && fifth != sixth
        && fifth != seventh
        && fifth != eighth
        && fifth != ninth
        && sixth != seventh
        && sixth != eighth
        && sixth != ninth
        && seventh != eighth
        && seventh != ninth
        && eighth != ninth
}

#[inline(always)]
pub(crate) fn sums_are_equal(
    first: usize,
    second: usize,
    third: usize,
    fourth: usize,
    fifth: usize,
    sixth: usize,
    seventh: usize,
    eighth: usize,
    ninth: usize,
) -> bool {
    if (first + second + third) != (fourth + fifth + sixth)
        || (fourth + fifth + sixth) != (seventh + eighth + ninth)
    {
        return false;
    }

    if (seventh + eighth + ninth) != (first + fourth + seventh)
        || (first + fourth + seventh) != (second + fifth + eighth)
        || (second + fifth + eighth) != (third + sixth + ninth)
    {
        return false;
    }

    (third + sixth + ninth) == (first + fifth + ninth)
        && (first + fifth + ninth) == (seventh + fifth + third)
}

Answer 1

我有 9 个嵌套的 for_each 循环

这就是您的问题的原因。这么多嵌套的 for 循环绝对是荒谬。 为了使该程序正常运行，您需要扁平化算法的结构，以减少其正在执行的总体工作量。

即使是中等大小的数字，O(n^9) 也永远无法完成。

您将需要研究如何在进行计算时挑选所采取的路径。