더 이상 눈물 흘리지 않아, 더 이상 맺히지 않아: 나무가 녹슬어 얼룩덜룩하다

경기장에 입장하다
Rust에서 프로그래밍을 할 때, 당신이 알고 있는 습관적인 사용법을 직접 번역하는 것은 항상 그렇게 간단하지 않습니다.그 중 하나는 트리 데이터 구조다.이러한 구조는 전통적으로Node 구조로 구축되었고 이런 구조는 나무 중의 기타Node 구조를 인용한다.구조를 반복하려면 이 인용을 사용해야 합니다. 나무의 구조를 바꾸는 것은 모든 나무에서 인용된 노드를 바꾸는 것을 의미합니다.
Rust는 이런 거 싫어해.곧 문제가 발생하기 시작할 것입니다. 예를 들어 노드를 훑어볼 때 구조를 빌려야 합니다.이렇게 하면 내부 구조로 다른 일을 하기 어려울 것이다.
그러나 나무는 생명의 일부이며, 이 방면에서 매우 유용하다.아플 필요 없어!우리는 그것을 거의 잊어버릴 정도로 region-based memory management 사용할 수 있다.

사막.
오늘 이 점을 시험해 보기 전에 나는 간단하게 다른 몇 가지 방법을 소개할 것이다.
가장 간단한 방법은 사용 unsafe 이다. 이것은 당신이 C에서처럼 원시 지침을 사용할 수 있도록 허락한다. 이것은 우리가 안전한 녹을 사용하는 것에서 얻은 많은 장점을 상실할 것이다. 왜냐하면 한 번 사용 unsafe 하면 당신의 전체 판자 상자에 감염되기 때문이다.현재 일부 코드는 안전하다고 여겨진다. 왜냐하면 프로그래머들은 그것이 녹슨 컴파일러가 아니라 안전하다고 생각하기 때문이다.
정적 보안 Rust를 꾸준히 사용하려면 내부 가변성을 가진 참조 계수 스마트 포인터Rc<RefCell<T>> 유형으로 포인터를 포장할 수 있다.Rc::clone(&ptr)를 호출할 때 같은 데이터를 가리키는 새로운 지침을 얻을 수 있습니다. 이 지침은 기존의 지침과 분리되어 있고, 모든 Rc 이 삭제될 때 데이터 자체도 삭제됩니다.이것은 정적 쓰레기 수집의 일종이다.RefCell 가변적인 사물에서 가변적인 것을 빌려쓰고 실행할 때 정적 집행이 아니라 강제로 실행할 수 있도록 합니다.이것은 너로 하여금 부정행위를 하게 한다. 만약 망치면 너는 부정행위를 할 것이다. panic!() 그래서 나는 만세를 원한다.data.borrow_mut()와 같은 방법을 사용해야 하지만, 반복하는 과정에서 next 필드에서 변경할 수 없는 대여를 사용하여 바늘을 변경할 수 있습니다.
또는 Box 스마트 포인터를 사용하여 주위를 복제하고 이유 없이 많은 추가 작업을 수행할 수 있습니다. 이것은 전체 하위 트리를 깊이 있게 복제하여 작은 편집을 하는 것과 관련이 있습니다.알다시피 그것은 내 일이 아니다.
일반 참조를 사용하여 명시적 생존 기간을 도입할 수도 있습니다.

struct Node<'a> {
    val: i32,
    next: &'a Node,
}

아이고, 너 지금 'a를 여기저기 뿌릴지도 몰라. 일부가 b와 친하게 지내고 싶어할 거야. 와우.이것은 너무 징그럽다. 너는 지금 더 간단한 문제를 해결하고 있다. 필요하다.
이 모든 선택은 고통을 의미하며 종종 타협을 의미한다.적어도 내 경험에서, 비록 너는 통상적으로 성공적으로 컴파일할 수 있지만, 너의 코드는 곧 읽을 수 없고 유지할 수 없게 될 것이다. 만약 네가 다른 선택을 해야 한다면, 너는 거의 원점으로 돌아가 이 모든 것을 결합시키려고 시도할 것이다.이것도 내가 녹 자국에서 단층을 생성할 수 있는 유일한 방법이다.나는 내가 일을 망친 것이 인상적이었다. 나는 내가 어떻게 했는지 더 잘 기록할 수 있기를 바란다. 그러나 나는 이것이 위와 같은 허튼소리라는 것을 안다.
문제는 Rust는 누가 당신의 노드와 각 노드의 생명 주기를 가지고 있는지 주의를 기울일 것이지만, 구조를 구축할 때 컴파일러가 항상 당신이 무엇을 하려는지 이해하기가 쉽지 않다는 것이다.최종적으로 추정되는 생명주기는 당신의 구조에 있어서 너무 작거나 정확하지 않아서 지도를 효과적으로 훑어보거나 편집할 수 없습니다.너는 결국 컴파일러를 설득하기 위해 수작업을 해야 한다. 네가 옳다는 것은 정말 야단났다.

오아시스
만약 당신의 노드가 모두 같은 생명 주기를 가지고 있다면?내 말은, 그들은 기본적으로 이렇다, 그렇지?물론, 일부는 하나하나 만들어질 수 있지만, 이 프로그램의 모든 의도와 목적 때문에, 최고급 트리 구조에 대한 관심만 있으면 됩니다.
아주 간단한 방법이 있습니다. Vec<T> 상자로 그것들을 열 수 있습니다.

#[derive(Debug, Default)]
struct ArenaTree<T> 
where
    T: PartialEq
{
    arena: Vec<Node<T>>,
}

번영하다.나무그것은 ==와 비교할 수 있는 모든 유형에 대해 통용되고 사용 수명 문제를 해결했다.노드를 원하십니까?사용self.arena[idx].다른 노드에 대한 실제 참조를 저장하기보다는 각 노드에 대한 인덱스를 제공합니다.

#[derive(Debug)]
struct Node<T>
where
    T: PartialEq
{
    idx: usize,
    val: T,
    parent: Option<usize>,
    children: Vec<usize>,
}

이 트리에는 각 노드마다 0 개 또는 1 개의 부모 노드와 0 개 이상의 하위 노드가 있다.
새 노드에는 지정된 ID와 저장할 값이 필요하며 다른 노드에는 연결되지 않습니다.

impl<T> Node<T>
where
    T: PartialEq
{
    fn new(idx: usize, val: T) -> Self {
        Self {
            idx,
            val,
            parent: None,
            children: vec![],
        }
    }
}

너는 계속해서 임의의 색인을 저장할 수 있다. 이것은 너의 도표이다.이것이 바로 내가 사용한 예시수Day 6 of AoC(그리고 우리가 여기에 있는 이유)이다.
이것은 사용하기 쉽다.값을 원할 때 색인을 요구할 수 있습니다.

impl<T> ArenaTree<T>
where
    T: PartialEq
{
    fn node(&mut self, val: T) -> usize {
        //first see if it exists
        for node in &self.arena {
            if node.val == val {
                return node.idx;
            }
        }
        // Otherwise, add new node
        let idx = self.arena.len();
        self.arena.push(Node::new(idx, name));
        idx
    }
}

이전에 존재했든 존재하지 않았든 간에, 지금은 트리에 이 값의 인덱스가 있습니다.존재하지 않으면 기존 노드와 연결하지 않고 새 노드를 분배합니다.ArenaTree가 범위를 벗어나면 자동으로 삭제되므로 모든 노드는 항상 다른 노드와 같이 길고 모든 노드가 동시에 정리됩니다.
이 코드는 스트리밍이 얼마나 쉬워졌는지 보여 준다. for node in &self.arena 스트리밍 벡터만 사용하면 된다.어떤 조작들은 보잘것없게 변했다. 몇 개의 노드가 필요합니까?고생을 사서 하다.

fn size(&self) -> usize {
    self.arena.len()
}

몇 쪽이 있는지 세어보는 게 어때요?여기도 별거 아니야. 세어봐.

fn edges(&self) -> usize {
    self.arena.iter().fold(0, |acc, node| acc + node.children.len())
}

그러나 표준적인 귀속 데이터 구조는 여전히 쉽다.노드의 깊이를 볼 수 있습니다.

fn depth(&self, idx: usize) -> usize {
    match self.arena[idx].parent {
        Some(id) => 1 + self.depth(id),
        None => 0,
    }
}

루트에서 값을 검색하여 깊이를 반환하려면 다음과 같이 하십시오.

fn depth_to_target(&self, idx: usize, target: &T) -> Option<usize> {
    // are we here?  If so, Some(0)
    if target == &self.arena[idx].val {
        return Some(0);
    }

    // If not, try all children
    for p in &self.arena[idx].children {
        if let Some(x) = self.depth_to_target(*p, &target) {
            return Some(1 + x);
        }
    }
    // If it cant be found, return None
    None
}

물론 반복할 수도 있다.이 방법은 두 노드의 부모 노드 사이의 거리를 반복하고 반복하여 일련의 깊이 우선 검색을 수행합니다.

fn distance_between(&mut self, from: T, target: T) -> usize {
    // If it's not in the tree, this will add a new unconnected node
    // the final function will still return None
    let start_node = self.node(from);
    let mut ret = 0;
    // Start traversal
    let mut trav = &self.arena[start_node];
    // Explore all children, then hop up one
    while let Some(inner) = trav.parent {
        if let Some(x) =  self.depth_to_target(inner, &target) {
            ret += x;
            break;
        }
        trav = &self.arena[inner];
        ret += 1;
    }
    // don't go all the way to target, just orbit
    ret - 1
}

거슬러 올라갈 때마다 작업이 조금씩 반복되지만 퍼즐 규모에서도 거의 즉각 계산된다.그것은 매우 간결하고 읽기 쉽다. 내가 녹나무를 형용하는 단어가 아니다.
삽입은 도메인에 따라 달라지지만 이 응용 프로그램이 수신하는 입력은 PARENT)CHILD이므로 내insert는 다음과 같습니다.

fn insert(&mut self, orbit: &str) {
    // Init nodes
    let split = orbit.split(')').collect::<Vec<&str>>();
    let inner = self.node(split[0]);
    let outer = self.node(split[1]);
    // set orbit
    match self.object_arena[outer].parent {
        Some(_) => panic!("Attempt to overwrite existing orbit"),
        None => self.object_arena[outer].parent = Some(inner),
    }
    // set parents
    self.object_arena[inner].children.push(outer);
}

요컨대, 주어진 노드를 조종하고 싶을 때마다, 색인만 있으면 된다.이것들은 모두 편리하다Copy. 그러므로 그것들을 조종하는 것을 너무 걱정하지 마라.노드의 인덱스를 가져오려면 tree.node(val) 을 호출하십시오.먼저 검색을 실행한 다음 나무의 경기장에 분배하면 (경기장에 없으면) 시종일관 성공할 것입니다.그리고 노드가 속한 인덱스self.arena[idx].children.push(outer);에 따라 노드의 필드를 조작할 수 있습니다.너는 더 이상 메모리를 걱정할 필요가 없다. 너의 Vec 는 가능할 때 자동으로 떨어질 것이다.각 노드에 저장된 인덱스와 새 인덱스를 삽입할 때 발생하는 상황을 통해 트리의 구조를 정의할 수 있습니다.
기본적으로, 이것은 당신이 원하는 나무이지만, 녹이 슬어서, 심지어는 그것을 위해 싸울 필요도 없다. 나무는 매우 좋다.
여기에 도장과 도장을 할 수 있는 playground link가 하나 있다.
표지 사진은 아만다 플라빌이 찍었다