Pertanyaan Menambahkan metode tambahan ke daftar tertaut tunggal


Saya sedang melihat melalui contoh daftar tertaut tunggal di rustbyexample.com dan saya perhatikan penerapannya tidak append metode, jadi saya memutuskan untuk mencoba dan menerapkannya:

fn append(self, elem: u32) -> List {
    let mut node = &self;
    loop { 
        match *node {
            Cons(_, ref tail) => {
                node = tail;
            },
            Nil => {
                node.prepend(elem);
                break;
            },
        }
    }
    return self;
}

Di atas adalah salah satu dari banyak upaya yang berbeda, tetapi saya tidak dapat menemukan cara untuk beralih ke ekor dan memodifikasinya, lalu entah bagaimana mengembalikan kepala, tanpa mengganggu pemeriksa pinjaman dalam beberapa cara.

Saya mencoba mencari solusi yang tidak melibatkan menyalin data atau melakukan pembukuan tambahan di luar append metode.


5
2018-05-15 10:11


asal


Jawaban:


Seperti yang dijelaskan dalam Tidak dapat memperoleh referensi yang bisa berubah ketika mengulangi struktur rekursif: tidak dapat meminjam sebagai bisa berubah lebih dari sekali pada suatu waktu, Anda perlu mentransfer kepemilikan referensi yang bisa berubah saat melakukan iterasi. Ini diperlukan untuk memastikan Anda tidak pernah memiliki dua referensi yang dapat berubah ke hal yang sama.

Kami menggunakan kode yang sama seperti itu Q & A untuk mendapatkan referensi yang bisa berubah ke item terakhir (back) yang akan selalu menjadi Nil varian. Kami kemudian memanggilnya dan mengaturnya Nil item ke a Cons. Kami membungkus semua itu dengan fungsi bernilai-nilai karena itulah yang diinginkan API.

Tidak ada alokasi tambahan, tidak ada risiko kehabisan frame stack.

use List::*;

#[derive(Debug)]
enum List {
    Cons(u32, Box<List>),
    Nil,
}

impl List {
    fn back(&mut self) -> &mut List {
        let mut node = self;

        loop {
            match {node} {
                &mut Cons(_, ref mut next) => node = next,
                other => return other,
            }
        }
    }

    fn append_ref(&mut self, elem: u32) {        
        *self.back() = Cons(elem, Box::new(Nil));
    }

    fn append(mut self, elem: u32) -> Self {
        self.append_ref(elem);
        self
    }
}

fn main() {
    let n = Nil;
    let n = n.append(1);
    println!("{:?}", n);
    let n = n.append(2);
    println!("{:?}", n);
    let n = n.append(3);
    println!("{:?}", n);
}

Kapan masa hidup non-leksikal diaktifkan, fungsi ini bisa lebih jelas:

fn back(&mut self) -> &mut List {
    let mut node = self;

    while let Cons(_, next) = node {
        node = next;
    }

    node
}

7
2018-05-15 13:16



Sebagai len Metode diimplementasikan secara rekursif, saya telah melakukan hal yang sama untuk append pelaksanaan:

fn append(self, elem: u32) -> List {
    match self {
        Cons(current_elem, tail_box) => {
            let tail = *tail_box;
            let new_tail = tail.append(elem);

            new_tail.prepend(current_elem)
        }
        Nil => {
            List::new().prepend(elem)
        }
    }
}

Satu solusi iteratif mungkin akan diterapkan append dengan kondisi prepend dan fungsi sebaliknya, seperti halnya (tidak akan performen tetapi seharusnya tetap hanya O (N)):

// Reverses the list
fn rev(self) -> List {
    let mut result = List::new();
    let mut current = self;
    while let Cons(elem, tail) = current {
        result = result.prepend(elem);
        current = *tail;
    }

    result
}

fn append(self, elem: u32) -> List {
    self.rev().prepend(elem).rev()
}

1
2018-05-15 11:44



Jadi, sebenarnya akan menjadi sedikit lebih sulit daripada yang mungkin Anda pikirkan; kebanyakan karena Box aku s sangat hilang yang merusak take metode yang akan mengembalikan kontennya.


Cara mudah: cara rekursif, tidak kembali.

fn append_rec(&mut self, elem: u32) {
    match *self {
        Cons(_, ref mut tail) => tail.append_rec(elem),
        Nil => *self = Cons(elem, Box::new(Nil)),
    }
}

Ini relatif mudah, seperti yang disebutkan.


Cara yang lebih sulit: cara rekursif, dengan kembali.

fn append_rec(self, elem: u32) -> List {
    match self {
        Cons(e, tail) => Cons(e, Box::new((*tail).append_rec(elem))),
        Nil => Cons(elem, Box::new(Nil)),
    }
}

Perhatikan bahwa ini terlalu tidak efisien. Untuk daftar ukuran N, kita menghancurkan kotak N dan mengalokasikan N yang baru. Di tempat mutasi (pendekatan pertama), adalah banyak lebih baik dalam hal ini.


Cara yang lebih keras: cara iteratif, tanpa kembali.

fn append_iter_mut(&mut self, elem: u32) {
    let mut current = self;
    loop {
        match {current} {
            &mut Cons(_, ref mut tail) => current = tail,
            c @ &mut Nil => {
                *c = Cons(elem, Box::new(Nil));
                return;
            },
        }
    }
}

Oke ... jadi mengulang (goyah) di atas struktur data bertingkat tidak mudah karena kepemilikan dan pemeriksaan pinjam akan memastikan bahwa:

  • referensi yang bisa berubah tidak pernah disalin, hanya dipindahkan,
  • referensi yang bisa berubah dengan pinjaman luar biasa tidak dapat dimodifikasi.

Inilah mengapa di sini:

  • kita gunakan {current} untuk bergerak current ke dalam pertandingan,
  • kita gunakan c @ &mut Nil karena kita perlu menamai kecocokan &mut Nil sejak current telah dipindahkan.

Perhatikan bahwa untungnya rustc cukup pintar untuk memeriksa jalur eksekusi dan mendeteksi bahwa tidak apa-apa untuk melanjutkan perulangan selama kita mengambil Cons cabang sejak kami menginisialisasi ulang current di cabang itu, namun tidak boleh melanjutkan setelah mengambil Nilcabang, yang memaksa kita untuk mengakhiri loop :)


Cara yang lebih keras: cara iteratif, dengan kembali

fn append_iter(self, elem: u32) -> List {
    let mut stack = List::default();
    {
        let mut current = self;
        while let Cons(elem, tail) = current {
            stack = stack.prepend(elem);
            current = take(tail);
        }
    }

    let mut result = List::new();
    result = result.prepend(elem);

    while let Cons(elem, tail) = stack {
        result = result.prepend(elem);
        stack = take(tail);
    }

    result
}

Dengan cara rekursif, kami menggunakan tumpukan untuk menyimpan barang-barang untuk kami, di sini kami menggunakan struktur tumpukan sebagai gantinya.

Ini bahkan lebih tidak efisien daripada cara rekursif dengan kembali; setiap node menyebabkan dua dealokasi dan dua alokasi.


TL; DR: Modifikasi di tempat biasanya lebih efisien, jangan takut menggunakannya ketika diperlukan.


1
2018-05-15 12:57