From: Tim "S.D.Eagle" Zeitz Date: Tue, 16 Oct 2018 15:50:50 +0000 (+0200) Subject: restructure and add documentation X-Git-Url: https://i11git.iti.kit.edu/anon-gitweb/?p=Mitarbeiter%2FTim-Zeitz%2Fstud-rust-base.git;a=commitdiff_plain;h=c56a14307218fbb51ad188826a431cd034cce473 restructure and add documentation --- diff --git a/README.md b/README.md new file mode 100644 index 0000000..3a06ffa --- /dev/null +++ b/README.md @@ -0,0 +1,112 @@ +# Getting started with Rust + +## Installieren über Rustup + +[`rustup`](https://rustup.rs/) ist ein Installer der einem das Management unterschiedlicher Compilerversionen (aktuell halten, mehrere Versionen parallel, Extra-Komponenten verwalten, etc.) abnimmt. +Rustup kann entweder über das Packetmanagement eurer Distribution oder die Anweisungen auf der Website installiert werden. +Die Website-Methode sollte auch verwendet werden, wenn Rust auf den Poolrechnern/Computes verwendet werden soll. +Diese installiert Rustup im Homeverzeichnis des aktuellen Nutzers. +Dokumentation gibt es [hier](https://github.com/rust-lang-nursery/rustup.rs/blob/master/README.md); + +Den aktuellen stable Compiler könnt ihr dann mit `rustup install stable` installieren. +Seine Toolchains kann man mit `rustup update` gesammelt auf den aktuellen Stand bringen. + +## Rust lernen + +Die Rust-Community legt Wert auf gute Dokumentation. +Dementsprechend sind Libraries (insbesondere die Standardlibrary) in der Regel gut dokumentiert. +Außerdem gibt es umfangreiche [Einstiegsressourcen](https://www.rust-lang.org/en-US/documentation.html). +Insbesondere mit ["Dem Buch"](https://doc.rust-lang.org/book/second-edition/index.html) kriegt man kompakt und gut sortiert einmal alle Sprachkonzepte erklärt. + +## Cargo: Buildsystem & Dependency Management + +Rust hat ein Build- und Dependency Managementsystem. Yay. +Heißt `cargo`. +Mit `cargo build` kann man Programme bauen. +Im Falle dieses Repos baut das nur die Basislib und noch keine Executable, dazu dann z.B. `cargo build --bin example`. +Mit `cargo run` kann man bauen und direkt ausführen. +Argumente an das Programm kommen nach einem `--`. +Sobald die Performance interessant ist unbedingt `cargo run --release` nutzen - das ist ungefähr was `-O3` bei C++ ist. +Alles zusammen `cargo run --release --bin example -- /path/to/graph/files/dir/`. + +Mit `cargo check` kann man das Programm checken ohne zu bauen, das kann einem einiges an Zeit sparen. + +## Clippy + +Rust hat einen exzellenten Linter, der einem sehr hilft idiomatischen und performanten Code zu schreiben. +Das ist insbesondere wenn man noch nicht viel Erfahrung mit der Sprache hat extrem sinnvoll! +Installieren kann man Clippy mit `rustup component add clippy-preview`. +Anstatt `cargo check` ruft man dann `cargo clippy` auf und kann sich auf viel hilfreiches Feedback freuen. + +# Rust Routenplanungs-Basis-Framework + +In diesem GIT-Repository finden Sie eine kleine Codebasis die Sie zur Bearbeitung des Übungsblatts verwenden sollen. +Sie haben Zugriff auf vier Module und 3 Hilfsprogramme. + +In `types` werden Gewichts und ID Typen definiert sowie eine wichtige Gewichtskonstante: `INFINITY`. +`INFINITY` repräsentiert die unendliche Distanz und ist so gewählt, dass die Konstante verdoppelt werden kann, ohne einen Überlauf zu verursachen, d.h., der Ausdruck `INFINITY < INFINITY + INFINITY` ist unproblematisch. +Im Modul `time` gibt es zwei Funktionen die verwendet werden können um die Laufzeit von Code zu messen. +Das Modul `index_heap` enthält eine Prioritätswarteschlange (`std::collections::BinaryHeap` ist problematisch für unseren Anwendungsfall, da keine `decrease_key` Operation vorhanden). +Das `io` Modul dienen dem Einlesen und der Ausgabe von Daten. +Jede Datendatei ist das binäre Abbild eines `std::vector`s im Speicher, d.h., ein Vektor von 100 `u32`s wird in einer Datei gespeichert die genau 400 Byte lang (Wir gehen stets davon aus, dass ein int 32 Bit hat.) ist. +Die entsprechenden Funktionen sind über Traits definiert und können so direkt auf den entsprechenden Objekten aufgerufen werden. +Das kann z.B. so aussehen: + +```Rust +extern crate stud_rust_base; +use stud_rust_base::io::*; + +let head = Vec::::load_from("head_file_name").expect("could not read head"); +let lat = Vec::::load_from("node_latitude_file_name").expect("could not read lat"); +head.write_to("output_file").expect("could not write head"); +``` + +Die Dateien in `src/bin/` sind einmal ein Beispielprogramm sowieso Hilfsprogramme. +`encode_vector` und `decode_vector` konvertieren Vektoren von und zu textuellen Darstellungen. +Das Programm `compare_vector` vergleicht ob zwei Vektoren identisch sind und wenn sie es nicht sind gibt es eine Übersicht über die Unterschiede. +Fügen sie Ihre Programme in `src/bin/` hinzu, diese werden dann von `cargo` automatisch gefunden. + +## Graphen + +Knoten und Kanten werden durch numerische IDs identifiziert, die von `0` bis `n-1` bzw. `m-1` gehen, wobei `n` die Anzahl an Knoten und `m` die Anzahl an gerichteten Kanten ist. +Wir speichern gewichtete und gerichtete Graphen in einer Ajdazenzarraydarstellung. +Ein gerichteter und gewichteter Graph besteht aus 3 Vektoren. +Diese heißen `first_out`, `head` und `weight`. +Um über die ausgehenden Kanten eines Knoten zu iterieren können Sie den folgenden Code verwenden: + +```Rust +extern crate stud_rust_base; +use stud_rust_base::{types::*, io::*}; + +let first_out = Vec::::load_from("first_out_file_name").expect("could not read first_out"); +let head = Vec::::load_from("head_file_name").expect("could not read head"); +let travel_time = Vec::::load_from("weight_file_name").expect("could not read travel_time"); + +let node_id = 42; +for edge_id in head[first_out[node_id] as usize .. first_out[node_id + 1] as usize] { + println!("There is an arc from {} to {} with weight {}", node_id, head[edge_id as usize], travel_time[edge_id as usize]); +} +``` + +**Hinweis**: `head` und `weight` haben so viel Elemente wie es Kanten gibt. +`first_out` hat ein Element mehr als es Knoten gibt. +Das erste Element von `first_out` ist immer 0 und das letzte ist die Anzahl an Kanten. +Für alle Graphen gibt es zwei unterschiedliche Kantengewichte: Reisezeit und Reiselänge. +Des Weiteren gibt es für manche Graphen zusätzliche für jeden Knoten die geographische Position. +Diese wird als zwei `float` Vektoren abgespeichert die für jeden Knoten den Längen- und Breitengrad angeben. + +Im Verzeichnis `/algoDaten/praktikum/graph` liegen die Daten von mehreren Graphen in diesem Format. +Manche dienen nur zu Testzwecken während andere zur Aufgabenbewertung verwendet werden. +Die Testgraphen entsprechen ganz grob Stupferich, Karlsruhe\&Umgebung, Deutschland\&Umgebung und (West-)Europa. +Die Aufgabengraphen haben die Größe des Deutschlandgraphen. + +**Achtung**: Der Europagraph könnte zu groß sein für den Hauptspeicher von manchen Poolraumrechnern. + +## Hinweise zur Nutzung im Routenplanungspraktikum + +Der Quellcode soll durch das Ausführen von `cargo build --all` mit dem aktuellen stabilen Compiler (1.29.2) übersetzt werden können. +Auf den Poolraumrechner ist kein Rust Compiler vorinstalliert. +Sie können aber für ihren Nutzer lokal `rustup` und damit dann einen aktuellen Compiler installieren. +Die Nutzung von nicht stabilen nightly Features ist nicht erlaubt. +Das verwenden externer crates ist nicht erlaubt. +Die Rust-Standardbibliothek ist nicht extern. diff --git a/src/bin/example.rs b/src/bin/example.rs new file mode 100644 index 0000000..775d2ca --- /dev/null +++ b/src/bin/example.rs @@ -0,0 +1,30 @@ +extern crate stud_rust_base; + +use stud_rust_base::{ + types::*, + io::*, + time::report_time, +}; + +use std::{env, path::Path}; + +fn main() { + let mut args = env::args(); + args.next(); + + let arg = &args.next().expect("No directory arg given"); + let path = Path::new(arg); + + let first_out = Vec::::load_from(path.join("first_out").to_str().unwrap()).expect("could not read first_out"); + let head = Vec::::load_from(path.join("head").to_str().unwrap()).expect("could not read head"); + let travel_time = Vec::::load_from(path.join("travel_time").to_str().unwrap()).expect("could not read travel_time"); + + report_time("iterating over arcs of some node", || { + let node_id = 42; + for &edge_id in &head[first_out[node_id] as usize .. first_out[node_id + 1] as usize] { + println!("There is an arc from {} to {} with weight {}", node_id, head[edge_id as usize], travel_time[edge_id as usize]); + } + }); + + vec![42; 42].write_to(path.join("distances").to_str().unwrap()).expect("could not write distances"); +} diff --git a/src/index_heap.rs b/src/index_heap.rs index 2f608d9..c086dc3 100644 --- a/src/index_heap.rs +++ b/src/index_heap.rs @@ -19,7 +19,6 @@ const TREE_ARITY: usize = 4; const INVALID_POSITION: usize = std::usize::MAX; impl IndexdMinHeap { - #[allow(dead_code)] pub fn new(max_id: usize) -> IndexdMinHeap { IndexdMinHeap { positions: vec![INVALID_POSITION; max_id], @@ -35,12 +34,10 @@ impl IndexdMinHeap { self.len() == 0 } - #[allow(dead_code)] pub fn contains_index(&self, id: usize) -> bool { self.positions[id] != INVALID_POSITION } - #[allow(dead_code)] pub fn clear(&mut self) { for element in &self.data { self.positions[element.as_index()] = INVALID_POSITION; @@ -48,12 +45,10 @@ impl IndexdMinHeap { self.data.clear(); } - #[allow(dead_code)] pub fn peek(&self) -> Option<&T> { self.data.first() } - #[allow(dead_code)] pub fn pop(&mut self) -> Option { self.data.pop().map(|mut item| { self.positions[item.as_index()] = INVALID_POSITION; @@ -67,7 +62,6 @@ impl IndexdMinHeap { }) } - #[allow(dead_code)] pub fn push(&mut self, element: T) { assert!(!self.contains_index(element.as_index())); let insert_position = self.len(); @@ -79,7 +73,6 @@ impl IndexdMinHeap { // Updates the key of an element if the new key is smaller than the old key. // Does nothing if the new key is larger. // Undefined if the element is not part of the queue. - #[allow(dead_code)] pub fn decrease_key(&mut self, element: T) { let position = self.positions[element.as_index()]; self.data[position] = element; @@ -89,7 +82,6 @@ impl IndexdMinHeap { // Updates the key of an element if the new key is larger than the old key. // Does nothing if the new key is smaller. // Undefined if the element is not part of the queue. - #[allow(dead_code)] pub fn increase_key(&mut self, element: T) { let position = self.positions[element.as_index()]; self.data[position] = element; diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..ffa1945 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,6 @@ +extern crate time as time_crate; + +pub mod index_heap; +pub mod io; +pub mod time; +pub mod types; diff --git a/src/main.rs b/src/main.rs deleted file mode 100644 index c920768..0000000 --- a/src/main.rs +++ /dev/null @@ -1,33 +0,0 @@ -extern crate time as time_crate; - -mod index_heap; -mod io; -mod time; -mod types; - -use types::*; -use io::*; -use time::*; - -use std::{env, path::Path}; - -fn main() { - let mut args = env::args(); - args.next(); - - let arg = &args.next().expect("No directory arg given"); - let path = Path::new(arg); - - let first_out: Vec = Vec::load_from(path.join("first_out").to_str().unwrap()).expect("could not read first_out"); - let head: Vec = Vec::load_from(path.join("head").to_str().unwrap()).expect("could not read head"); - let travel_time: Vec = Vec::load_from(path.join("travel_time").to_str().unwrap()).expect("could not read travel_time"); - - report_time("iterating over arcs of some node", || { - let node_id = 42; - for &edge_id in &head[first_out[node_id] as usize .. first_out[node_id + 1] as usize] { - println!("There is an arc from {} to {} with weight {}", node_id, head[edge_id as usize], travel_time[edge_id as usize]); - } - }); - - vec![42; 42].write_to(path.join("distances").to_str().unwrap()).expect("could not write distances"); -} diff --git a/src/time.rs b/src/time.rs index 2f6e9ac..30da0a2 100644 --- a/src/time.rs +++ b/src/time.rs @@ -1,6 +1,5 @@ use time_crate as time; -#[allow(dead_code)] pub fn report_time Out>(name: &str, f: F) -> Out { let start = time::now(); println!("starting {}", name); @@ -9,36 +8,36 @@ pub fn report_time Out>(name: &str, f: F) -> Out { res } -#[allow(dead_code)] pub fn measure Out>(f: F) -> (Out, time::Duration) { let start = time::now(); let res = f(); (res, time::now() - start) } -#[allow(dead_code)] #[derive(Debug)] pub struct Timer { start: time::Tm } +impl Default for Timer { + fn default() -> Self { + Self::new() + } +} + impl Timer { - #[allow(dead_code)] pub fn new() -> Timer { Timer { start: time::now() } } - #[allow(dead_code)] pub fn restart(&mut self) { self.start = time::now(); } - #[allow(dead_code)] pub fn report_passed_ms(&self) { println!("{}ms", (time::now() - self.start).num_milliseconds()); } - #[allow(dead_code)] pub fn get_passed_ms(&self) -> i64 { (time::now() - self.start).num_milliseconds() } diff --git a/src/types.rs b/src/types.rs index bb11a00..b10ba13 100644 --- a/src/types.rs +++ b/src/types.rs @@ -1,10 +1,6 @@ use std; -#[allow(dead_code)] pub type NodeId = u32; -#[allow(dead_code)] pub type EdgeId = u32; -#[allow(dead_code)] pub type Weight = u32; -#[allow(dead_code)] pub const INFINITY: Weight = std::u32::MAX / 2;