4

我正在尝试使用并行化查找 BST 的直径：

extern crate rayon;

use std::cmp::Ordering::*;
use std::ops::Index;
use rayon::prelude::*;

#[derive(Debug)]
struct Node<K> {
    left: Option<Box<Node<K>>>,
    right: Option<Box<Node<K>>>,
    key: K,
}

impl<K> Node<K> {
    fn new(k: K) -> Node<K> {
        Node {
            left: None,
            right: None,
            key: k,
        }
    }
}

impl<K: Ord> Node<K> {
    fn insert(&mut self, n: Node<K>) {
        match n.key.cmp(&self.key) {
            Less => {
                match self.left {
                    None => self.left = Some(Box::new(n)),
                    Some(ref mut l) => l.insert(n),
                }
            }
            Greater => {
                match self.right {
                    None => self.right = Some(Box::new(n)),
                    Some(ref mut r) => r.insert(n),
                }
            }
            _ => {}
        }
    }

    fn height(&self) -> u32 {
        let mut left_he = 1;
        if let Some(ref l) = self.left {
            left_he = 1 + l.height()
        }
        let mut right_he = 1;
        if let Some(ref r) = self.right {
            right_he = 1 + r.height()
        }
        if left_he > right_he {
            return left_he;
        }
        return right_he;
    }

    fn rec(&self) -> u32 {
        let mut le = 0;
        if let Some(ref l) = self.left {
            le = l.height()
        }
        let mut re = 0;
        if let Some(ref r) = self.right {
            re = r.height()
        }
        let hei = le + re + 1;
        let mut led = 0;
        let mut red = 0;

        let Some(ref l) = self.left;

        let Some(ref r) = self.right;

        rayon::join(|| led = l.rec(), || red = r.rec());

        let greater_diameter;
        if red > led {
            greater_diameter = red;
        } else {
            greater_diameter = led;
        }

        if hei > greater_diameter {
            return hei;
        }
        return greater_diameter;
    }

    fn print_recursive(nodes: Vec<&Self>) {
        let mut v: Vec<&Self> = vec![];
        for n in nodes {
            print!("1 ");
            match n.left {
                None => {}
                Some(ref l) => v.push(&*l),
            }
            match n.right {
                None => {}
                Some(ref r) => v.push(&*r),
            }
        }
        println!("");
        if v.len() > 0 {
            Node::print_recursive(v);
        }
    }
}

#[derive(Debug, Default)]
struct Bst<K> {
    root: Option<Box<Node<K>>>,
}
impl<K> Bst<K> {
    fn new() -> Bst<K> {
        Bst { root: None }
    }
}

impl<K: Ord> Bst<K> {
    fn insert(&mut self, k: K) {
        match self.root {
            None => self.root = Some(Box::new(Node::new(k))),
            Some(ref mut r) => r.insert(Node::new(k)),
        }
    }

    fn rec(&self) -> u32 {
        match self.root {
            None => 0,
            Some(ref r) => r.rec(),
        }
    }

    fn print(&self) {
        match self.root {
            None => {}
            Some(ref r) => Node::print_recursive(vec![&*r]),
        };
    }
}

fn main() {
    let mut bst1 = Bst::new();

    bst1.insert(20);
    bst1.insert(21);
    bst1.insert(22);
    bst1.insert(23);
    bst1.insert(24);
    bst1.insert(25);
    bst1.insert(19);
    bst1.insert(18);
    bst1.insert(17);
    bst1.insert(16);
    bst1.insert(15);
    bst1.insert(14);
    bst1.print();

    println!("{}", bst1.rec());
}

当我编译（rustc code.rs）时，它显示

error: can't find crate for `rayon` [E0463]

我的 Rust 版本是rustc 1.8.0 (db2939409 2016-04-11)

4

1 回答 1

7

您不能只使用外部依赖项而不告诉编译器在哪里找到它。最简单的方法是创建一个Cargo.toml文件，然后使用它cargo build来编译您的项目，而不是rustc直接编译。

要创建Cargo.toml文件，您只需进入项目目录并键入：

cargo init --bin

这将做两件事：

  1. 创建文件src/main.rs。你应该把你的代码放在这里。
  2. 创建一个Cargo.toml文件，Cargo 使用该文件来存储依赖项和其他构建信息

然后，您可以编辑Cargo.toml以添加rayon依赖项。人造丝的crates.io 页面为您提供了您可以粘贴在那里的确切信息。完成后，它应该如下所示：

[package]
name = "foo"
version = "0.1.0"
authors = ["singh <singh@singh.com>"]

[dependencies]
rayon = "0.3.1"

完成此操作后，您可以使用以下命令构建项目：

cargo build

或运行：

cargo run

您可以在货运指南中获得更多信息。

于 2016-04-23T09:22:26.833 回答