diff options
Diffstat (limited to 'bonusaufgabe/src')
| -rw-r--r-- | bonusaufgabe/src/benchmark.rs | 24 | ||||
| -rw-r--r-- | bonusaufgabe/src/main.rs | 103 |
2 files changed, 72 insertions, 55 deletions
diff --git a/bonusaufgabe/src/benchmark.rs b/bonusaufgabe/src/benchmark.rs new file mode 100644 index 0000000..9063977 --- /dev/null +++ b/bonusaufgabe/src/benchmark.rs @@ -0,0 +1,24 @@ +use super::*; +use test::Bencher; + +fn benchmark(task_file_name: &str, bencher: &mut Bencher) { + let task_str = fs::read_to_string(task_file_name).expect("Datei kann nicht gelesen werden"); + let task = Task::try_from(task_str.as_str()).expect("Datei enthält keine gültige Aufgabe"); + + bencher.iter(|| solve_task(&task)); +} + +#[bench] +fn benchmark3(bencher: &mut Bencher) { + benchmark("input/stapel3.txt", bencher); +} + +#[bench] +fn benchmark4(bencher: &mut Bencher) { + benchmark("input/stapel4.txt", bencher); +} + +#[bench] +fn benchmark5(bencher: &mut Bencher) { + benchmark("input/stapel5.txt", bencher); +} diff --git a/bonusaufgabe/src/main.rs b/bonusaufgabe/src/main.rs index f5983bc..f3245d2 100644 --- a/bonusaufgabe/src/main.rs +++ b/bonusaufgabe/src/main.rs @@ -1,14 +1,21 @@ +#![feature(test)] + +extern crate test; + +#[cfg(test)] +mod benchmark; + use bitvec::prelude::*; use rand::seq::SliceRandom; use std::env; use std::fmt; use std::fs; use std::process; +use std::time; type Card = BitVec; // Typ, der eine zu lösende Aufgabe beschreibt. -#[derive(Clone)] // TODO remove struct Task { cards: Vec<Card>, num_pass_cards: usize, @@ -17,11 +24,18 @@ struct Task { // Die Lösung enthält die von Zara stammenden echten Karten. struct Solution { real_cards: Vec<Card>, + // Der Anschaulichkeit halber werden ein paar weitere Randinformationen + // mit ausgegeben. + num_cards: usize, + num_real_cards: usize, + bits_per_card: usize, + num_free_vars: usize, + p: usize, } // `solve_task` löst eine gegebene Aufgabe und beinhaltet den // eigentlichen Algorithmus. -fn solve_task(task: Task) -> Solution { +fn solve_task(task: &Task) -> Solution { // `num_real_cards` Karten im Stapel stammen von Zara Zackig, nämlich // die `num_pass_cards` Öffnungskarten plus eine Sicherungkarte. let num_real_cards = task.num_pass_cards + 1; @@ -76,28 +90,20 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut // `ppcm` ist eine solche Kontrollmatrix (repräsentiert als Iliffe-Vektor), // auf dessen Spalten zusätzlich noch die Permutation `permutation` // angewandt wurde. - // - // O(bits_per_card num_cards) let mut ppcm = transpose_and_optionally_permute_columns(cards, Some(&permutation)); // `basic_vars` und `free_vars` enthalten jeweils die Spaltenindizes der - // Basisvariablen bzw. freien Variablen von `ppcm`. Die Indizes der - // Basisvariablen bilden das "information set" (siehe Dokumentation) - // dieser Iteration. + // Basisvariablen bzw. freien Variablen von `ppcm`. let mut basic_vars = Vec::new(); let mut free_vars = Vec::new(); // Zunächst wird `ppcm` mittels des Gaußschen Eliminierungsverfahrens // in die reduzierte Stufenform gebracht. - // - // O(bits_per_card^2 num_cards) let mut current_row = 0; let mut current_col = 0; while current_row < bits_per_card && current_col < num_cards { - // O(bits_per_card) // Wir suchen in der derzeitigen Spalte ein Pivotelement (eine 1). let pivot_row = match (current_row..bits_per_card).find(|row| ppcm[*row][current_col]) { - // O(bits_per_card) worst-case Some(row) => row, None => { // Wurde kein Pivotelement gefunden, gehört diese Spalte zu @@ -118,10 +124,9 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut // indem die entsprechenden Zeilen mit der Zeile des Pivotelements XOR // gerechnet (addiert) werden. for lower_row in (current_row + 1)..bits_per_card { - // O(bits_per_card) if ppcm[lower_row][current_col] { let current_row_cloned = ppcm[current_row].clone(); - ppcm[lower_row] ^= current_row_cloned; // O(num_cards) + ppcm[lower_row] ^= current_row_cloned; } } // Es kann zur nächsten Zeile und Spalte übergegangen werden. @@ -145,15 +150,11 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut // Einsen werden eliminiert, indem die entsprechenden Zeilen mit der Zeile // des Pivotelements XOR gerechnet (addiert) werden. Diese Erweiterung // wird auch als Gauß-Jordan-Algorithmus bezeichnet. - // - // O(bits_per_card^2 num_cards) for (pivot_row, pivot_col) in basic_vars.iter().enumerate().rev() { - // O(bits_per_card) for upper_row in 0..pivot_row { - // O(bits_per_card) if ppcm[upper_row][*pivot_col] { let pivot_row_cloned = ppcm[pivot_row].clone(); - ppcm[upper_row] ^= pivot_row_cloned; // O(num_cards) + ppcm[upper_row] ^= pivot_row_cloned; } } } @@ -164,25 +165,24 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut // den Wert 1 haben. Ob diese Annahme stimmt, hängt davon ab, ob im ersten // Schritt eine glückliche Permutation gewählt wurde. - // Bei sehr einfachen Aufgabenstellungen kann es vorkommen, das die Anzahl - // der freien Variablen noch kleiner als Parameter `P` des Lee-Brickell- - // Algorithmus ist (z.B. bei nur einer freien Variable). In diesem Fall - // muss der Parameter natürlich entsprechend nach unten korrigiert werden. - let p = P.min(num_free_vars); + // In einigen Fällen muss der Parameter `P` des Lee-Brickell-Algorithmus + // an die Eingabe angepasst werden, z.B. bei sehr leicht lösbaren Aufgaben + // mit nur einer freien Variable. Details sind in der Dokumentation, + // Abschnitt 1.2, Schritt 4 zu finden. + let p = ((P as isize).clamp( + -(num_cards as isize) + num_free_vars as isize + num_real_cards as isize, + num_real_cards.min(num_free_vars) as isize, + )) as usize; // Zunächst wird die Matrix transponiert, damit die Bits der Spalten // jeweils zusammenhängend im Speicher liegen und somit die Spalten // schneller miteinander XOR gerechnet werden können. - // - // O(bits_per_card num_cards) let transposed_ppcm = transpose_and_optionally_permute_columns(&ppcm, None); // Um die `p` freien Variablen mit dem Wert 1 zu finden, wird über alle // möglichen `p`-Untermengen der freien Variablen iteriert und jeweils // angenommen, dass von den freien Variablen nur die in der Untermenge den // Wert 1 haben. - // - // O(k choose p) let mut subset_iter = SubsetIterator::new(num_free_vars, p); while let Some(subset) = subset_iter.next() { // Zunächst wird das exklusive Oder der `p` Spalten in der Untermenge @@ -216,7 +216,14 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut // echten Karten vor der Ausgabe aufsteigend sortiert. real_cards.sort(); - return Some(Solution { real_cards }); + return Some(Solution { + real_cards, + num_cards, + num_real_cards, + bits_per_card, + num_free_vars, + p, + }); } } @@ -334,33 +341,12 @@ fn main() { let task_str = fs::read_to_string(task_file_name).expect("Datei kann nicht gelesen werden"); let task = Task::try_from(task_str.as_str()).expect("Datei enthält keine gültige Aufgabe"); - // let solution = solve_task(task); - // print!("{}", solution); - - let mut task = task; + let start = time::Instant::now(); + let solution = solve_task(&task); + let elapsed = start.elapsed(); - loop { - use rand::prelude::*; - let solution = solve_task(task.clone()); - print!("{}", solution); - - let num_rand_cards = task.cards.len() - task.num_pass_cards - 1; - let bits_per_card = task.cards[0].len(); - let mut new_rand_cards = (0..num_rand_cards) - .map(|_| { - rand::thread_rng() - .sample_iter::<bool, rand::distributions::Standard>( - rand::distributions::Standard, - ) - .take(bits_per_card) - .collect::<BitVec>() - }) - .collect::<Vec<BitVec>>(); - let mut new_cards = solution.real_cards; - new_cards.append(&mut new_rand_cards); - new_cards.shuffle(&mut rand::thread_rng()); - task.cards = new_cards - } + println!("{}", solution); + println!("Laufzeit ohne I/O: {:?}", elapsed); } // Liest eine Aufgabe im Format der Beispielaufgaben ein. @@ -386,7 +372,7 @@ impl TryFrom<&str> for Task { '1' => Some(true), _ => None, }) - .collect::<BitVec>() + .collect::<Card>() }) .collect::<Vec<Card>>(); @@ -404,6 +390,13 @@ impl TryFrom<&str> for Task { // Formatiert die Lösung zur Ausgabe. impl fmt::Display for Solution { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + writeln!( + f, + "Randinformationen (siehe Dokumentation):\nn = {}; w = {}; b = {}; k = {}; p = {}", + self.num_cards, self.num_real_cards, self.bits_per_card, self.num_free_vars, self.p + )?; + writeln!(f)?; + writeln!(f, "Echte Karten:")?; for card in self.real_cards.iter() { for bit in card.iter() { match *bit { |