Programovací jazyk Rust: binární halda, použití TCP

13. 4. 2017

Doba čtení: 18 minut

Líbí se vám článek?
Podpořte redakci

Poslední datovou strukturou ve standardní knihovně jazyka Rust je takzvaná binární halda, kterou si dnes podrobněji popíšeme. V závěru článku se navíc zmíníme o podpoře TCP v základní knihovně Rustu.

Obsah

1. Datová struktura BinaryHeap (binární halda)

2. Interní implementace binární haldy

3. Časová složitost základních operací s binární haldou

4. Triviální příklad použití binární haldy

5. Problematika uspořádání prvků

6. Iterátor pro BinaryHeap versus funkce pop()

7. Převod prvků z binární haldy do vektoru

8. Převod prvků do setříděného vektoru

9. Postupný přesun prvků z binární haldy s použitím funkce drain()

10. Podpora TCP v základní knihovně programovacího jazyka Rust

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

12. Odkazy na Internetu

1. Datová struktura BinaryHeap (binární halda)

Poslední datovou strukturou, která je ve standardní knihovně programovacího jazyka Rust zařazena mezi datové kolekce, je takzvaná binární halda neboli binary heap. Interně je binární halda, jakožto konkrétní implementace strukturovaného datového typu haldy (viz poznámka níže), reprezentována speciálně uloženým binárním stromem, na nějž jsou vztažena další dvě omezení:

Až na poslední úroveň musí být binární strom vyvážený. Poslední úroveň může být buď kompletní (potom je pochopitelně celý binární strom vyvážený) nebo nekompletní. V případě, že je poslední úroveň nekompletní, naplňují se uzly na této úrovni zleva doprava.
Hodnota uložená v každém uzlu takového binárního stromu musí být větší nebo rovna hodnotám uloženým v potomcích uzlu. Naproti tomu tato vlastnost nijak přesněji nespecifikuje, jak (a zda vůbec) musí být potomci daného uzlu uspořádáni. Pokud například oba potomky nějakého uzlu prohodíme, jedná se o zcela korektní operaci, která nijak toto pravidlo (omezení) neporuší.

Samozřejmě platí, že podmínka větší nebo rovna je volitelná, přesněji řečeno si programátor sám může zvolit funkci, která tuto podmínku testuje. Pro tento účel se používá trait str::cmp::Ord (https://doc.rust-lang.org/std/cmp/trait.Ord.html).

Poznámka: pojem halda (heap) má v kontextu programovacího jazyka Rust minimálně dva významy. Označuje se jím jak datová struktura popsaná výše, tak i ta část operační paměti, která je využívána pro alokaci dynamické paměti (resp. dynamických proměnných).

Poznámka²: halda jakožto datová struktura musí splňovat takzvanou vlastnost haldy: pokud je B potomek A, pak platí x(A) >= x(B). To znamená, že v kořenu stromu je vždy umístěn prvek s nejvyšším klíčem.

2. Interní implementace binární haldy

Existuje několik způsobů implementace binární haldy. Samozřejmě se skutečně může jednat o klasický binární strom, tj. o datovou strukturu obsahující uzly, přičemž každý uzel obsahuje ukazatele na své dva potomky. Ovšem v praxi se setkáme spíše s implementací binární haldy pomocí pole nebo v případě programovacího jazyka Rust s využitím vektoru. To je umožněno díky prvnímu požadavku na binární strom reprezentující haldu: až na poslední úroveň musí být binární strom vyvážený. Tato alternativní reprezentace, v níž není nutné používat ukazatele ani reference, s sebou samozřejmě přináší mnohé výhody, především pak menší nároky na operační paměť, rychlejší přístup k prvkům haldy a lepší využití L1 i L2 cache (což je možná dnes zdaleka nejdůležitější). Konkrétně v Rustu je reprezentace binární haldy následující:

pub struct BinaryHeap<T> {
    data: Vec<T>,
}

Poznámka: počet uzlů se zjistí jednoduše použitím metody len() pro vektor.

Jak však reprezentace binární haldy pomocí pole nebo vektoru vypadá? První prvek v poli či vektoru obsahuje kořen, tj. prvek s maximální hodnotou (podle druhé podmínky z předchozí kapitoly). Následující dva prvky pole/vektoru obsahují přímé potomky kořenového prvku. Další maximálně čtyři prvky pole/vektoru obsahují potomky předchozích dvou uzlů (potomků kořene) a tak dále až do dosažení potřebného počtu prvků. Lze snadno zjistit, že pro prvek uložený v poli/vektoru na indexu n budou jeho potomci uloženi na pozici 2n+1 a 2n+2. Pro kořen s indexem n=0 jsou jeho potomci skutečně uloženi na pozicích 2×0+1=1 a 2×0+2=2. První z těchto uzlů s indexem/pozicí n=1 má potomky na pozicích 2×1+1=3 a 2×1+2=4 atd. Podívejme se ostatně na ilustrační obrázek:

Obrázek 1: Interní reprezentace haldy.
Zdroj: Wikipedia

Poznámka: právě z tohoto způsobu uložení plyne nutnost naplňovat poslední úroveň stromu zleva doprava.

3. Časová složitost základních operací s binární haldou

Nejdůležitější praktickou vlastností binární haldy je zjištění prvku s maximální hodnotou v konstantním čase, protože tento prvek musí být uložen v kořenu stromu. Mj. i z tohoto důvodu se binární haldy používají pro implementaci prioritních front a podobných užitečných struktur. V následující tabulce jsou vypsány časové složitosti dalších často používaných operací. Nejhorší složitost má operace pro sloučení dvou binárních hald, zatímco vložení či vyjmutí prvku je operace se „slušnou“ logaritmickou složitostí (je tomu tak z toho důvodu, že log n odpovídá výšce stromu):

Operace	Časová složitost
Stavba haldy	O(n)
Získání hodnoty kořene	O(1)
Vyjmutí kořene z haldy	O(log n)
Vložení prvku do haldy	O(log n)
Odstranění prvku z haldy	O(log n)
Sloučení 2 hald	O(n1 + n2)

Algoritmus pro vkládání prvku do binární haldy je popsán na Wikipedii.

4. Triviální příklad použití binární haldy

Do binární haldy je možné ukládat jakékoli datové typy implementující již výše zmíněný trait Ord. To se týká i řetězců, takže se podívejme na velmi jednoduchý příklad, v němž do binární haldy vložíme pětici řetězců (ve skutečnosti se vkládají reference na konstantní řetězce). Povšimněte si, že podobně jako u dalších typů kolekcí, si typ prvků odvodí překladač automaticky po první operaci heap.push(). Pro jednoduchost prvky z haldy získáváme s využitím iterátoru:

use std::collections::BinaryHeap;
 
fn main() {
    let mut heap = BinaryHeap::new();
 
    heap.push("Trachta");
    heap.push("Hlavacek");
    heap.push("Bierhanzel");
    heap.push("Meyer");
    heap.push("Vaclav Kotek");
 
    for item in &heap {
        println!("{}", item);
    }
}

Po spuštění tohoto příkladu získáme následující výstup. Povšimněte si, že pořadí prvků je (pseudo)náhodné:

Vaclav Kotek
Trachta
Bierhanzel
Hlavacek
Meyer

5. Problematika uspořádání prvků

V předchozí části tohoto seriálu zazněla otázka, jak by bylo možné uspořádat prvky představující komplexní čísla. Pokud totiž budeme chtít komplexní čísla vložit do binární haldy, je vyžadována implementace traitu Ord. Jedno z možných (špatných :-) řešení může vypadat následovně. Implementujeme traity Ord a PartialOrd (povšimněte si, jaké datové typy vrací metody cmp a partial_cmp):

impl Ord for Complex {
    fn cmp(&self, other: &Complex) -> Ordering {
        self.real.cmp(&other.real)
    }
}
 
impl PartialOrd for Complex {
    fn partial_cmp(&self, other: &Complex) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

Volání self.real.cmp() je možné z toho důvodu, že tato metoda (a trait Cmp) pro celá čísla existuje (pro čísla s plovoucí řádovou čárkou však nikoli):

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

Navíc ještě implementujeme trait Eq a PartialEq:

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

Program, který vloží několik komplexních čísel do binární haldy, může vypadat následovně:

use std::collections::BinaryHeap;
use std::cmp::Ordering;
 
#[derive(Clone, Debug)]
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 Ord for Complex {
    fn cmp(&self, other: &Complex) -> Ordering {
        self.real.cmp(&other.real)
    }
}
 
impl PartialOrd for Complex {
    fn partial_cmp(&self, other: &Complex) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
 
impl PartialEq for Complex {
    fn eq(&self, other: &Complex) -> bool {
        self.real == other.real
    }
}
 
impl Eq for Complex {}
 
impl Drop for Complex {
    fn drop(&mut self) {
        println!("Dropping complex number: {:}+{:}i", self.real, self.imag);
    }
}
 
fn main() {
    let mut heap = BinaryHeap::new();
 
    heap.push(Complex::new(0, 0));
    heap.push(Complex::new(1, 1));
    heap.push(Complex::new(0, 0));
    heap.push(Complex::new(1, 1));
    heap.push(Complex::new(2, 2));
 
    println!("max: {:?}", heap.peek());
    for item in &heap {
        item.print();
    }
}

Povšimněte si, že zavoláním heap.peek() můžeme získat maximální prvek v binární haldě, tj. vlastně kořen stromu:

max: Some(Complex { real: 2, imag: 2 })
complex number: 2+2i
complex number: 1+1i
complex number: 0+0i
complex number: 0+0i
complex number: 1+1i
Dropping complex number: 2+2i
Dropping complex number: 1+1i
Dropping complex number: 0+0i
Dropping complex number: 0+0i
Dropping complex number: 1+1i

Komplexní čísla jsou opět vrácena v obecně náhodném pořadí.

6. Iterátor pro BinaryHeap versus funkce pop()

Zkusme nyní do binární haldy ukládat celá čísla, pro něž je uspořádání triviální. Nejprve do haldy vložíme devět hodnot v zadaném pořadí, následně získáme prvek s maximální hodnotou, posléze vypíšeme prvky v pořadí vráceném iterátorem a na závěr použijeme metodu pop() pro postupné čtení prvků z haldy:

use std::collections::BinaryHeap;
 
fn main() {
    let mut heap = BinaryHeap::new();
 
    heap.push(1);
    heap.push(2);
    heap.push(3);
    heap.push(4);
    heap.push(100);
    heap.push(5);
    heap.push(6);
    heap.push(7);
    heap.push(8);
 
    println!("max value: {:?}", heap.peek());
 
    for item in &heap {
        println!("{}", item);
    }
 
    for _ in 0..heap.len()+1 {
        println!("{:?}", heap.pop());
    }
 
}

Podívejme se na výstup tohoto programu. Maximální prvek je vrácen jako hodnota typu Option (None/Some), následně přes iterátor získáme prvky v obecně náhodném pořadí a metoda pop() postupně vrátí prvky setříděné podle jejich velikosti. Pokud se dojde na konec haldy, vrátí se hodnota None (nedojde však k žádné výjimce):

max value: Some(100)
100
8
6
7
3
2
5
1
4
Some(100)
Some(8)
Some(7)
Some(6)
Some(5)
Some(4)
Some(3)
Some(2)
Some(1)
None

7. Převod prvků z binární haldy do vektoru

Binární halda implementuje metodu nazvanou into_vec(), která dokáže převést haldu na vektor. Vzhledem k tomu, že již víme, že halda je implementována vektorem, je tato operace pravděpodobně provedena velmi rychle:

use std::collections::BinaryHeap;
 
fn main() {
    let mut heap = BinaryHeap::new();
 
    heap.push(1);
    heap.push(2);
    heap.push(3);
    heap.push(4);
    heap.push(100);
    heap.push(5);
    heap.push(6);
    heap.push(7);
    heap.push(8);
 
    println!("max value: {:?}", heap.peek());
 
    let vec = heap.into_vec();
 
    for item in &vec {
        println!("{}", item);
    }
}

Prvky výsledného vektoru jsou obecně vráceny v náhodném pořadí. Přesněji řečeno není pořadí zcela náhodné, protože první prvek bude mít maximální hodnotu, ale další pořadí již není pevně dané:

max value: Some(100)
100
8
6
7
3
2
5
1
4

8. Převod prvků do setříděného vektoru

Mnohem častěji budeme vyžadovat převod binární haldy do vektoru, ovšem takovým způsobem, aby byly jeho prvky vzestupně setříděny. K tomuto účelu dobře poslouží metoda nazvaná into_sorted_vec(), jejíž implementace však není tak triviální, jako tomu bylo u metody into_vec():

use std::collections::BinaryHeap;
 
fn main() {
    let mut heap = BinaryHeap::new();
 
    heap.push(1);
    heap.push(2);
    heap.push(3);
    heap.push(4);
    heap.push(100);
    heap.push(5);
    heap.push(6);
    heap.push(7);
    heap.push(8);
 
    println!("max value: {:?}", heap.peek());
 
    let vec = heap.into_sorted_vec();
 
    for item in &vec {
        println!("{}", item);
    }
}

Z výsledného výpisu je patrné, že prvky jsou skutečně vráceny setříděné:

max value: Some(100)
1
2
3
4
5
6
7
8
100

9. Postupný přesun prvků z binární haldy s použitím funkce drain()

Již minule jsme se zmiňovali o funkci pojmenované drain(), díky níž je možné postupně zpracovávat prvky z datových kolekcí bez nutnosti jejich klonování. Tato funkce samozřejmě existuje i pro binární haldu, takže se jen rychle podívejme na příklad jejího použití:

use std::collections::BinaryHeap;
 
fn main() {
    let mut heap = BinaryHeap::new();
 
    heap.push(1);
    heap.push(2);
    heap.push(3);
    heap.push(4);
    heap.push(100);
    heap.push(5);
    heap.push(6);
    heap.push(7);
    heap.push(8);
 
    println!("max value: {:?}", heap.peek());
 
    let iter = heap.drain();
 
    for item in iter {
        println!("{}", item);
    }
}

Výsledek bude shodný s použitím metody iter(), protože prvky budou zpracovány v tom pořadí, v jakém jsou uloženy do vektoru:

max value: Some(100)
100
8
6
7
3
2
5
1
4

10. Podpora TCP v základní knihovně programovacího jazyka Rust

Ve standardní knihovně programovacího jazyka Rust nalezneme i podporu pro práci s TCP. To mj. znamená, že je možné relativně snadno tvořit aplikace běžící v režimu serveru (s nasloucháním na zvoleném portu či portech) či v režimu klienta (který se připojuje k serveru). Základními datovými strukturami, které se v tomto případě používají, jsou struktury TcpListener a TcpStream. Názvy těchto struktur napovídají, jak se používají – TcpListener slouží pro implementaci jednoduchého serveru, TcpStream pak představuje objekt zajišťující obousměrný přenos dat mezi klientem a serverem.

Podívejme se nyní na příklad velmi jednoduchého serveru, který naslouchá na portu 1234 a který realizuje odpovědi v jediném vláknu (což může být samozřejmě omezující). Číslo portu je větší než 1024, takže ho může otevřít i aplikace bez rootovských práv. Listener se vytvoří triviálně (zejména v porovnání s tím, co by se dělo v céčku):

let listener = TcpListener::bind("127.0.0.1:1234").unwrap();

Následně se získá nekonečný iterátor, který při každém požadavku o spojení od klienta vrátí strukturu typu Option<Result<TcpStream>>, která již reprezentuje obousměrný komunikační kanál. Vzhledem k tomu, že je iterátor nekonečný, bude nutné server ukončit jinak, například přes Ctrl+C z terminálu, posláním signálu STOP příkazem kill atd.:

let tcp_stream_iter = listener.incoming();

Způsob realizace na požadavek o spojení může vypadat takto:

for tcp_stream in tcp_stream_iter {
    if tcp_stream.is_ok() {
        handler(tcp_stream.unwrap());
    } else {
        println!("connection failed");
    }
}

Handler je prozatím velmi primitivní, protože pouze klientovi pošle textovou odpověď a následně spojení ukončí:

fn handler(mut stream:TcpStream) {
    println!("Accepted connection");
    stream.write(b"Server response...\r\n").unwrap();
}

Celý zdrojový kód vypadá následovně:

use std::io::Write;
use std::net::TcpListener;
use std::net::TcpStream;
 
fn handler(mut stream:TcpStream) {
    println!("Accepted connection");
    stream.write(b"Server response...\r\n").unwrap();
}
 
fn main() {
    let listener = TcpListener::bind("127.0.0.1:1234").unwrap();
 
    let tcp_stream_iter = listener.incoming();
 
    for tcp_stream in tcp_stream_iter {
        if tcp_stream.is_ok() {
            handler(tcp_stream.unwrap());
        } else {
            println!("connection failed");
        }
    }
}

Nejprve spustíme server:

$ ./292_tcp_listener_1

Následně se z jiného terminálu pokusíme k serveru připojit. Měli bychom přijmout zprávu „Server response…“ a spojení by se mělo automaticky ukončit:

$ telnet localhost 1234
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
Server response...
Connection closed by foreign host.

Vylepšení tohoto serveru si ukážeme příště.

11. 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/presentations. Příklady si můžete v případě potřeby stáhnout i jednotlivě bez nutnosti klonovat celý repositář:

Příklad	Odkaz do GIT repositáře
286_sequences47.rs	https://github.com/tisnik/presentations/blob/master/rust/286_sequences47.rs
287_sequences48.rs	https://github.com/tisnik/presentations/blob/master/rust/287_sequences48.rs
288_sequences49.rs	https://github.com/tisnik/presentations/blob/master/rust/288_sequences49.rs
289_sequences50.rs	https://github.com/tisnik/presentations/blob/master/rust/289_sequences50.rs
290_sequences51.rs	https://github.com/tisnik/presentations/blob/master/rust/290_sequences51.rs
291_sequences52.rs	https://github.com/tisnik/presentations/blob/master/rust/291_sequences52.rs

Již dopředu se můžete podívat na demonstrační příklady, s nimiž se seznámíme v navazující části tohoto seriálu:

Příklad	Odkaz do GIT repositáře
292_tcp_listener₁.rs	https://github.com/tisnik/presentations/blob/master/rust/292_tcp_listener₁.rs
293_tcp_listener₂.rs	https://github.com/tisnik/presentations/blob/master/rust/293_tcp_listener₂.rs
294_tcp_listener₃.rs	https://github.com/tisnik/presentations/blob/master/rust/294_tcp_listener₃.rs
295_tcp_listener₄.rs	https://github.com/tisnik/presentations/blob/master/rust/295_tcp_listener₄.rs

12. Odkazy na Internetu

TcpListener
https://doc.rust-lang.org/std/net/struct.TcpListener.html
TcpStream
https://doc.rust-lang.org/std/net/struct.TcpStream.html
Binary heap (Wikipedia)
https://en.wikipedia.org/wiki/Binary_heap
Binární halda (Wikipedia)
https://cs.wikipedia.org/wiki/Bin%C3%A1rn%C3%AD_halda
Halda (datová struktura)
https://cs.wikipedia.org/wiki/Halda_%28datov%C3%A1_struktura%29
Struct std::collections::HashSet
https://doc.rust-lang.org/std/collections/struct.HashSet.html
Struct std::collections::BTreeSet
https://doc.rust-lang.org/std/collections/struct.BTreeSet.html
Struct std::collections::BinaryHeap
https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html
Set (abstract data type)
https://en.wikipedia.org/wiki/Set_%28abstract_data_type%29#Language_support
Associative array
https://en.wikipedia.org/wiki/Associative_array
Hash Table
https://en.wikipedia.org/wiki/Hash_table
B-tree
https://en.wikipedia.org/wiki/B-tree
Pedro Celis: Robin Hood Hashing (naskenované PDF!)
https://cs.uwaterloo.ca/research/tr/1986/CS-86–14.pdf
Robin Hood hashing
http://codecapsule.com/2013/11/11/robin-hood-hashing/
Robin Hood hashing: backward shift deletion
http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/
Module std::collections
https://doc.rust-lang.org/std/collections/
Module std::vec
https://doc.rust-lang.org/nightly/std/vec/index.html
Struct std::collections::VecDeque
https://doc.rust-lang.org/std/collections/struct.VecDeque.html
Struct std::collections::LinkedList
https://doc.rust-lang.org/std/collections/struct.LinkedList.html
Module std::fmt
https://doc.rust-lang.org/std/fmt/
Macro std::println
https://doc.rust-lang.org/std/macro.println.html
Enum std::result::Result
https://doc.rust-lang.org/std/result/enum.Result.html
Module std::result
https://doc.rust-lang.org/std/result/
Result
http://rustbyexample.com/std/result.html
Rust stdlib: Option
https://doc.rust-lang.org/std/option/enum.Option.html
Module std::option
https://doc.rust-lang.org/std/option/index.html
Rust by example: option
http://rustbyexample.com/std/option.html
Rust by example: if-let
http://rustbyexample.com/flow_control/if_let.html
Rust by example: while let
http://rustbyexample.com/flow_control/while_let.html
Rust by example: Option<i32>
http://rustbyexample.com/std/option.html
An Overview of Macros in Rust
http://words.steveklabnik.com/an-overview-of-macros-in-rust
A Practical Intro to Macros in Rust 1.0
https://danielkeep.github.io/practical-intro-to-macros.html
The Rust Programming Language: macros
https://doc.rust-lang.org/beta/book/macros.html
Rust by example: 15 macro_rules!
http://rustbyexample.com/macros.html
Primitive Type isize
https://doc.rust-lang.org/nightly/std/primitive.isize.html
Primitive Type usize
https://doc.rust-lang.org/nightly/std/primitive.usize.html
Primitive Type array
https://doc.rust-lang.org/nightly/std/primitive.array.html
Module std::slice
https://doc.rust-lang.org/nightly/std/slice/
Rust by Example: 2.3 Arrays and Slices
http://rustbyexample.com/primitives/array.html
What is the difference between Slice and Array (stackoverflow)
http://stackoverflow.com/questions/30794235/what-is-the-difference-between-slice-and-array
Learning Rust With Entirely Too Many Linked Lists
http://cglab.ca/~abeinges/blah/too-many-lists/book/
Testcase: linked list
http://rustbyexample.com/custom_types/enum/testcase_linked_list.html
Operators and Overloading
https://doc.rust-lang.org/book/operators-and-overloading.html
Module std::ops
https://doc.rust-lang.org/std/ops/index.html
Module std::cmp
https://doc.rust-lang.org/std/cmp/index.html
Trait std::ops::Add
https://doc.rust-lang.org/stable/std/ops/trait.Add.html
Trait std::ops::AddAssign
https://doc.rust-lang.org/std/ops/trait.AddAssign.html
Trait std::ops::Drop
https://doc.rust-lang.org/std/ops/trait.Drop.html
Trait std::cmp::Eq
https://doc.rust-lang.org/std/cmp/trait.Eq.html
Struct std::boxed::Box
https://doc.rust-lang.org/std/boxed/struct.Box.html
Explore the ownership system in Rust
https://nercury.github.io/rust/guide/2015/01/19/ownership.html
Rust's ownership and move semantic
http://www.slideshare.net/saneyuki/rusts-ownership-and-move-semantics
Trait std::marker::Copy
https://doc.rust-lang.org/stable/std/marker/trait.Copy.html
Trait std::clone::Clone
https://doc.rust-lang.org/stable/std/clone/trait.Clone.html
The Stack and the Heap
https://doc.rust-lang.org/book/the-stack-and-the-heap.html
Rust Compare: Pointers & References
http://www.rust-compare.com/site/pointers.html
Rust Compare: Parameters
http://www.rust-compare.com/site/params.html
Why does this compile? Automatic dereferencing?
https://users.rust-lang.org/t/why-does-this-compile-automatic-dereferencing/2183
Understanding Pointers, Ownership, and Lifetimes in Rust
http://koerbitz.me/posts/Understanding-Pointers-Ownership-and-Lifetimes-in-Rust.html
Rust lang series episode #25 — pointers (#rust-series)
https://steemit.com/rust-series/@jimmco/rust-lang-series-episode-25-pointers-rust-series
Rust – home page
https://www.rust-lang.org/en-US/
Rust – Frequently Asked Questions
https://www.rust-lang.org/en-US/faq.html
Destructuring and Pattern Matching
https://pzol.github.io/getting_rusty/posts/20140417_destructuring_in_rust/
The Rust Programming Language
https://doc.rust-lang.org/book/
Rust (programming language)
https://en.wikipedia.org/wiki/Rust_%28programming_language%29
Go – home page
https://golang.org/
Stack Overflow – Most Loved, Dreaded, and Wanted language
https://stackoverflow.com/research/developer-survey-2016#technology-most-loved-dreaded-and-wanted
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/
Rust vs Go: My experience
https://www.reddit.com/r/golang/comments/21m6jq/rust_vs_go_my_experience/
Friends of Rust (Organizations running Rust in production)
https://www.rust-lang.org/en-US/friends.html
Rust programs versus C++ g++
https://benchmarksgame.alioth.debian.org/u64q/compare.php?lang=rust&lang2=gpp
Další benchmarky (nejedná se o reálné příklady „ze života“)
https://github.com/kostya/benchmarks
Go na Redditu
https://www.reddit.com/r/golang/
Rust vs. Go
http://vschart.com/compare/rust/vs/go-language
Abstraction without overhead: traits in Rust
https://blog.rust-lang.org/2015/05/11/traits.html
Method Syntax
https://doc.rust-lang.org/book/method-syntax.html
Traits in Rust
https://doc.rust-lang.org/book/traits.html
Functional Programming in Rust – Part 1 : Function Abstraction
http://blog.madhukaraphatak.com/functional-programming-in-rust-part-1/
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
Chytré ukazatele (moderní verze jazyka C++) [MSDN]
https://msdn.microsoft.com/cs-cz/library/hh279674.aspx
UTF-8 Everywhere
http://utf8everywhere.org/
Rust by Example
http://rustbyexample.com/
Rust oficiálně ve Fedoře
https://mojefedora.cz/rust-oficialne-ve-fedore/
Resource acquisition is initialization
https://en.wikipedia.org/wiki/Resource_acquisition_is_initialization
TIOBE index (October 2016)
http://www.tiobe.com/tiobe-index/
Porovnání Go, D a Rustu na OpenHubu:
https://www.openhub.net/languages/compare?language_name[]=-1&language_name[]=-1&language_name[]=dmd&language_name[]=golang&language_name[]=rust&language_name[]=-1&measure=commits
String Types in Rust
http://www.suspectsemantics.com/blog/2016/03/27/string-types-in-rust/
Trait (computer programming)
https://en.wikipedia.org/wiki/Trait_%28computer_programming%29
Type inference
https://en.wikipedia.org/wiki/Type_inference

Seriál: Programovací jazyk Rust

Programovací jazyk Rust: efektivní práce s prvky uloženými v kolekcích
Programovací jazyk Rust: binární halda, použití TCP
Programovací jazyk Rust: jednoduchý server a klient komunikující přes TCP

Přečtěte si všechny díly seriálu Programovací jazyk Rust nebo sledujte jeho RSS

Vstoupit do diskuse (6 názorů)

Pavel Tišnovský

Vystudoval VUT FIT a v současné době pracuje na projektech vytvářených v jazycích Python a Go.

Pravděpodobně viz: https://hoverbear.github.io/raft-rs/mio/index.html

Bel Shamharoth

Sdílet

Obsah

1. Datová struktura BinaryHeap (binární halda)

2. Interní implementace binární haldy

3. Časová složitost základních operací s binární haldou

4. Triviální příklad použití binární haldy

5. Problematika uspořádání prvků

6. Iterátor pro BinaryHeap versus funkce pop()

7. Převod prvků z binární haldy do vektoru

8. Převod prvků do setříděného vektoru

9. Postupný přesun prvků z binární haldy s použitím funkce drain()

10. Podpora TCP v základní knihovně programovacího jazyka Rust

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

12. Odkazy na Internetu

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