Задача из проекта Эйлера, 11 в Rust: крупный продукт последовательных элементов сетки 20х20


Вот мое решение проблемы 11 на проект Эйлера. Цель была найти наибольшее из четырех чисел в строчку подряд в любом направлении (по вертикали, горизонтали или диагонали). В то время как мой код достигается решение кажется неправильным для меня, в смысле я не совсем членораздельно. Я попытался реализовать псевдо-матрица структуры как ВМК от Vec после нахождения документов на существующие ящики имеем дело с матрицами довольно трудно понять. С текущим кодом я чувствую, что цикл слишком много раз. По сетке 20х20 это не проблема, но для большой сетки, это будет реальная проблема. Предложения по улучшению эффективности моего кода?

Ссылка на ржавчину площадка

struct Matrix {
    size: (usize, usize),
    rows: Vec<Vec<u32>>,
    cols: Vec<Vec<u32>>
}


fn new_matrix(row_size: usize, col_size: usize) -> Matrix {
    Matrix { size: (row_size, col_size), rows: Vec::with_capacity(row_size), cols: Vec::with_capacity(col_size) }
}


impl Matrix {
    fn cols_from_rows(&self) -> Vec<Vec<u32>> {
         let mut cols = vec![];
         for i in 0..(self.rows.len()) {
            let mut col = vec![];
            for j in 0..(self.rows[i].len()) {
                let item = *self.rows[j].iter().nth(i).unwrap();
                col.push(item);
             }
            cols.push(col);
         }
         cols
    }

    fn rows_from_cols(&self) -> Vec<Vec<u32>> {
        let mut rows = vec![];
        for i in 0..(self.cols.len()) {
            let mut row = vec![];
            for j in 0..(self.cols[i].len()) {
                let item = *self.cols[i].iter().nth(j).unwrap();
                row.push(item);
            }
            rows.push(row);
        }
        rows
    }

    fn matrix_row(&self, ndx: usize) -> Vec<u32> {
        let ref row = self.rows[ndx];
        row.to_vec()
    }

    fn matrix_column(&self, ndx: usize) -> Vec<u32> {
        let ref col = self.cols[ndx];
        col.to_vec()
    }

    fn matrix_diag_pos(&self, start_row: usize, start_col: usize, row_stride: usize, col_stride: usize) -> Vec<u32> {
        let mut diag = vec![];
        let mut cur_row = start_row;
        let mut cur_col = start_col;
        while cur_row < self.rows.len() && cur_col < self.cols.len() {
            diag.push(self.rows[cur_row][cur_col]);
            cur_row += row_stride;
            cur_col += col_stride;
        }
        diag
    }

    fn matrix_diag_neg(&self, start_row: usize, start_col: usize, row_stride: usize, col_stride: usize) -> Vec<u32> {
        let mut diag = vec![];
        let mut cur_row = start_row;
        let mut cur_col = start_col;
        while cur_col < self.cols.len() {
            diag.push(self.rows[cur_row][cur_col]);
            if cur_row != 0 { cur_row -= row_stride; } else { break }
            cur_col += col_stride; 
        }
        diag
    }
}

fn main() {
  let mut matrix = new_matrix(20, 20);
  matrix.rows = mtrx_rows();
  matrix.cols = matrix.cols_from_rows();
  let mut max_row_prod = 0u32;
  for i in 0..(matrix.rows.len()) {
      let current_row_prod = mult_windows(matrix.rows.iter().nth(i).unwrap().to_vec(), 4);
      if current_row_prod > max_row_prod {
          max_row_prod = current_row_prod;
      } else { max_row_prod; };
  }
  let mut max_col_prod = 0u32;
  for i in 0..(matrix.cols.len()) {
      let current_col_prod = mult_windows(matrix.cols.iter().nth(i).unwrap().to_vec(), 4);
      if current_col_prod > max_col_prod {
          max_col_prod = current_col_prod;
      } else { max_col_prod; };
  }
  let mut max_diag_prod = 0u32;
  let mut diags =vec![];
  for i in 0..(matrix.rows.len() - 3) {
    diags.push(matrix.matrix_diag_pos(0, i, 1, 1));
  }
  for i in (1..(matrix.rows.len() - 3)).rev() {
    diags.push(matrix.matrix_diag_pos(i,0,1,1));
  }
  for i in (3..(matrix.rows.len())).rev() {
    diags.push(matrix.matrix_diag_neg(i,0,1, 1));
  }
  for i in (0..(matrix.rows.len()-3)).rev() {
      diags.push(matrix.matrix_diag_neg(matrix.rows.len()-1,i,1,1));
  }
  for k in 0..diags.len() {
    let current_diag_prod = mult_windows(diags.iter().nth(k).unwrap().to_vec(), 4);
    if current_diag_prod > max_diag_prod {
        max_diag_prod = current_diag_prod;
    } else { max_diag_prod; };
  }
  println!("Max prod of diag sliced by four: {}", max_diag_prod);
  println!("Max prod of row sliced by four: {}", max_row_prod);
  println!("Max prod of col sliced by four: {}", max_col_prod);
}


fn mult_windows(num: Vec<u32>, window_size: usize) -> u32 {
    let mut prods = num.windows(window_size)
       .map(|i| i.iter().fold(1, |acc, &j| acc * j))
       .collect::<Vec<u32>>();
    prods.sort();
    *prods.last().unwrap()
}

fn mtrx_rows() -> Vec<Vec<u32>> {
    vec![vec![ 08,  02,  22,  97,  38,  15,  00,  40,  00,  75,  04,  05,  07,  78,  52,  12,  50,  77,  91,  08 ],
         vec![ 49,  49,  99,  40,  17,  81,  18,  57,  60,  87,  17,  40,  98,  43,  69,  48,  04,  56,  62,  00 ],
         vec![ 81,  49,  31,  73,  55,  79,  14,  29,  93,  71,  40,  67,  53,  88,  30,  03,  49,  13,  36,  65 ],
         vec![ 52,  70,  95,  23,  04,  60,  11,  42,  69,  24,  68,  56,  01,  32,  56,  71,  37,  02,  36,  91 ],
         vec![ 22,  31,  16,  71,  51,  67,  63,  89,  41,  92,  36,  54,  22,  40,  40,  28,  66,  33,  13,  80 ],
         vec![ 24,  47,  32,  60,  99,  03,  45,  02,  44,  75,  33,  53,  78,  36,  84,  20,  35,  17,  12,  50 ],
         vec![ 32,  98,  81,  28,  64,  23,  67,  10,  26,  38,  40,  67,  59,  54,  70,  66,  18,  38,  64,  70 ],
         vec![ 67,  26,  20,  68,  02,  62,  12,  20,  95,  63,  94,  39,  63,  08,  40,  91,  66,  49,  94,  21 ],
         vec![ 24,  55,  58,  05,  66,  73,  99,  26,  97,  17,  78,  78,  96,  83,  14,  88,  34,  89,  63,  72 ],
         vec![ 21,  36,  23,  09,  75,  00,  76,  44,  20,  45,  35,  14,  00,  61,  33,  97,  34,  31,  33,  95 ],
         vec![ 78,  17,  53,  28,  22,  75,  31,  67,  15,  94,  03,  80,  04,  62,  16,  14,  09,  53,  56,  92 ],
         vec![ 16,  39,  05,  42,  96,  35,  31,  47,  55,  58,  88,  24,  00,  17,  54,  24,  36,  29,  85,  57 ],
         vec![ 86,  56,  00,  48,  35,  71,  89,  07,  05,  44,  44,  37,  44,  60,  21,  58,  51,  54,  17,  58 ],
         vec![ 19,  80,  81,  68,  05,  94,  47,  69,  28,  73,  92,  13,  86,  52,  17,  77,  04,  89,  55,  40 ],
         vec![ 04,  52,  08,  83,  97,  35,  99,  16,  07,  97,  57,  32,  16,  26,  26,  79,  33,  27,  98,  66 ],
         vec![ 88,  36,  68,  87,  57,  62,  20,  72,  03,  46,  33,  67,  46,  55,  12,  32,  63,  93,  53,  69 ],
         vec![ 04,  42,  16,  73,  38,  25,  39,  11,  24,  94,  72,  18,  08,  46,  29,  32,  40,  62,  76,  36 ],
         vec![ 20,  69,  36,  41,  72,  30,  23,  88,  34,  62,  99,  69,  82,  67,  59,  85,  74,  04,  36,  16 ],
         vec![ 20,  73,  35,  29,  78,  31,  90,  01,  74,  31,  49,  71,  48,  86,  81,  16,  23,  57,  05,  54 ],
         vec![ 01,  70,  54,  71,  83,  51,  54,  69,  16,  92,  33,  48,  61,  43,  52,  01,  89,  19,  67,  48 ]
        ]

}


Комментарии
1 ответ

Отказ от ответственности: я не знаком с математикой на эту проблему - я добавила утверждает, чтобы код, чтобы убедиться, что он остается правильным!

Я думаю, что есть несколько изменений, которые вы могли бы сделать, чтобы сделать код более ржавчины-Y, и вы можете оптимизировать несколько вещей в процессе:


  • Если вы хотите, чтобы аннотации применять к своему окружению, вам нужно #! префикс - как она стоит, вы только отключен мертвого кода предупреждения Matrix структуры, а не остальной части кода.

  • Если вы создаете функцию, которая создает структуру, это обычный, чтобы быть прикреплены к структуре сам и называется new.

  • Вам не нужно указать u32 В конце числовых литералов в данном случае - компилятор может вывести их тип от их использования.

  • Обычно вам не нужно использовать явные индексы/диапазоны для перебора коллекции в Руст - for выражение может работать на чем угодно, что реализует IntoIterator! С помощью этого, можно удалить кучу unwrap шаблонный от основной функции.

  • Ваш другой ветки в для петли на самом деле не делаешь ничего - обратите внимание на 'путь без эффекта' предупреждение в выходных данных компилятора!

  • Это редкое, что вы когда-либо хотите сделать Vec в качестве параметра функция - ломтики являются более общими/гибкий. Также обратите внимание, что каждый раз, когда вы называете to_vecты не просто отливка, вы делаете копию данных. Я не знаю, что здесь узким местом в производительности, но это не обязательно в любом случае.

  • В общем, я думаю, что ты копирования/выделения векторов чаще, чем нужно :Р

  • Попробуйте использовать инструмент Скрепка (который имеется на детской площадке, или в командной строке программы) - он будет анализировать ваш код на типичные ошибки/вещи, которые unidiomatic. Например, он указал мне, что ваш fold в mult_windows на самом деле просто повторно реализует существующий итератор product способ!

Там, наверное, больше, что вы могли бы сделать, чем я сделал здесь (в частности, я думаю, что код, который вычисляет диагоналей может быть сделано с итераторами без особых проблем), но, надеюсь, ты в правильном направлении!

https://play.rust-lang.org/?gist=122310b496907b7da301a1d2987be837&version=stable

#![allow(dead_code)]

struct Matrix {
size: (usize, usize),
rows: Vec<Vec<u32>>,
cols: Vec<Vec<u32>>,
}

impl Matrix {
fn new(row_size: usize, col_size: usize) -> Matrix {
Matrix {
size: (row_size, col_size),
rows: Vec::with_capacity(row_size),
cols: Vec::with_capacity(col_size),
}
}

fn cols_from_rows(&self) -> Vec<Vec<u32>> {
let mut cols = vec![];
for row in &self.rows {
let mut col = vec![];
for item in row {
col.push(*item);
}
cols.push(col);
}
cols
}

fn rows_from_cols(&self) -> Vec<Vec<u32>> {
let mut rows = vec![];
for col in &self.cols {
let mut row = vec![];
for item in col {
row.push(*item);
}
rows.push(row);
}
rows
}

fn matrix_row(&self, ndx: usize) -> &[u32] {
&self.rows[ndx]
}

fn matrix_column(&self, ndx: usize) -> &[u32] {
&self.cols[ndx]
}

fn matrix_diag_pos(
&self,
start_row: usize,
start_col: usize,
row_stride: usize,
col_stride: usize,
) -> Vec<u32> {
let mut diag = vec![];
let mut cur_row = start_row;
let mut cur_col = start_col;
while cur_row < self.rows.len() && cur_col < self.cols.len() {
diag.push(self.rows[cur_row][cur_col]);
cur_row += row_stride;
cur_col += col_stride;
}
diag
}

fn matrix_diag_neg(
&self,
start_row: usize,
start_col: usize,
row_stride: usize,
col_stride: usize,
) -> Vec<u32> {
let mut diag = vec![];
let mut cur_row = start_row;
let mut cur_col = start_col;
while cur_col < self.cols.len() {
diag.push(self.rows[cur_row][cur_col]);
if cur_row != 0 {
cur_row -= row_stride;
} else {
break;
}
cur_col += col_stride;
}
diag
}
}

fn main() {
let mut matrix = Matrix::new(20, 20);

matrix.rows = mtrx_rows();
matrix.cols = matrix.cols_from_rows();

let mut max_row_prod = 0;

for row in &matrix.rows {
let current_row_prod = mult_windows(row, 4);
if current_row_prod > max_row_prod {
max_row_prod = current_row_prod;
}
}

let mut max_col_prod = 0;

for col in &matrix.cols {
let current_col_prod = mult_windows(col, 4);
if current_col_prod > max_col_prod {
max_col_prod = current_col_prod;
}
}

let mut max_diag_prod = 0;
let mut diags = vec![];

for i in 0..(matrix.rows.len() - 3) {
diags.push(matrix.matrix_diag_pos(0, i, 1, 1));
}

for i in (1..(matrix.rows.len() - 3)).rev() {
diags.push(matrix.matrix_diag_pos(i, 0, 1, 1));
}

for i in (3..(matrix.rows.len())).rev() {
diags.push(matrix.matrix_diag_neg(i, 0, 1, 1));
}

for i in (0..(matrix.rows.len() - 3)).rev() {
diags.push(matrix.matrix_diag_neg(matrix.rows.len() - 1, i, 1, 1));
}

for diag in &diags {
let current_diag_prod = mult_windows(diag, 4);
if current_diag_prod > max_diag_prod {
max_diag_prod = current_diag_prod;
}
}

println!("Max prod of diag sliced by four: {}", max_diag_prod);
println!("Max prod of row sliced by four: {}", max_row_prod);
println!("Max prod of col sliced by four: {}", max_col_prod);

assert_eq!(70_600_674, max_diag_prod);
assert_eq!(48_477_312, max_row_prod);
assert_eq!(51_267_216, max_col_prod);
}

fn mult_windows(num: &[u32], window_size: usize) -> u32 {
let mut prods = num.windows(window_size)
.map(|i| i.iter().product())
.collect::<Vec<u32>>();

prods.sort();
*prods.last().unwrap()
}

fn mtrx_rows() -> Vec<Vec<u32>> {
vec![
vec![
08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08,
],
vec![
49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00,
],
vec![
81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65,
],
vec![
52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91,
],
vec![
22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80,
],
vec![
24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50,
],
vec![
32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70,
],
vec![
67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63, 08, 40, 91, 66, 49, 94, 21,
],
vec![
24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72,
],
vec![
21, 36, 23, 09, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95,
],
vec![
78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 09, 53, 56, 92,
],
vec![
16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57,
],
vec![
86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58,
],
vec![
19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40,
],
vec![
04, 52, 08, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66,
],
vec![
88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69,
],
vec![
04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 08, 46, 29, 32, 40, 62, 76, 36,
],
vec![
20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16,
],
vec![
20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54,
],
vec![
01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48,
],
]
}

Редактировать:

Вы правы, что пока сам до сих пор требует ночью, но это не означает, что ваш код целевой ночам - если вы используете rustup для управления инструментов (вы должны!), вы можете сделать это:

cargo +nightly install clippy
cargo +nightly clippy

Это компилирует, устанавливает и запускает Скрепка в вечерних toolchain и без переключения по умолчанию от стабильной.

Что касается ссылки в for петли - это восходит к тому, что я говорю о for принимать что-либо, который реализует IntoIterator черта. &'a Vec<T> реализует IntoIterator таким образом, что for цикл может автоматически создать итератор &'a T когда вы пытаетесь перебрать его. Ты получишь тот же результат, делая for col in matrix.cols.iter().

При этом возникает вопрос: зачем вам & если Vec<T> также реализует IntoIterator? Это происходит потому, что IntoIterator реализации Vec<T> возвращает фактические значения из вектора, а не ссылки на них - так как данные могут иметь только одного владельца в Русте, в результате вы фактически извлекать данные из вектора, который не то, что вы хотите!

3
ответ дан 10 апреля 2018 в 11:04 Источник Поделиться