From 1cac34b7ea939e0d0d1157de59e90c70b2831812 Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Sun, 25 Sep 2022 00:12:14 +0200 Subject: More efficient? --- src/config.rs | 41 +++++++++ src/corpus.rs | 137 +++++++++++++++++++++++++++ src/layout.rs | 212 ++++++++++++++++++++++++++++++++++++++++++ src/main.rs | 291 +++++++--------------------------------------------------- 4 files changed, 421 insertions(+), 260 deletions(-) create mode 100644 src/config.rs create mode 100644 src/corpus.rs create mode 100644 src/layout.rs (limited to 'src') diff --git a/src/config.rs b/src/config.rs new file mode 100644 index 0000000..4449b7b --- /dev/null +++ b/src/config.rs @@ -0,0 +1,41 @@ +pub const NUM_KEYS: usize = 30; // you should not change this + +pub const KEY_CHARS: [char; NUM_KEYS] = [ + 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', + 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '/', '.', ',', '\'', +]; + +pub const KEY_TO_FINGER: [usize; NUM_KEYS] = [ + 0, 1, 2, 3, 3, 4, 4, 5, 6, 7, 0, 1, 2, 3, 3, 4, 4, 5, 6, 7, 0, 1, 2, 3, 3, 4, 4, 5, 6, 7, +]; + +pub fn canonicalise(inp: char) -> Option { + if inp.is_ascii_alphabetic() { + return Some(inp.to_ascii_uppercase()); + } else { + match inp { + '.' => Some('.'), + '>' => Some('.'), + ',' => Some(','), + '<' => Some(','), + '/' => Some('/'), + '?' => Some('/'), + '\'' => Some('\''), + '"' => Some('\''), + _ => None, + } + } +} + +const fn build_lookup_table() -> [usize; 128] { + let mut result = [0; 128]; + let mut i = 0; + + while i < NUM_KEYS { + result[KEY_CHARS[i] as usize] = i; + i += 1; + } + return result; +} + +pub const CHAR_TO_INDEX: [usize; 128] = build_lookup_table(); diff --git a/src/corpus.rs b/src/corpus.rs new file mode 100644 index 0000000..20ddbb3 --- /dev/null +++ b/src/corpus.rs @@ -0,0 +1,137 @@ +use std::fmt; +use std::fs; + +use crate::config::*; +use crate::layout::*; + +const NUM_BIGRAMS: usize = NUM_KEYS * NUM_KEYS; + +pub struct Corpus { + bigram_count: [u32; NUM_BIGRAMS], + character_count: [u32; NUM_KEYS], + total_count: u32, +} + +fn pair_to_index(x: char, y: char) -> usize { + let xi = CHAR_TO_INDEX[x as usize]; + let yi = CHAR_TO_INDEX[y as usize]; + xi + NUM_KEYS * yi +} + +impl Corpus { + pub fn load(path: &str) -> Result { + let contents = fs::read_to_string(path)?; + + let mut bigram_count = [0; NUM_BIGRAMS]; + let mut character_count = [0; NUM_KEYS]; + let mut total_count = 0; + + let mut last_char = None; + for c in contents.chars() { + if let Some(c) = canonicalise(c) { + if let Some(lc) = last_char { + // We don't count these anyway + if lc != c { + bigram_count[pair_to_index(c, lc)] += 1; + bigram_count[pair_to_index(lc, c)] += 1; + } + } + last_char = Some(c); + character_count[CHAR_TO_INDEX[c as usize]] += 1; + total_count += 1; + } else { + last_char = None; + } + } + + return Ok(Corpus { + bigram_count, + character_count, + total_count, + }); + } + + pub fn evaluate_layout(&self, layout: &Layout) -> Evaluation { + let mut keypress: [u32; NUM_KEYS] = [0; NUM_KEYS]; + let mut sfb: [u32; 8] = [0; 8]; + + for (i, &c) in self.character_count.iter().enumerate() { + keypress[layout.translate_index(i)] = c; + } + + // TODO: We make assumptions about NUM_KEYS here + for i in 0..8 { + let ind = if i < 4 { i } else { i + 2 }; + + let k1 = layout.get_key(ind + 10 * 0); + let k2 = layout.get_key(ind + 10 * 1); + let k3 = layout.get_key(ind + 10 * 2); + + sfb[i] = self.bigram_count[pair_to_index(k1, k2)] + + self.bigram_count[pair_to_index(k1, k3)] + + self.bigram_count[pair_to_index(k2, k3)]; + + if i == 3 { + let k4 = layout.get_key(4 + 10 * 0); + let k5 = layout.get_key(4 + 10 * 1); + let k6 = layout.get_key(4 + 10 * 2); + sfb[i] += self.bigram_count[pair_to_index(k4, k5)] + + self.bigram_count[pair_to_index(k4, k6)] + + self.bigram_count[pair_to_index(k5, k6)] + + self.bigram_count[pair_to_index(k1, k4)] + + self.bigram_count[pair_to_index(k1, k5)] + + self.bigram_count[pair_to_index(k1, k6)] + + self.bigram_count[pair_to_index(k2, k4)] + + self.bigram_count[pair_to_index(k2, k5)] + + self.bigram_count[pair_to_index(k2, k6)] + + self.bigram_count[pair_to_index(k3, k4)] + + self.bigram_count[pair_to_index(k3, k5)] + + self.bigram_count[pair_to_index(k3, k6)]; + } else if i == 4 { + let k4 = layout.get_key(5 + 10 * 0); + let k5 = layout.get_key(5 + 10 * 1); + let k6 = layout.get_key(5 + 10 * 2); + sfb[i] += self.bigram_count[pair_to_index(k4, k5)] + + self.bigram_count[pair_to_index(k5, k6)] + + self.bigram_count[pair_to_index(k4, k6)] + + self.bigram_count[pair_to_index(k1, k4)] + + self.bigram_count[pair_to_index(k1, k5)] + + self.bigram_count[pair_to_index(k1, k6)] + + self.bigram_count[pair_to_index(k2, k4)] + + self.bigram_count[pair_to_index(k2, k5)] + + self.bigram_count[pair_to_index(k2, k6)] + + self.bigram_count[pair_to_index(k3, k4)] + + self.bigram_count[pair_to_index(k3, k5)] + + self.bigram_count[pair_to_index(k3, k6)]; + } + } + + return Evaluation::new(keypress, self.total_count, sfb); + } +} + +fn dump_bigrams(corpus: &Corpus) -> Vec<(String, u32)> { + let mut result: Vec<(String, u32)> = Vec::new(); + + for (i, &x) in KEY_CHARS.iter().enumerate() { + for &y in &KEY_CHARS[i..] { + let mut pair = String::from(x); + pair.push(y); + result.push((pair, corpus.bigram_count[pair_to_index(x, y)])); + } + } + + result.sort_by(|(_, c1), (_, c2)| c1.cmp(c2).reverse()); + + return result; +} + +impl fmt::Display for Corpus { + fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result { + formatter.write_str(&format!( + "Counted {} characters, top 5 bigrams {:?}", + self.total_count, + &dump_bigrams(self)[0..5] + )) + } +} diff --git a/src/layout.rs b/src/layout.rs new file mode 100644 index 0000000..0ce3fdc --- /dev/null +++ b/src/layout.rs @@ -0,0 +1,212 @@ +use crate::config::*; + +use rand::prelude::*; +use std::fmt; + +#[derive(Copy, Clone)] +pub struct Layout { + keys: [char; NUM_KEYS], + // index in KEY_CHAR -> index in layout + translate_index: [usize; NUM_KEYS], +} + +impl Layout { + pub fn get_key(&self, index: usize) -> char { + self.keys[index] + } + + pub fn translate_index(&self, i: usize) -> usize { + self.translate_index[i] + } + + fn keys_to_layout(layout: [char; NUM_KEYS]) -> Layout { + let mut translate_index: [usize; NUM_KEYS] = [0; NUM_KEYS]; + + for (i, seek) in KEY_CHARS.iter().enumerate() { + for (j, found) in layout.iter().enumerate() { + if seek == found { + translate_index[i] = j; + } + } + } + + return Layout { + keys: layout, + translate_index, + }; + } + + pub fn from_verbose(inp: &str) -> Option { + let mut layout: [char; NUM_KEYS] = ['x'; NUM_KEYS]; + + let mut k: usize = 0; + for c in inp.chars() { + let valid = (c.is_uppercase() && c.is_alphabetic()) + || c == '.' + || c == '/' + || c == ',' + || c == '\''; + if valid { + layout[k] = c; + k += 1; + } + if k > NUM_KEYS { + return None; + } + } + + return Some(Layout::keys_to_layout(layout)); + } + + pub fn new_random_from(kbd: &Layout, rng: &mut R) -> Layout { + let mut layout = kbd.keys; + layout.shuffle(rng); + Layout::keys_to_layout(layout) + } +} + +impl fmt::Display for Layout { + fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result { + formatter.write_str(&format_block_output(self.keys.into_iter())) + } +} + +#[derive(Copy, Clone)] +pub struct Evaluation { + keypress: [u32; NUM_KEYS], + total_keypress: u32, + sfb: [u32; 8], +} + +impl Evaluation { + pub fn new(keypress: [u32; NUM_KEYS], total_keypress: u32, sfb: [u32; 8]) -> Evaluation { + Evaluation { + keypress, + sfb, + total_keypress, + } + } + + fn output_eval(&self) -> String { + let mut result = String::new(); + let tot = self.total_keypress as f32; + + result += &format!( + "Total keypresses: {}\nPercent per key:\n", + self.total_keypress + ); + result += &format_block_output(self.keypress.into_iter().map(|k| 100.0 * k as f32 / tot)); + + let mut finger_usages = [0; 8]; + for (i, &c) in self.keypress.iter().enumerate() { + finger_usages[KEY_TO_FINGER[i]] += c; + } + + result += "finger usage: "; + for (i, &u) in finger_usages.iter().enumerate() { + result += &format!( + "{:>5.2}%{}", + u as f32 / tot * 100.0, + if i < 7 { ", " } else { "" } + ); + } + + result += "\nsame finger bigrams: "; + for (i, &u) in self.sfb.iter().enumerate() { + result += &format!( + "{:>6.3}%{}", + u as f32 / tot * 100.0, + if i < 7 { ", " } else { "" } + ); + } + + result += &format!( + "\ntotal sfb: {:.2}%", + self.sfb.iter().sum::() as f32 / tot * 100.0 + ); + + return result; + } + + // TODO + pub fn fitness(&self) -> f32 { + // let mut finger_usages = [0; 8]; + // let tot = self.total_keypress as f32; + // for (i, &c) in self.keypress.iter().enumerate() { + // finger_usages[KEY_TO_FINGER[i]] += c; + // } + // const MAX_FINGER_USAGES: [f32; 8] = [8.0, 11.0, 21.0, 21.0, 21.0, 21.0, 11.0, 8.0]; + // const MAX_FINGER_USAGES: [f32; 8] = + // [100.0, 100.0, 100.0, 100.0, 100.0, 100.0, 100.0, 100.0]; + // if finger_usages + // .iter() + // .enumerate() + // .any(|(i, &c)| c as f32 / tot * 100.00 > MAX_FINGER_USAGES[i]) + // { + // std::u32::MAX + // } else { + // self.sfb + // .iter() + // .enumerate() + // .map(|(i, &s)| s as f32 / finger_usages[i] as f32 * 50.0) + // .sum() + // } + self.sfb.iter().sum::() as f32 + } +} + +impl fmt::Display for Evaluation { + fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result { + formatter.write_str(&self.output_eval()) + } +} + +// This is a silly amount of work to genericise the below... +trait ToMyString { + const BLANK_STRING: &'static str; + fn to_my_string(&self) -> String; +} + +impl ToMyString for char { + const BLANK_STRING: &'static str = " "; + fn to_my_string(&self) -> String { + self.to_string() + } +} + +impl ToMyString for u32 { + const BLANK_STRING: &'static str = " "; + fn to_my_string(&self) -> String { + format!("{:5}", *self) + } +} + +impl ToMyString for f32 { + const BLANK_STRING: &'static str = " "; + fn to_my_string(&self) -> String { + format!("{:>4.1}", *self) + } +} + +fn format_block_output, S: ToMyString>(things: T) -> String { + let mut result = String::new(); + for (i, t) in things.enumerate() { + result += &t.to_my_string(); + if i < NUM_KEYS - 1 { + result.push(' '); + } + if (i + 1) % 10 == 0 { + result.push('\n'); + if NUM_KEYS < 30 && i == 19 { + result += S::BLANK_STRING; + result.push(' ') + } + } else if (i < 20 && (i + 1) % 5 == 0) || (i == (NUM_KEYS - 20) / 2 + 19) { + result.push(' '); + } + if i + 1 >= NUM_KEYS { + break; + } + } + return result; +} diff --git a/src/main.rs b/src/main.rs index 241ed3a..462d2fe 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,5 +1,6 @@ -use std::fmt; -use std::fs; +mod config; +mod corpus; +mod layout; use core::cmp::Ordering; use rayon::prelude::*; @@ -7,241 +8,14 @@ use rayon::prelude::*; use rand::prelude::*; use rand_pcg::*; -const NUM_KEYS: usize = 30; - -#[derive(Copy, Clone)] -struct Keyboard { - mappings: [u8; NUM_KEYS], -} - -#[derive(Copy, Clone)] -struct KeyboardEvaluation { - keypress: [u32; NUM_KEYS], - total_keypress: u32, - sfb: [u32; 8], -} - -impl Keyboard { - const KEY_TO_FINGER: [usize; NUM_KEYS] = [ - 0, 1, 2, 3, 3, 4, 4, 5, 6, 7, 0, 1, 2, 3, 3, 4, 4, 5, 6, 7, 0, 1, 2, 3, 3, 4, 4, 5, 6, 7, - ]; - - fn to_lookup(&self) -> [Option; 256] { - let mut result = [None; 256]; - for (i, m) in self.mappings.into_iter().enumerate() { - let index = Some(i); - if m.is_ascii_alphabetic() { - result[m.to_ascii_lowercase() as usize] = index; - result[m.to_ascii_uppercase() as usize] = index; - } else { - // For now we just hardcode this - match m { - b'.' => { - result[b'>' as usize] = index; - } - b',' => { - result[b'<' as usize] = index; - } - b'/' => { - result[b'?' as usize] = index; - } - b'\'' => { - result[b'"' as usize] = index; - } - _ => (), - } - result[m as usize] = index; - } - } - return result; - } - - fn from_verbose(inp: &str) -> Option { - let mut mappings: [u8; NUM_KEYS] = [0; NUM_KEYS]; - let mut k: usize = 0; - for c in inp.chars() { - let valid = (c.is_uppercase() && c.is_alphabetic()) - || c == '.' - || c == '/' - || c == ',' - || c == '\''; - if valid { - mappings[k] = c as u8; - k += 1; - } - if k > NUM_KEYS { - return None; - } - } - return Some(Keyboard { mappings }); - } - - fn new_random_from(kbd: &Keyboard, rng: &mut R) -> Keyboard { - let mut mappings = kbd.mappings; - mappings.shuffle(rng); - Keyboard { mappings } - } -} - -impl KeyboardEvaluation { - fn new() -> KeyboardEvaluation { - KeyboardEvaluation { - keypress: [0; NUM_KEYS], - sfb: [0; 8], - total_keypress: 0, - } - } - - fn evaluate_keyboard(kbd: &Keyboard, corpus: &str) -> KeyboardEvaluation { - let mut result = KeyboardEvaluation::new(); - let lookup_key = kbd.to_lookup(); - - let mut last_finger: Option = None; - for c in corpus.chars() { - let key = lookup_key[c as usize]; - if let Some(key_idx) = key { - result.total_keypress += 1; - let finger = Keyboard::KEY_TO_FINGER[key_idx]; - result.keypress[key_idx] += 1; - if let Some(last_finger) = last_finger { - if last_finger == finger { - result.sfb[last_finger] += 1; - } - } - last_finger = Some(finger); - } - } - return result; - } - - fn output_eval(&self) -> String { - let mut result = String::new(); - let tot = self.total_keypress as f32; - - result += &format!( - "Total keypresses: {}\nPercent per key:\n", - self.total_keypress - ); - result += &format_block_output(self.keypress.into_iter().map(|k| 100.0 * k as f32 / tot)); - - let mut finger_usages = [0; 8]; - for (i, &c) in self.keypress.iter().enumerate() { - finger_usages[Keyboard::KEY_TO_FINGER[i]] += c; - } - - result += "finger usage: "; - for (i, &u) in finger_usages.iter().enumerate() { - result += &format!( - "{:>5.2}%{}", - u as f32 / tot * 100.0, - if i < 7 { ", " } else { "" } - ); - } - - result += "\nsame finger bigrams: "; - for (i, &u) in self.sfb.iter().enumerate() { - result += &format!( - "{:>5.2}%{}", - u as f32 / finger_usages[i] as f32 * 50.0, - if i < 7 { ", " } else { "" } - ); - } - - result += &format!("\ntotal sfb: {}", self.sfb.iter().sum::()); - - return result; - } - - // TODO - fn fitness(&self) -> f32 { - let mut finger_usages = [0; 8]; - // let tot = self.total_keypress as f32; - for (i, &c) in self.keypress.iter().enumerate() { - finger_usages[Keyboard::KEY_TO_FINGER[i]] += c; - } - // const MAX_FINGER_USAGES: [f32; 8] = [8.0, 11.0, 21.0, 21.0, 21.0, 21.0, 11.0, 8.0]; - // const MAX_FINGER_USAGES: [f32; 8] = - // [100.0, 100.0, 100.0, 100.0, 100.0, 100.0, 100.0, 100.0]; - // if finger_usages - // .iter() - // .enumerate() - // .any(|(i, &c)| c as f32 / tot * 100.00 > MAX_FINGER_USAGES[i]) - // { - // std::u32::MAX - // } else { - self.sfb - .iter() - .enumerate() - .map(|(i, &s)| s as f32 / finger_usages[i] as f32 * 50.0) - .sum() - // } - } -} - -// This is a silly amount of work to genericise the below... -trait ToMyString { - const BLANK_STRING: &'static str; - fn to_my_string(&self) -> String; -} - -impl ToMyString for u8 { - const BLANK_STRING: &'static str = " "; - fn to_my_string(&self) -> String { - (*self as char).to_string() - } -} - -impl ToMyString for u32 { - const BLANK_STRING: &'static str = " "; - fn to_my_string(&self) -> String { - format!("{:5}", *self) - } -} - -impl ToMyString for f32 { - const BLANK_STRING: &'static str = " "; - fn to_my_string(&self) -> String { - format!("{:>4.1}", *self) - } -} - -fn format_block_output, S: ToMyString>(things: T) -> String { - let mut result = String::new(); - for (i, t) in things.enumerate() { - result += &t.to_my_string(); - if i < NUM_KEYS - 1 { - result.push(' '); - } - if (i + 1) % 10 == 0 { - result.push('\n'); - if NUM_KEYS < 30 && i == 19 { - result += S::BLANK_STRING; - result.push(' ') - } - } else if (i < 20 && (i + 1) % 5 == 0) || (i == (NUM_KEYS - 20) / 2 + 19) { - result.push(' '); - } - if i + 1 >= NUM_KEYS { - break; - } - } - return result; -} - -impl fmt::Display for Keyboard { - fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result { - formatter.write_str(&format_block_output(self.mappings.into_iter())) - } -} - -impl fmt::Display for KeyboardEvaluation { - fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result { - formatter.write_str(&self.output_eval()) - } -} +use corpus::*; +use layout::*; fn main() { - let starting_kbd = Keyboard::from_verbose( + let corpus = Corpus::load("chained_english_bigrams_1m.txt").unwrap(); + println!("{}", corpus); + + let starting_layout = Layout::from_verbose( " Y W F L M K P O , Q U R S N H D T E A I @@ -250,54 +24,51 @@ fn main() { ) .unwrap(); - // let contents = fs::read_to_string("books.txt").unwrap(); - let contents = fs::read_to_string("chained_english_bigrams_10k.txt").unwrap(); - let mut rng = Pcg64::from_entropy(); - type Fun = Vec<(Keyboard, KeyboardEvaluation, f32)>; + type Fun = Vec<(Layout, Evaluation, f32)>; let mut best = std::f32::INFINITY; - let mut kbds: Fun = (0..10) + let mut layouts: Fun = (0..10) .into_iter() .map(|i| { - let kbd; - if i > 0 { - kbd = Keyboard::new_random_from(&starting_kbd, &mut rng); + let layout; + if i >= 0 { + layout = Layout::new_random_from(&starting_layout, &mut rng); } else { - kbd = starting_kbd; + layout = starting_layout; } - let evl = KeyboardEvaluation::evaluate_keyboard(&kbd, &contents); + let evl = corpus.evaluate_layout(&layout); let fitness = evl.fitness(); - return (kbd, evl, fitness); + return (layout, evl, fitness); }) .collect(); - let mut counter = 0; - while counter < 1000000000 { - let new_layouts = kbds + let mut counter: u64 = 0; + while counter < 10000000000000 { + let new_layouts = layouts .iter() .enumerate() .map(|(i, (kbd, _, _))| { if i > 0 { - Keyboard::new_random_from(kbd, &mut rng) + Layout::new_random_from(kbd, &mut rng) } else { kbd.clone() } }) - .collect::>(); + .collect::>(); new_layouts .par_iter() - .map(|kbd| { - let evl = KeyboardEvaluation::evaluate_keyboard(kbd, &contents); + .map(|layout| { + let evl = corpus.evaluate_layout(layout); let fitness = evl.fitness(); - return (*kbd, evl, fitness); + return (*layout, evl, fitness); }) - .collect_into_vec(&mut kbds); + .collect_into_vec(&mut layouts); - kbds.sort_by(|(_, _, lfit), (_, _, rfit)| { + layouts.sort_by(|(_, _, lfit), (_, _, rfit)| { if lfit < rfit { Ordering::Less } else { @@ -305,14 +76,14 @@ fn main() { } }); - if kbds[0].2 < best { - best = kbds[0].2; + if layouts[0].2 < best { + best = layouts[0].2; println!(""); println!("================================================================================\nLayout:\n{}", - kbds[0].0 + layouts[0].0 ); - println!("{}\n{}", kbds[0].1, kbds[0].2); + println!("{}\n{}", layouts[0].1, layouts[0].2); } counter += 1; -- cgit v1.3.1