Hlavní navigace

Programovací jazyk Rust: efektivní práce s prvky uloženými v kolekcích

Pavel Tišnovský

Dnes dokončíme popis datových kolekcí ve standardní knihovně Rustu. Nejdříve si řekneme, jak efektivně pracovat s objekty uloženými v kolekcích a pak si popíšeme použití množin s uživatelsky definovanými strukturami.

Obsah

1. Efektivní práce s prvky uloženými v kolekcích

2. Uložení komplexních čísel implementujících trait Drop do kolekce

3. Převod vektoru s komplexními čísly na seznam a problém klonování

4. Implementace traitu Clone

5. První varianta pro obejití nutnosti klonování prvků: „consuming“ iterátor

6. Druhá varianta pro obejití nutnosti klonování prvků: „draining“ iterátor

7. Uložení komplexních čísel do množiny

8. Použití množiny reprezentované hešovací tabulkou

9. Převod obsahu celého vektoru na množinu bez klonování prvků

10. Pokus o vložení stejných prvků do množiny

11. Vložení stejných prvků do množiny bez vytvoření klonů

12. Otázka k zamyšlení

13. Repositář s demonstračními příklady

14. Odkazy na Internetu

1. Efektivní práce s prvky uloženými v kolekcích

V předchozích třech částech tohoto seriálu jsme se seznámili se třemi základními typy datových kolekcí, které jsou dostupné ve standardní knihovně programovacího jazyka Rust. Připomeňme si, že se jedná o takzvané sekvence (konkrétně o seznamy a vektory), mapy a množiny, které jsou doplněny o pole (v Rustu se jedná o primitivní datový typ!). Víme již, jakým způsobem je možné kolekce vytvářet, definovat jejich kapacitu, vkládat do vytvořených kolekcí nové prvky či prvky naopak odstraňovat (či je pouze číst). Dozvěděli jsme se také, jak lze prvky modifikovat s využitím speciálního typu iterátoru.

Ovšem ve chvíli, kdy jsou kolekce rozsáhlejší, tj. když obsahují větší množství prvků, popř. prvky tvořené většími strukturami, je vhodné a někdy i nutné se zaměřit na efektivitu všech prováděných operací. To se týká zejména situace, kdy se například převádí prvky z vektoru do kolekce (to je totiž poměrně často prováděná operace, už jen díky existenci užitečného makra vec!). Musíme si totiž uvědomit, že typový systém Rustu s jeho řízením životnosti (dostupnosti) hodnot mnohdy vede k tomu, že se prvky při převodu mezi vektorem a kolekcí klonují, což není vždy nutné a navíc je to velmi neefektivní jak z časového, tak i paměťového hlediska.

Podívejme se na typický příklad, v němž se provádí klonování prvků:

use std::collections::LinkedList;
 
fn print_list(list: &LinkedList<&str>) {
 
    if list.is_empty() {
        println!("list is empty");
    } else {
        println!("list has {} items", list.len());
    }
 
    for item in list.iter() {
        println!("{}", item);
    }
 
    println!("-------------------------");
}
 
fn main() {
    let list: LinkedList<&str> = vec!["podporucik", "inspektor", "praktikant", "tovarnik"].iter().cloned().collect();
 
    print_list(&list);
}

Výsledek běhu příkladu:

list has 4 items
podporucik
inspektor
praktikant
tovarnik
-------------------------

V tomto příkladu se nejdříve vytvoří vektor s řetězci (přesněji řečeno s referencemi na konstantní řetězce) a posléze se tento vektor převádí přes iterátor na dvojitě vázaný seznam (LinkedList). Zápis je to sice pochopitelný a bez problémů čitelný (najdeme ho i v příručkách k Rustu), ovšem ve skutečnosti se musí každý prvek naklonovat, což zde konkrétně znamená, že se vytvoří další čtyři reference na řetězce, řekněme 4×4 bajty či 4×8 bajtů v závislosti na platformě. Tento problém se ještě zhorší ve chvíli, kdy se do kolekcí ukládají rozsáhlejší datové struktury, což si ukážeme hned v navazující kapitole.

2. Uložení komplexních čísel implementujících trait Drop do kolekce

Zkusme si předchozí příklad upravit takovým způsobem, aby do větší míry odpovídal reálným aplikacím. V tomto seriálu jsme se již mnohokrát setkali s datovou strukturou představující jednu z možných reprezentací komplexních čísel:

struct Complex {
    real: f32,
    imag: f32,
}

Pro tuto strukturu jsme implementovali metody new (forma konstruktoru) a print:

impl Complex {
    fn new(real: f32, imag: f32) -> Complex {
        Complex{real:real, imag:imag}
    }
    fn print(&self) {
        println!("complex number: {:}+{:}i", self.real, self.imag);
    }
}

A navíc tato struktura implementuje trait Drop s metodou drop() volanou ve chvíli, kdy se má objekt uvolnit z paměti:

impl Drop for Complex {
    fn drop(&mut self) {
        println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
    }
}

Vytvoření lineárně vázaného seznamu komplexních čísel je snadné:

let mut list: LinkedList<Complex> = LinkedList::new();
 
list.push_back(Complex::new(0.0, 0.0));
list.push_back(Complex::new(1.0, 1.0));
list.push_back(Complex::new(2.0, 2.0));

Celý příklad může vypadat následovně:

use std::collections::LinkedList;
 
struct Complex {
    real: f32,
    imag: f32,
}
 
impl Complex {
    fn new(real: f32, imag: f32) -> Complex {
        Complex{real:real, imag:imag}
    }
    fn print(&self) {
        println!("complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
impl Drop for Complex {
    fn drop(&mut self) {
        println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
fn print_list(list: &LinkedList<Complex>) {
 
    if list.is_empty() {
        println!("list is empty");
    } else {
        println!("list has {} items", list.len());
    }
 
    for item in list.iter() {
        item.print();
    }
}
 
fn main() {
    let mut list: LinkedList<Complex> = LinkedList::new();
 
    list.push_back(Complex::new(0.0, 0.0));
    list.push_back(Complex::new(1.0, 1.0));
    list.push_back(Complex::new(2.0, 2.0));
 
    print_list(&list);
 
    println!("exit from main()");
}

Po spuštění získáme na standardním výstupu následující řádky ukazující, kdy přesně dochází k dealokaci komplexních čísel:

list has 3 items
complex number: 0+0i
complex number: 1+1i
complex number: 2+2i
exit from main()
Dropping complex number: 0+0i
Dropping complex number: 1+1i
Dropping complex number: 2+2i

3. Převod vektoru s komplexními čísly na seznam a problém klonování

V úvodní kapitole jsme převáděli vektor řetězců (resp. vektor referencí na řetězce) na lineární seznam:

let list: LinkedList<&str> = vec!["podporucik",
                                  "inspektor",
                                  "praktikant",
                                  "tovarnik"].iter().cloned().collect();

Stejnou operaci si samozřejmě můžeme zkusit provést i pro vektor komplexních čísel:

let list: LinkedList<Complex> = vec![Complex::new(0.0, 0.0),
                                     Complex::new(1.0, 1.0),
                                     Complex::new(2.0, 2.0)].iter().cloned().collect();

Podívejme se nyní na úplnou implementaci. Pokuste se sami odpovědět na to, zda je příklad napsaný korektně či nikoli:

use std::collections::LinkedList;
 
struct Complex {
    real: f32,
    imag: f32,
}
 
impl Complex {
    fn new(real: f32, imag: f32) -> Complex {
        Complex{real:real, imag:imag}
    }
    fn print(&self) {
        println!("complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
impl Drop for Complex {
    fn drop(&mut self) {
        println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
fn print_list(list: &LinkedList<Complex>) {
 
    if list.is_empty() {
        println!("list is empty");
    } else {
        println!("list has {} items", list.len());
    }
 
    for item in list.iter() {
        item.print();
    }
}
 
fn main() {
    let list: LinkedList<Complex> = vec![Complex::new(0.0, 0.0),
                                         Complex::new(1.0, 1.0),
                                         Complex::new(2.0, 2.0)].iter().cloned().collect();
 
    print_list(&list);
 
    println!("exit from main()");
}

Problém nastane při pokusu o překlad tohoto příkladu:

error[E0277]: the trait bound `Complex: std::clone::Clone` is not satisfied
  --> 278_sequences39_error.rs:39:73
   |
39 |                                          Complex::new(2.0, 2.0)].iter().cloned().collect();
   |                                                                         ^^^^^^
 
error[E0277]: the trait bound `Complex: std::clone::Clone` is not satisfied
  --> 278_sequences39_error.rs:39:82
   |
39 |                                          Complex::new(2.0, 2.0)].iter().cloned().collect();
   |                                                                                  ^^^^^^^
   |
   = note: required because of the requirements on the impl of `std::iter::Iterator` for `std::iter::Cloned<std::slice::Iter<'_, Complex>>`
 
error: aborting due to 2 previous errors

Překladač se nám snaží naznačit, že není možné volat metodu cloned() na prvky získané iterátorem z vektoru obsahujícího komplexní čísla. Proč to není možné? Napoví nám popis této metody:

Creates an iterator which [clone()]s all of its elements

Pravda je, že struktura komplexních čísel skutečně neimplementuje trait pro klonování, což lze ale snadno napravit.

4. Implementace traitu Clone

Implementace traitu Clone pro komplexní čísla je ve skutečnosti až triviálně jednoduchá, postačuje totiž namísto této deklarace:

struct Complex {
    real: f32,
    imag: f32,
}

použít deklaraci:

#[derive(Clone)]
struct Complex {
    real: f32,
    imag: f32,
}

Nejdříve se pro jistotu podívejme, jak vypadá úplný kód tohoto příkladu a posléze budeme analyzovat jeho výstup:

use std::collections::LinkedList;
 
#[derive(Clone)]
struct Complex {
    real: f32,
    imag: f32,
}
 
impl Complex {
    fn new(real: f32, imag: f32) -> Complex {
        Complex{real:real, imag:imag}
    }
    fn print(&self) {
        println!("complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
impl Drop for Complex {
    fn drop(&mut self) {
        println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
fn print_list(list: &LinkedList<Complex>) {
 
    if list.is_empty() {
        println!("list is empty");
    } else {
        println!("list has {} items", list.len());
    }
 
    for item in list.iter() {
        item.print();
    }
}
 
fn main() {
    let list: LinkedList<Complex> = vec![Complex::new(0.0, 0.0),
                                         Complex::new(1.0, 1.0),
                                         Complex::new(2.0, 2.0)].iter().cloned().collect();
 
    print_list(&list);
 
    println!("exit from main()");
}

Tento příklad již půjde bez problémů přeložit, ovšem nás bude zajímat, jaké zprávy se vytisknou při spuštění programu:

Dropping complex number: 0+0i
Dropping complex number: 1+1i
Dropping complex number: 2+2i
list has 3 items
complex number: 0+0i
complex number: 1+1i
complex number: 2+2i
exit from main()
Dropping complex number: 0+0i
Dropping complex number: 1+1i
Dropping complex number: 2+2i

Povšimněte si, že se metoda drop() volá celkem šestkrát – třikrát na začátku programu, ještě před vytištěním obsahu seznamu a třikrát na konci programu, po opuštění funkce main(). Proč tomu tak je? První tři komplexní čísla byla vytvořena explicitně konstruktorem a vložena do vektoru. Posléze byl získán iterátor vektoru a každý prvek se naklonoval; naklonovaný prvek se uložil do výsledného seznamu. Po zavolání metody collect() již vektor nebyl zapotřebí (neukládali jsme ho do žádné proměnné), takže došlo k jeho automatickému zrušení (destrukci :-) společně se zrušením všech jeho prvků.

5. První varianta pro obejití nutnosti klonování prvků: „consuming“ iterátor

Existuje hned několik možností, jak zabránit „povinnému“ klonování prvků při převodu vektoru (či libovolné jiné kolekce) na seznam či do množiny. Namísto:

let list: LinkedList<Complex> = vec![Complex::new(0.0, 0.0),
                                     Complex::new(1.0, 1.0),
                                     Complex::new(2.0, 2.0)].iter().cloned().collect();

je možné použít poněkud odlišnou konstrukci, která nevytvoří iterátor z vektoru, ale převede vektor na tzv. „consuming“ iterátor, který postupně získává vlastnictví prvků z původní kolekce (namísto „copy“ strategie se použije „move“ strategie). To v našem případě znamená, že vektor bude po provedení všech iterací prázdný, což nám ovšem vůbec nevadí, protože ho stejně nikam nepřiřazujeme:

let list: LinkedList<Complex> = vec![Complex::new(0.0, 0.0),
                                     Complex::new(1.0, 1.0),
                                     Complex::new(2.0, 2.0)].into_iter().collect();

Úplný zdrojový kód upraveného příkladu vypadá takto:

use std::collections::LinkedList;
 
#[derive(Clone)]
struct Complex {
    real: f32,
    imag: f32,
}
 
impl Complex {
    fn new(real: f32, imag: f32) -> Complex {
        Complex{real:real, imag:imag}
    }
    fn print(&self) {
        println!("complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
impl Drop for Complex {
    fn drop(&mut self) {
        println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
fn print_list(list: &LinkedList<Complex>) {
 
    if list.is_empty() {
        println!("list is empty");
    } else {
        println!("list has {} items", list.len());
    }
 
    for item in list.iter() {
        item.print();
    }
}
 
fn main() {
    let list: LinkedList<Complex> = vec![Complex::new(0.0, 0.0),
                                         Complex::new(1.0, 1.0),
                                         Complex::new(2.0, 2.0)].into_iter().collect();
 
    print_list(&list);
 
    println!("exit from main()");
}

O tom, zda se prvky klonují či ne, se snadno přesvědčíme spuštěním příkladu:

list has 3 items
complex number: 0+0i
complex number: 1+1i
complex number: 2+2i
exit from main()
Dropping complex number: 0+0i
Dropping complex number: 1+1i
Dropping complex number: 2+2i

6. Druhá varianta pro obejití nutnosti klonování prvků: „draining“ iterátor

Druhá varianta, jak je možné zabránit klonování prvků a namísto něj provést jejich přesun do jiné kolekce, spočívá v použití takzvaného „draining“ iterátoru. Ten pracuje podobným způsobem jako „consuming“ iterátor, ovšem použitím objektu typu Range lze přesně určit, které prvky se budou ze zdrojové kolekce odstraňovat a přes které se současně bude iterovat. Pokud iterované prvky nezpracujeme (nikam je neuložíme), jsou jednoduše ze zdrojové kolekce odstraněny:

let mut v = vec![Complex::new(0.0, 0.0),
                 Complex::new(1.0, 1.0),
                 Complex::new(2.0, 2.0)];
 
let list: LinkedList<Complex> = v.drain(0..).collect();

V tomto případě není možné použít zápis na jednom řádku, protože by došlo k chybě při pokusu o překlad:

error: borrowed value does not live long enough
 --> <std macros>:3:1
  |
3 | < [ _ ] > :: into_vec ( box [ $ ( $ x ) , * ] ) ) ; ( $ ( $ x : expr , ) * )
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ does not live long enough
test.rs:43:5: 45:45 note: in this expansion of vec! (defined in <std macros>)

Použití „draining“ iterátoru bude vypadat takto:

use std::collections::LinkedList;
 
#[derive(Clone)]
struct Complex {
    real: f32,
    imag: f32,
}
 
impl Complex {
    fn new(real: f32, imag: f32) -> Complex {
        Complex{real:real, imag:imag}
    }
    fn print(&self) {
        println!("complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
impl Drop for Complex {
    fn drop(&mut self) {
        println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
fn print_list(list: &LinkedList<Complex>) {
 
    if list.is_empty() {
        println!("list is empty");
    } else {
        println!("list has {} items", list.len());
    }
 
    for item in list.iter() {
        item.print();
    }
}
 
fn main() {
    let mut v = vec![Complex::new(0.0, 0.0),
                     Complex::new(1.0, 1.0),
                     Complex::new(2.0, 2.0)];
 
    let list: LinkedList<Complex> = v.drain(0..).collect();
 
    print_list(&list);
 
    println!("exit from main()");
}

Snadno se přesvědčíme, že ani v tomto případě nebude docházet ke klonování prvků z původního vektoru:

list has 3 items
complex number: 0+0i
complex number: 1+1i
complex number: 2+2i
exit from main()
Dropping complex number: 0+0i
Dropping complex number: 1+1i
Dropping complex number: 2+2i

7. Uložení komplexních čísel do množiny

Ve druhé části článku si ukážeme, jak lze komplexní čísla uložit do množiny (set). Připomeňme si, že množiny jsou implementovány buď hešovací tabulkou nebo B-stromem. V prvním případě, tj. při použití hešovací tabulky, je nutné, aby struktura představující komplexní čísla implementovala traity Eq, PartialEq a Hash, v případě druhém je navíc nutné implementovat i trait Ord (uspořádání), což je u komplexních čísel poměrně velký (neřešitelný?) problém.

8. Použití množiny reprezentované hešovací tabulkou

Podívejme se nyní na způsob uložení komplexních čísel do množiny reprezentované hešovací tabulkou. Kvůli poslednímu požadavku na implementaci traitu Hash si pro jednoduchost upravme strukturu komplexních čísel tak, aby byla reálná i imaginární složka reprezentována celými čísly, protože pro celá čísla již výpočet hešovací hodnoty existuje (na rozdíl od čísel reálných):

#[derive(Clone)]
struct Complex {
    real: i32,
    imag: i32,
}

Trait PartialEq může být implementován velmi jednoduše porovnáním reálných složek a imaginárních složek dvou komplexních čísel. Toto porovnání plně odpovídá požadavkům na tento trait – symetričnost a tranzitivitu:

impl PartialEq for Complex {
    fn eq(&self, right: &Complex) -> bool {
        self.real == right.real && self.imag == right.imag
    }
}

Zatímco implementace traitu PartialEq byla jednoduchá, implementace traitu Eq je triviální, protože překladači stačí pouze oznámit, že je tento trait podporován:

impl Eq for Complex {
}

Nejsložitější je implementace traitu Hash. V tomto traitu je předepsána metoda hash(), která kupodivu nic nevrací (jak jste možná zvyklí z jiných knihoven a jazyků), ale jen upravuje stav postupně počítaného otisku. Při implementaci můžeme využít faktu, že pro celá čísla je trait Hash plně implementován, takže například pro reálnou složku lze zavolat metodu self.real.hash(state), která upravuje měnitelnou (mutable) hodnotu state:

impl Hash for Complex {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.real.hash(state);
        self.imag.hash(state);
    }
}

Druhou možností je pouze specifikace #[derive(Hash)] pro naši implementaci komplexních čísel.

#[derive(Clone, Hash)]
struct Complex {
    real: i32,
    imag: i32,
}

Poznámka: současně je nutné zaručit, že pokud se komplexní číslo A rovná komplexnímu číslu B (což se zjišťuje přes traity PartialEq a Eq), musí současně platit i Hash(A)==Hash(B). To je v našem případě samozřejmě zaručeno, ovšem pokud se budete snažit implementovat nějaký „zajímavější“ způsob porovnání, například řetězců podle jejich délky, je nutné si dávat pozor, jinak nebude práce s kolekcemi korektní.

Podívejme se nyní, jak lze jednoduše vytvořit množinu s komplexními čísly:

use std::collections::HashSet;
use std::hash::Hash;
use std::hash::Hasher;
 
#[derive(Clone)]
struct Complex {
    real: i32,
    imag: i32,
}
 
impl Complex {
    fn new(real: i32, imag: i32) -> Complex {
        Complex{real:real, imag:imag}
    }
    fn print(&self) {
        println!("complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
impl Drop for Complex {
    fn drop(&mut self) {
        println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
impl PartialEq for Complex {
    fn eq(&self, right: &Complex) -> bool {
        self.real == right.real && self.imag == right.imag
    }
}
 
impl Eq for Complex {
}
 
impl Hash for Complex {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.real.hash(state);
        self.imag.hash(state);
    }
}
 
fn print_set(set: &HashSet<Complex>) {
 
    if set.is_empty() {
        println!("set is empty");
    } else {
        println!("set has {} items", set.len());
    }
 
    for item in set.iter() {
        item.print();
    }
}
 
fn main() {
    let set: HashSet<Complex> = vec![Complex::new(0, 0),
                                     Complex::new(1, 1),
                                     Complex::new(2, 2)].iter().cloned().collect();
 
    print_set(&list);
 
    println!("exit from main()");
}

Po spuštění tohoto příkladu se na standardní výstup vypíšou následující řádky:

Dropping complex number: 0+0i
Dropping complex number: 1+1i
Dropping complex number: 2+2i
set has 3 items
complex number: 1+1i
complex number: 0+0i
complex number: 2+2i
exit from main()
Dropping complex number: 2+2i
Dropping complex number: 0+0i
Dropping complex number: 1+1i

Proč je vytvořeno a posléze odstraněno šest komplexních čísel již víme – provádí se klonování prvků při převodu vektoru na množinu.

9. Převod obsahu celého vektoru na množinu bez klonování prvků

Pokud potřebujeme převést celý vektor na množinu bez (zbytečného) klonování prvků, můžeme použít již osvědčenou metodu into_iter() převádějící vlastnictví prvků z vektoru přímo do iterátoru:

use std::collections::HashSet;
use std::hash::Hash;
use std::hash::Hasher;
 
#[derive(Clone)]
struct Complex {
    real: i32,
    imag: i32,
}
 
impl Complex {
    fn new(real: i32, imag: i32) -> Complex {
        Complex{real:real, imag:imag}
    }
    fn print(&self) {
        println!("complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
impl Drop for Complex {
    fn drop(&mut self) {
        println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
impl PartialEq for Complex {
    fn eq(&self, right: &Complex) -> bool {
        self.real == right.real && self.imag == right.imag
    }
}
 
impl Eq for Complex {
}
 
impl Hash for Complex {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.real.hash(state);
        self.imag.hash(state);
    }
}
 
fn print_set(set: &HashSet<Complex>) {
 
    if set.is_empty() {
        println!("set is empty");
    } else {
        println!("set has {} items", set.len());
    }
 
    for item in set.iter() {
        item.print();
    }
}
 
fn main() {
    let set: HashSet<Complex> = vec![Complex::new(0, 0),
                                     Complex::new(1, 1),
                                     Complex::new(2, 2)].into_iter().collect();
 
    print_set(&set);
 
    println!("exit from main()");
}

O tom, že ke klonování skutečně nedochází, se snadno přesvědčíme:

set has 3 items
complex number: 1+1i
complex number: 0+0i
complex number: 2+2i
exit from main()
Dropping complex number: 2+2i
Dropping complex number: 0+0i
Dropping complex number: 1+1i

10. Pokus o vložení stejných prvků do množiny

Upravme si nepatrně předchozí příklad tak, že ve vektoru (převáděného na množinu) budou shodné prvky, tj. prvky, pro něž metoda eq vrátí True:

let set: HashSet<Complex> = vec![Complex::new(0, 0),
                                 Complex::new(1, 1),
                                 Complex::new(0, 0),
                                 Complex::new(1, 1),
                                 Complex::new(2, 2),
                                 Complex::new(2, 2)].iter().cloned().collect();

Po spuštění takto upraveného příkladu uvidíme, že na začátku došlo k vytvoření klonů všech šesti prvků. Následně se tři z těchto klonů převedly do výsledné množiny, kdežto druhá trojice klonů byla prakticky ihned po jejich vzniku odstraněna (zvýrazněno). To je sice korektní chování (v množině nelze mít dva shodné prvky), ovšem z paměťového i výpočetního hlediska se jedná o velmi neefektivní způsob:

Dropping complex number: 0+0i
Dropping complex number: 1+1i
Dropping complex number: 2+2i
Dropping complex number: 0+0i
Dropping complex number: 1+1i
Dropping complex number: 0+0i
Dropping complex number: 1+1i
Dropping complex number: 2+2i
Dropping complex number: 2+2i
set has 3 items
complex number: 1+1i
complex number: 2+2i
complex number: 0+0i
exit from main()
Dropping complex number: 0+0i
Dropping complex number: 2+2i
Dropping complex number: 1+1i

Úplný zdrojový kód příkladu vypadá následovně:

use std::collections::HashSet;
use std::hash::Hash;
use std::hash::Hasher;
 
#[derive(Clone)]
struct Complex {
    real: i32,
    imag: i32,
}
 
impl Complex {
    fn new(real: i32, imag: i32) -> Complex {
        Complex{real:real, imag:imag}
    }
    fn print(&self) {
        println!("complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
impl Drop for Complex {
    fn drop(&mut self) {
        println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
impl PartialEq for Complex {
    fn eq(&self, right: &Complex) -> bool {
        self.real == right.real && self.imag == right.imag
    }
}
 
impl Eq for Complex {
}
 
impl Hash for Complex {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.real.hash(state);
        self.imag.hash(state);
    }
}
 
fn print_set(set: &HashSet<Complex>) {
 
    if set.is_empty() {
        println!("set is empty");
    } else {
        println!("set has {} items", set.len());
    }
 
    for item in set.iter() {
        item.print();
    }
}
 
fn main() {
    let set: HashSet<Complex> = vec![Complex::new(0, 0),
                                     Complex::new(1, 1),
                                     Complex::new(0, 0),
                                     Complex::new(1, 1),
                                     Complex::new(2, 2),
                                     Complex::new(2, 2)].iter().cloned().collect();
 
    print_set(&set);
 
    println!("exit from main()");
}

11. Vložení stejných prvků do množiny bez vytvoření klonů

Pokud provedeme převod vektoru na množinu bez klonování prvků, bude chování poněkud odlišné – tři prvky, které již v množině existují (byly do ní vloženy při předchozí iteraci), jsou odstraněny ještě před vytištěním obsahu množiny, další tři prvky převedené do množiny jsou odstraněny až při odchodu z funkce main:

Dropping complex number: 0+0i
Dropping complex number: 1+1i
Dropping complex number: 2+2i
set has 3 items
complex number: 0+0i
complex number: 1+1i
complex number: 2+2i
exit from main()
Dropping complex number: 2+2i
Dropping complex number: 1+1i
Dropping complex number: 0+0i

Úplný zdrojový kód příkladu vypadá následovně:

use std::collections::HashSet;
use std::hash::Hash;
use std::hash::Hasher;
 
#[derive(Clone)]
struct Complex {
    real: i32,
    imag: i32,
}
 
impl Complex {
    fn new(real: i32, imag: i32) -> Complex {
        Complex{real:real, imag:imag}
    }
    fn print(&self) {
        println!("complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
impl Drop for Complex {
    fn drop(&mut self) {
        println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
impl PartialEq for Complex {
    fn eq(&self, right: &Complex) -> bool {
        self.real == right.real && self.imag == right.imag
    }
}
 
impl Eq for Complex {
}
 
impl Hash for Complex {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.real.hash(state);
        self.imag.hash(state);
    }
}
 
fn print_set(set: &HashSet<Complex>) {
 
    if set.is_empty() {
        println!("set is empty");
    } else {
        println!("set has {} items", set.len());
    }
 
    for item in set.iter() {
        item.print();
    }
}
 
fn main() {
    let set: HashSet<Complex> = vec![Complex::new(0, 0),
                                     Complex::new(1, 1),
                                     Complex::new(0, 0),
                                     Complex::new(1, 1),
                                     Complex::new(2, 2),
                                     Complex::new(2, 2)].into_iter().collect();
 
    print_set(&set);
 
    println!("exit from main()");
}

12. Otázka k zamyšlení

Pokud by se namísto množiny reprezentované hešovací tabulkou použila množina reprezentovaná B-stromem, musela by naše struktura komplexních čísel reprezentovat trait Ord, což je kontrolováno překladačem:

impl Ord for Complex {
    fn cmp(&self, other: &Complex) -> Ordering {
        ???
        ???
        ???
    }
}

Jak by bylo možné tento trait implementovat? Existuje vůbec nějaký rozumný způsob?

13. Repositář s demonstračními příklady

Všechny dnes popisované demonstrační příklady byly, podobně jako ve všech předchozích částech tohoto seriálu, uloženy do Git repositáře dostupného na adrese https://github.com/tisnik/pre­sentations. Příklady si můžete v případě potřeby stáhnout i jednotlivě bez nutnosti klonovat celý repositář:

14. Odkazy na Internetu

  1. Struct std::collections::HashSet
    https://doc.rust-lang.org/std/collections/struc­t.HashSet.html
  2. Struct std::collections::BTreeSet
    https://doc.rust-lang.org/std/collections/struc­t.BTreeSet.html
  3. Struct std::collections::BinaryHeap
    https://doc.rust-lang.org/std/collections/struc­t.BinaryHeap.html
  4. Set (abstract data type)
    https://en.wikipedia.org/wi­ki/Set_%28abstract_data_ty­pe%29#Language_support
  5. Associative array
    https://en.wikipedia.org/wi­ki/Associative_array
  6. Hash Table
    https://en.wikipedia.org/wi­ki/Hash_table
  7. B-tree
    https://en.wikipedia.org/wiki/B-tree
  8. Pedro Celis: Robin Hood Hashing (naskenované PDF!)
    https://cs.uwaterloo.ca/re­search/tr/1986/CS-86–14.pdf
  9. Robin Hood hashing
    http://codecapsule.com/2013/11/11/ro­bin-hood-hashing/
  10. Robin Hood hashing: backward shift deletion
    http://codecapsule.com/2013/11/17/ro­bin-hood-hashing-backward-shift-deletion/
  11. Module std::collections
    https://doc.rust-lang.org/std/collections/
  12. Module std::vec
    https://doc.rust-lang.org/nightly/std/vec/index.html
  13. Struct std::collections::VecDeque
    https://doc.rust-lang.org/std/collections/struc­t.VecDeque.html
  14. Struct std::collections::LinkedList
    https://doc.rust-lang.org/std/collections/struc­t.LinkedList.html
  15. Module std::fmt
    https://doc.rust-lang.org/std/fmt/
  16. Macro std::println
    https://doc.rust-lang.org/std/macro.println.html
  17. Enum std::result::Result
    https://doc.rust-lang.org/std/result/enum.Result.html
  18. Module std::result
    https://doc.rust-lang.org/std/result/
  19. Result
    http://rustbyexample.com/std/re­sult.html
  20. Rust stdlib: Option
    https://doc.rust-lang.org/std/option/enum.Option.html
  21. Module std::option
    https://doc.rust-lang.org/std/option/index.html
  22. Rust by example: option
    http://rustbyexample.com/std/op­tion.html
  23. Rust by example: if-let
    http://rustbyexample.com/flow_con­trol/if_let.html
  24. Rust by example: while let
    http://rustbyexample.com/flow_con­trol/while_let.html
  25. Rust by example: Option<i32>
    http://rustbyexample.com/std/op­tion.html
  26. An Overview of Macros in Rust
    http://words.steveklabnik.com/an-overview-of-macros-in-rust
  27. A Practical Intro to Macros in Rust 1.0
    https://danielkeep.github.io/practical-intro-to-macros.html
  28. The Rust Programming Language: macros
    https://doc.rust-lang.org/beta/book/macros.html
  29. Rust by example: 15 macro_rules!
    http://rustbyexample.com/macros.html
  30. Primitive Type isize
    https://doc.rust-lang.org/nightly/std/primi­tive.isize.html
  31. Primitive Type usize
    https://doc.rust-lang.org/nightly/std/primi­tive.usize.html
  32. Primitive Type array
    https://doc.rust-lang.org/nightly/std/primi­tive.array.html
  33. Module std::slice
    https://doc.rust-lang.org/nightly/std/slice/
  34. Rust by Example: 2.3 Arrays and Slices
    http://rustbyexample.com/pri­mitives/array.html
  35. What is the difference between Slice and Array (stackoverflow)
    http://stackoverflow.com/qu­estions/30794235/what-is-the-difference-between-slice-and-array
  36. Learning Rust With Entirely Too Many Linked Lists
    http://cglab.ca/~abeinges/blah/too-many-lists/book/
  37. Testcase: linked list
    http://rustbyexample.com/cus­tom_types/enum/testcase_lin­ked_list.html
  38. Operators and Overloading
    https://doc.rust-lang.org/book/operators-and-overloading.html
  39. Module std::ops
    https://doc.rust-lang.org/std/ops/index.html
  40. Module std::cmp
    https://doc.rust-lang.org/std/cmp/index.html
  41. Trait std::ops::Add
    https://doc.rust-lang.org/stable/std/ops/trait.Add.html
  42. Trait std::ops::AddAssign
    https://doc.rust-lang.org/std/ops/trait.AddAssign.html
  43. Trait std::ops::Drop
    https://doc.rust-lang.org/std/ops/trait.Drop.html
  44. Trait std::cmp::Eq
    https://doc.rust-lang.org/std/cmp/trait.Eq.html
  45. Struct std::boxed::Box
    https://doc.rust-lang.org/std/boxed/struct.Box.html
  46. Explore the ownership system in Rust
    https://nercury.github.io/rus­t/guide/2015/01/19/ownership­.html
  47. Rust's ownership and move semantic
    http://www.slideshare.net/sa­neyuki/rusts-ownership-and-move-semantics
  48. Trait std::marker::Copy
    https://doc.rust-lang.org/stable/std/marker/tra­it.Copy.html
  49. Trait std::clone::Clone
    https://doc.rust-lang.org/stable/std/clone/tra­it.Clone.html
  50. The Stack and the Heap
    https://doc.rust-lang.org/book/the-stack-and-the-heap.html
  51. Rust Compare: Pointers & References
    http://www.rust-compare.com/site/pointers.html
  52. Rust Compare: Parameters
    http://www.rust-compare.com/site/params.html
  53. Why does this compile? Automatic dereferencing?
    https://users.rust-lang.org/t/why-does-this-compile-automatic-dereferencing/2183
  54. Understanding Pointers, Ownership, and Lifetimes in Rust
    http://koerbitz.me/posts/Understanding-Pointers-Ownership-and-Lifetimes-in-Rust.html
  55. Rust lang series episode #25 — pointers (#rust-series)
    https://steemit.com/rust-series/@jimmco/rust-lang-series-episode-25-pointers-rust-series
  56. Rust – home page
    https://www.rust-lang.org/en-US/
  57. Rust – Frequently Asked Questions
    https://www.rust-lang.org/en-US/faq.html
  58. Destructuring and Pattern Matching
    https://pzol.github.io/get­ting_rusty/posts/20140417_des­tructuring_in_rust/
  59. The Rust Programming Language
    https://doc.rust-lang.org/book/
  60. Rust (programming language)
    https://en.wikipedia.org/wi­ki/Rust_%28programming_lan­guage%29
  61. Go – home page
    https://golang.org/
  62. Stack Overflow – Most Loved, Dreaded, and Wanted language
    https://stackoverflow.com/re­search/developer-survey-2016#technology-most-loved-dreaded-and-wanted
  63. Rust vs Go (dva roky staré hodnocení, od té doby došlo k posunům v obou jazycích)
    http://jaredforsyth.com/2014/03/22/rust-vs-go/
  64. Rust vs Go: My experience
    https://www.reddit.com/r/go­lang/comments/21m6jq/rust_vs_go_my_ex­perience/
  65. Friends of Rust (Organizations running Rust in production)
    https://www.rust-lang.org/en-US/friends.html
  66. Rust programs versus C++ g++
    https://benchmarksgame.ali­oth.debian.org/u64q/compa­re.php?lang=rust&lang2=gpp
  67. Další benchmarky (nejedná se o reálné příklady „ze života“)
    https://github.com/kostya/benchmarks
  68. Go na Redditu
    https://www.reddit.com/r/golang/
  69. Rust vs. Go
    http://vschart.com/compare/rust/vs/go-language
  70. Abstraction without overhead: traits in Rust
    https://blog.rust-lang.org/2015/05/11/traits.html
  71. Method Syntax
    https://doc.rust-lang.org/book/method-syntax.html
  72. Traits in Rust
    https://doc.rust-lang.org/book/traits.html
  73. Functional Programming in Rust – Part 1 : Function Abstraction
    http://blog.madhukaraphatak­.com/functional-programming-in-rust-part-1/
  74. Of the emerging systems languages Rust, D, Go and Nim, which is the strongest language and why?
    https://www.quora.com/Of-the-emerging-systems-languages-Rust-D-Go-and-Nim-which-is-the-strongest-language-and-why
  75. Chytré ukazatele (moderní verze jazyka C++) [MSDN]
    https://msdn.microsoft.com/cs-cz/library/hh279674.aspx
  76. UTF-8 Everywhere
    http://utf8everywhere.org/
  77. Rust by Example
    http://rustbyexample.com/
  78. Rust oficiálně ve Fedoře
    https://mojefedora.cz/rust-oficialne-ve-fedore/
  79. Resource acquisition is initialization
    https://en.wikipedia.org/wi­ki/Resource_acquisition_is_i­nitialization
  80. TIOBE index (October 2016)
    http://www.tiobe.com/tiobe-index/
  81. Porovnání Go, D a Rustu na OpenHubu:
    https://www.openhub.net/lan­guages/compare?language_na­me[]=-1&language_name[]=-1&language_name[]=dmd&lan­guage_name[]=golang&langu­age_name[]=rust&language_na­me[]=-1&measure=commits
  82. String Types in Rust
    http://www.suspectsemantic­s.com/blog/2016/03/27/str­ing-types-in-rust/
  83. Trait (computer programming)
    https://en.wikipedia.org/wi­ki/Trait_%28computer_program­ming%29
  84. Type inference
    https://en.wikipedia.org/wi­ki/Type_inference
Našli jste v článku chybu?
10. 4. 2017 0:01
ded.kenedy (neregistrovaný)

Chápu-li dobře, tak proto je možno (někdy nutno) definovat i PartialEq, PartialOrd a partrial_cmp, které dělají to lidské (ve smyslu praxe, reality) porovnávání.

Nechapes to dobre, neni zadne matematicke a lidske porovnani. Jsou algoritmy a problemy u nichz ti staci znat castecne usporadani (napr. relace byt pod mnozinou) a jsou problemy, kdy potrebujes mit uplne usporadani (napr. lexikograficke usporadani mnozin), ktere ma striktnejsi podminky. Pricemz, jak uz jsem psal vyse, pokud mas nejake …

9. 4. 2017 18:28
xxxxx (neregistrovaný)

Tak co jsem se tak díval kolem, tak mi to připadá, že rust si je vědom těch praktických problémů při porovnávání.

Chápu-li dobře, tak proto je možno (někdy nutno) definovat i PartialEq, PartialOrd a partrial_cmp, které dělají to lidské (ve smyslu praxe, reality) porovnávání. V nich je možno vracet duplicity či None (nejde-li porovnat) a podobně. A ty si mohu používat při svých porovnáváních.

Kdežto čisté Ord (resp. Eq, Hash) jsou určeny vnitřně pro rust, aby umožnily definovat úplné uspořádání…