rust - 你如何在 Rust 中实现这个简单的 trie 节点？

Question

我想实现一个 trie对于整数索引序列。为了提高效率，节点的子节点通过索引序列而不是某种映射与节点相关联很重要。为了说明基本思想，这里是 Ruby 中的一个实现:

require 'virtus'

class TrieNode
  include Virtus.model

  attribute :terminal, Boolean, default: false
  attribute :children, Array,   default: []

  def add(i, vec)
    if i == vec.length
      terminal = true
    else
      ( children[vec[i]] ||= TrieNode.new ).add i + 1, vec
    end
  end
end

这是 Perl 中的相同内容:

package TrieNode;
use Moo;

has terminal => ( is => 'rw' );
has children => ( is => 'ro', default => sub { [] } );

sub add {
   my ( $self, $i, $vec ) = @_;
   if ( $i == @$vec ) {
      $self->terminal(1);
   }
   else {
      ( $self->children->[ $vec->[$i] ] //= TrieNode->new )->add( ++$i, $vec );
   }
}

'wheee!!!';

这是我在 Rust 中实现它的各种尝试之一:

struct TrieNode {
    children: Vec<Option<TrieNode>>,
    terminal: bool
}

impl TrieNode {
    fn new() -> TrieNode { TrieNode { children: vec![], terminal: false } }
    fn add(&mut self, i: usize, s: &Vec<usize>) {
        if s.len() == i {
            self.terminal = true;
        } else {
            let j = s[i];
            let k = j - 1;
            let ref mut c = self.children;
            while c.len() < k {
                c.push(None);
            }
            if c.len() < j {
                let mut n = TrieNode::new();
                n.add( i + 1, s );
                c.push(Some(n));
            } else {
                let ref o = c[j];
                match o {
                    Some(ref mut n) => {
                        n.add( i + 1, s );
                    },
                    None => {
                        let mut n = TrieNode::new();
                        n.add( i + 1, s );
                        c.remove(j);
                        c.insert(j, Some(n));
                    }
                }
            }
        }
    }
}

对于它的值(value)，这里是该尝试的编译错误:

file_toy (master #) $ cargo build
   Compiling file_toy v0.1.0 (file:///Users/houghton/playground/file_toy)
src/main.rs:27:21: 27:36 error: mismatched types:
 expected `&_`,
    found `core::option::Option<_>`
(expected &-ptr,
    found enum `core::option::Option`) [E0308]
src/main.rs:27                     Some(ref mut n) => {
                                   ^~~~~~~~~~~~~~~
src/main.rs:27:21: 27:36 help: run `rustc --explain E0308` to see a detailed explanation
src/main.rs:30:21: 30:25 error: mismatched types:
 expected `&_`,
    found `core::option::Option<_>`
(expected &-ptr,
    found enum `core::option::Option`) [E0308]
src/main.rs:30                     None => {
                                   ^~~~
src/main.rs:30:21: 30:25 help: run `rustc --explain E0308` to see a detailed explanation
src/main.rs:28:27: 28:30 error: the type of this value must be known in this context
src/main.rs:28                         n.add( i + 1, s );
                                         ^~~
error: aborting due to 3 previous errors
error: Could not compile `file_toy`.

它的预期用途是 this 的 Rust 实现.这个 trie，一旦被序列填满，将是不可变的，并将在程序的整个生命周期内存在。我这样做是为了学习 Rust，所以我的愚蠢越多越好。谢谢!

Answer 1

你的控制流程有点绕，而且有很多嵌套。通过减少嵌套和展开控制流，我们可以得到一些更可口的东西。我也希望避免所有冗余。

#[derive(Clone, Debug, Default)]
struct TrieNode {
    children: Vec<Option<TrieNode>>,
    terminal: bool
}

impl TrieNode {
    pub fn add(&mut self, element: &[usize]) {
        if element.len() == 0 {
            self.terminal = true;
            return;
        }

        let ref mut c = self.children; 

        let value = element[0];

        //  Ensure there is at least "value" children
        if c.len() < value { c.resize(value, None); }

        //  Ensure the "value"th child is a full TrieNode
        if c[value - 1].is_none() {
            c[value - 1] = Some(TrieNode::default());
        }

        c[value - 1].as_mut().unwrap().add(&element[1..]);
    }
}

fn main() {
    let mut t = TrieNode::default();
    t.add(&[1, 2]);
    println!("{:?}", t);
}

烦人的是 add 的后 6 行。 match 在概念上更优雅，但是您不能在 match 期间借用 c[value - 1] 并在 中修改它code>None 分支，因为借用检查不是“路径感知”的，而只是“范围感知的”( future 可能会取消的限制，但我们现在必须应对)。

建议:

• 尽可能多地检查现有方法。例如，使用 Vec::resize 而不是 while 循环可以更准确地传达意图。
• 检查现有特征，当 new() 不带参数时，最好实现 Default 特征(打开更多门)；此外，Default 可以定期派生，因此您甚至不必输入它!
• 当不需要 String/Vec 的所有权时使用切片。除了使代码更通用(任何可对切片取消引用的类型都可以工作)之外，我们还受益于索引符号 [1..] 以廉价地切断第一个元素，从而避免携带额外的索引。

所有这些都使代码更短，更少的代码通常意味着更少的错误出现的机会。尤其是在避免重复的情况下。

---

另一方面，如果您愿意为 child 使用 HashMap 或 BTreeMap，您可以获得免费的“稀疏”和更简单的添加方法。例如，修改为 use std::collections::HashMap 的 add 方法:

impl TrieNode {
    pub fn add(&mut self, element: &[usize]) {
        if element.len() == 0 {
            self.terminal = true;
            return;
        }

        self.children
            .entry(element[0])
            .or_insert(TrieNode::default())
            .add(&element[1..]);
    }
}

很多，很多，更简单，不是吗？