Get best of the week

Karat. Meminjam pemeriksa melalui iterator

Halo, Habr!

Saya telah belajar selama sekitar satu tahun dan, di waktu luang saya, saya menulis di masa lalu. Saya suka bagaimana penulisnya memecahkan masalah manajemen memori dan membuang pengumpul sampah - melalui konsep pinjaman. Pada artikel ini saya akan mendekati ide ini melalui iterator.

Akhir-akhir ini, scala adalah bahasa utama saya, jadi akan ada perbandingan dengan itu, tetapi tidak banyak dari mereka dan semuanya intuitif, tanpa sihir :)

Artikel ini dirancang untuk mereka yang mendengar sesuatu tentang karat, tetapi tidak masuk ke rincian.


foto diambil dari sini dan dari sini

Kata pengantar


Dalam bahasa jvm, biasanya untuk menyembunyikan pekerjaan dengan tautan, yaitu, di sana kami hampir selalu bekerja dengan tipe data referensi, jadi kami memutuskan untuk menyembunyikan ampersand (&).

Dalam rasta terdapat tautan eksplisit, misalnya ke integer - `& i32`, tautan tersebut dapat ditinjau ulang melalui` *`, juga ada tautan ke tautan tersebut dan kemudian perlu ditinjau ulang dua kali **.

Iterator


Saat menulis kode, sangat sering Anda perlu memfilter koleksi berdasarkan kondisi (predikat). Di batu untuk mengambil elemen genap akan terlihat seperti ini:

    val vec = Vector(1,2,3,4)
    val result = vec.filter(e => e % 2 == 0)

Mari kita lihat jenisnya:

  private[scala] def filterImpl(p: A => Boolean, isFlipped: Boolean): Repr = {
    val b = newBuilder
    for (x <- this)
      if (p(x) != isFlipped) b += x

    b.result
  }

Tanpa masuk ke perincian `newBuilder`, jelaslah bahwa koleksi baru sedang dibuat, kami beralih ke yang lama dan jika predikat mengembalikan true, lalu tambahkan elemen. Terlepas dari kenyataan bahwa koleksinya baru, unsur-unsurnya sebenarnya terkait dengan unsur-unsur dari koleksi pertama, dan jika, tiba-tiba, unsur-unsur ini dapat berubah, maka mengubahnya akan menjadi hal yang biasa di kedua koleksi.

Sekarang mari kita coba melakukan hal yang sama di masa lalu. Saya akan segera memberikan contoh kerja, dan kemudian saya akan mempertimbangkan perbedaannya.

    let v: Vec<i32> = vec![1, 2, 3, 4];
    let result: Vec<&i32> = v.iter().filter(|e| **e % 2 == 0).collect();

Wow, wow apa? Dereferensi pointer ganda? Hanya untuk menyaring vektor? Sulit :( Tapi ada alasan untuk ini.

Mari kita cari tahu bagaimana kode ini berbeda dari rock:

  1. secara eksplisit mendapatkan iterator pada vektor (`iter ()`)
  2. dalam fungsi predikat, untuk beberapa alasan, kami melakukan dereferensi pointer dua kali
  3. panggil `collect ()`
  4. itu juga menghasilkan vektor jenis referensi Vec <& i32>, dan bukan ints biasa

Pemeriksa pinjaman


Mengapa memanggil secara eksplisit `iter ()` di koleksi? Jelas bagi rockman manapun bahwa jika Anda memanggil `.filter (...)` maka Anda perlu mengulangi koleksi tersebut. Mengapa dalam suatu masa secara eksplisit menulis apa yang dapat dilakukan secara implisit? Karena ada tiga iterator berbeda!



Untuk mencari tahu mengapa tiga? perlu menyentuh Peminjam (pinjam, pinjam) pemeriksa 'a. Hal yang paling penting dimana rast bekerja tanpa GC dan tanpa alokasi / deallokasi memori eksplisit.

Mengapa itu dibutuhkan?

  1. Untuk menghindari situasi ketika beberapa petunjuk menunjuk ke area memori yang sama, memungkinkan Anda untuk mengubahnya. Itu adalah kondisi lomba.
  2. Agar tidak membatalkan memori yang sama beberapa kali.

Bagaimana ini dicapai?

Karena konsep kepemilikan.

Secara umum, konsep kepemilikan itu sederhana - hanya satu yang bisa memiliki sesuatu (bahkan intuisi).

Pemilik dapat berubah, tetapi dia selalu sendirian. Ketika kita menulis `let x: i32 = 25`, ini berarti bahwa ada alokasi memori untuk int 32bit dan pemilik tertentu` x` memilikinya. Gagasan kepemilikan hanya ada dalam pikiran penyusun, di pemeriksa pinjaman. Ketika pemilik, dalam hal ini, `x` meninggalkan ruang lingkup (keluar dari ruang lingkup), memori yang dimilikinya akan dihapus.

Berikut adalah kode yang tidak akan dilewatkan oleh pemeriksa pinjaman:


struct X; // 

fn test_borrow_checker () -> X {
    let first = X; //  
    let second = first; //  
    let third = first; //   ,   first   
//    value used here after move

    return third;
}

`struct X` adalah sesuatu seperti` case kelas X () `- struktur tanpa batas.

Perilaku ini sangat berlawanan dengan intuisi, saya pikir, untuk semua orang. Saya tidak tahu bahasa lain di mana tidak mungkin untuk "menggunakan" "variabel" yang sama dua kali. Penting untuk merasakan momen ini. pertama sama sekali bukan referensi ke X, itu adalah pemiliknya . Mengubah pemilik, kami jenis membunuh yang sebelumnya, pemeriksa pinjaman tidak akan mengizinkan penggunaannya.

Mengapa Anda perlu membuat struktur sendiri, mengapa tidak menggunakan integer biasa?
— (`struct X`), , , integer. , , :


fn test_borrow_checker () -> i32 {
    let first = 32;
    let second = first; 
    let third = first; 

    return third;
}

, borrow checker, , . Copy, . `i32` second , ( ), - third . X Copy, .

. , , «» . Clone, , . copy clone.

Kembali ke iterators. Konsep "capture" di antara mereka adalah IntoIter . Dia “menelan” koleksi itu, memberikan kepemilikan atas elemen-elemennya. Dalam kode, ide ini akan tercermin seperti ini:


let coll_1 = vec![1,2,3];
let coll_2: Vec<i32> = coll_1.into_iter().collect();
//coll_1 doesn't exists anymore

Dengan memanggil `into_iter ()` di coll_1 kami "mengubahnya" menjadi iterator, menyerap semua elemennya, seperti dalam contoh sebelumnya, `second` absorbed` first`. Setelah itu, semua panggilan ke coll_1 akan dihukum oleh pemeriksa pinjaman selama kompilasi. Kemudian kami mengumpulkan elemen-elemen ini dengan fungsi `collect`, membuat vektor baru. Fungsi `collect` diperlukan untuk mengumpulkan koleksi dari iterator, untuk ini Anda harus secara eksplisit menentukan jenis apa yang ingin kami kumpulkan. Oleh karena itu, coll_2 dengan jelas menunjukkan jenisnya.

Oke, secara umum, yang dijelaskan di atas sudah cukup untuk bahasa pemrograman, tetapi tidak akan sangat efisien untuk menyalin / mengkloning struktur data setiap kali kami ingin mentransfernya, dan Anda juga harus dapat mengubah sesuatu. Jadi kita pergi ke petunjuk.

Pointer


Pemiliknya, seperti yang sudah kami ketahui, hanya bisa satu. Tetapi Anda dapat memiliki sejumlah tautan.


#[derive(Debug)]
struct Y; // 

fn test_borrow_checker() -> Y {
    let first = Y; //  
    let second: &Y = &first; //   ,     
    let third = &first; //    

// 
    println!("{:?}", second);
    println!("{:?}", third);

    return first;
}

Kode ini sudah valid, karena pemiliknya masih satu. Semua logika kepemilikan diperiksa hanya pada tahap kompilasi, tanpa memengaruhi alokasi / pemindahan memori. Selain itu, Anda dapat melihat bahwa jenis detik telah berubah menjadi `& Y`! Artinya, semantik kepemilikan dan tautan tercermin dalam jenisnya, yang memungkinkan Anda memeriksa selama kompilasi, misalnya, tidak adanya kondisi balapan.

Bagaimana saya bisa melindungi dari kondisi balapan pada waktu kompilasi?

Dengan menetapkan batas jumlah tautan yang bisa berubah-ubah!

Tautan yang dapat berubah pada satu saat dapat menjadi satu dan hanya satu (tanpa berubah). Yaitu, salah satu / beberapa tidak berubah, atau satu bisa berubah. Kode ini terlihat seperti ini:


// 
struct X {
    x: i32,
} 

fn test_borrow_checker() -> X {
    let mut first = X { x: 20 }; //  
    let second: &mut X = &mut first; //   
    let third: &mut X = &mut first; //    .        `second`        - .
//    second.x = 33;  //    ,             ,    
    third.x = 33;

    return first;
}

Mari kita membahas perubahan dalam contoh relatif sebelumnya. Pertama, kami menambahkan satu bidang ke struktur sehingga ada sesuatu yang berubah, karena kami membutuhkan kemampuan berubah-ubah. Kedua, `mut` muncul dalam deklarasi variabel` let mut first = ...`, ini adalah penanda kompilator tentang mutabilitas, seperti `val` &` var` di dalam rock. Ketiga, semua tautan telah mengubah tipenya dari `& X` ke` & mut X` (sepertinya, tentu saja, mengerikan. Dan ini tanpa masa pakai ...), sekarang kita dapat mengubah nilai yang disimpan oleh tautan.

Tetapi saya mengatakan bahwa kita tidak dapat membuat beberapa tautan yang dapat berubah, mereka mengatakan peminjam tidak akan memberikan ini, tetapi saya membuat dua tautan sendiri! Ya, tetapi pemeriksaan di sana sangat rumit, itulah sebabnya terkadang tidak jelas mengapa kompiler bersumpah. Dia berusaha keras untuk memastikan bahwa program Anda dikompilasi dan jika sama sekali tidak ada opsi untuk memenuhi aturan, maka kesalahan, dan mungkin bukan yang Anda tunggu, tetapi yang melanggar upaya terakhirnya, yang paling putus asa dan tidak jelas bagi pemula: ) Sebagai contoh, Anda diberitahu bahwa struktur tidak menerapkan sifat Salin, meskipun Anda tidak menyebut salinan apa pun di mana pun.

Dalam hal ini, keberadaan dua tautan yang dapat berubah diizinkan pada saat yang sama karena kami hanya menggunakan satu, yaitu, yang kedua dapat dibuang dan tidak ada yang akan berubah. Juga `detik` dapat digunakan hinggabuat `third` dan kemudian semuanya akan baik-baik saja. Tetapi, jika Anda membatalkan komentar `second.x = 33;`, ternyata dua tautan yang bisa berubah ada secara bersamaan dan Anda tidak dapat keluar dari sini - kompilasi kesalahan waktu.

Iterator


Jadi, kami memiliki tiga jenis transmisi:

  1. Penyerapan, peminjaman, pemindahan
  2. Tautan
  3. Tautan yang dapat diubah

Setiap jenis membutuhkan iterator sendiri.

  1. IntoIter menyerap objek dari koleksi asli
  2. Iter berjalan pada tautan objek
  3. IterMut berjalan pada referensi objek yang bisa diubah

Muncul pertanyaan - kapan harus menggunakan yang mana. Tidak ada peluru perak - Anda perlu latihan, membaca kode orang lain, artikel. Saya akan memberikan contoh yang menunjukkan ide tersebut.

Misalkan ada sekolah, ada kelas di dalamnya, dan siswa di kelas.


#[derive(PartialEq, Eq)]
enum Sex {
    Male,
    Female
}

struct Scholar {
    name: String,
    age: i32,
    sex: Sex
}

let scholars: Vec<Scholar> = ...;

Kami mengambil vektor anak sekolah dengan menanyakan database, misalnya. Selanjutnya, saya perlu menghitung jumlah gadis di kelas. Jika kita "menelan" vektor melalui `into_iter ()`, maka setelah menghitung kita tidak bisa lagi menggunakan koleksi ini untuk menghitung anak laki-laki:


fn bad_idea() {
    let scholars: Vec<Scholar> = Vec::new();
    let girls_c = scholars
        .into_iter()
        .filter(|s| (*s).sex == Sex::Female)
        .count();

    let boys_c = scholars 
        .into_iter()
        .filter(|s| (*s).sex == Sex::Male)
        .count();
}

Akan ada kesalahan "nilai yang digunakan di sini setelah pindah" pada baris untuk menghitung anak laki-laki. Juga jelas bahwa iterator yang dapat berubah tidak berguna bagi kita. Itulah mengapa ini hanya `iter ()` dan bekerja dengan tautan ganda:


fn good_idea() {
    let scholars: Vec<Scholar> = Vec::new();
    let girls_c = scholars.iter().filter(|s| (**s).sex == Sex::Female).count();
    let boys_c = scholars.iter().filter(|s| (**s).sex == Sex::Male).count();
}

Di sini, untuk meningkatkan jumlah calon potensial di negara ini, diperlukan iterator yang bisa berubah:


fn very_good_idea() {
    let mut scholars: Vec<Scholar> = Vec::new();
    scholars.iter_mut().for_each(|s| (*s).sex = Sex::Male);
}

Mengembangkan ide, kita dapat membuat tentara keluar dari "orang-orang" dan menunjukkan iterator "menyerap":


impl Scholar {
    fn to_soldier(self) -> Soldier {
        Soldier { forgotten_name: self.name, number: some_random_number_generator() }
    }
}

struct Soldier {
    forgotten_name: String,
    number: i32
}

fn good_bright_future() {
    let mut scholars: Vec<Scholar> = Vec::new();
    scholars.iter_mut().for_each(|s| (*s).sex = Sex::Male);
    let soldiers: Vec<Soldier> = scholars.into_iter().map(|s| s.to_soldier()).collect();
    //   scholars,    
}

Pada catatan indah ini, mungkin itu saja.

Pertanyaan terakhir tetap - dari mana dereferencing ganda tautan di `filter` berasal. Faktanya adalah bahwa predikat adalah fungsi yang mengambil referensi ke argumen (agar tidak menangkapnya):


    fn filter<P>(self, predicate: P) -> Filter<Self, P> where
        Self: Sized, P: FnMut(&Self::Item) -> bool,

predikatnya adalah FnMut (secara kasar berbicara fungsi), yang mengambil referensi ke item (mandiri) dan mengembalikan bool. Karena kami sudah memiliki tautan dari iterator `.iter ()`, yang kedua muncul di filter. Ketika diserap oleh iterator (`into_iter`), dereferencing ganda dari tautan berubah menjadi yang biasa.

Kelanjutan


Saya tidak punya banyak pengalaman dalam menulis artikel, jadi saya akan senang mengkritik.
Jika tertarik, saya bisa melanjutkan. Opsi untuk topik:

  • bagaimana dan kapan terjadi deallokasi memori
  • tautan seumur hidup
  • pemrograman asinkron
  • menulis layanan web kecil, Anda bahkan dapat menawarkan api

Tautan


  • buku karat
  • Karena konsep kepemilikan, penerapan hal-hal dasar seperti, misalnya, daftar tertaut tidak lagi sepele. Berikut adalah beberapa cara bagaimana mengimplementasikannya.

More articles:


All Articles