Как мне удобно конвертировать 2-мерный массив в 2-мерный вектор? - PullRequest
Новая
       7

Как мне удобно конвертировать 2-мерный массив в 2-мерный вектор?

0 голосов
/ 30 апреля 2018

Я следую учебному пособию Rust-wasm и хочу легко добавить корабль (действительно форму) во Вселенную в игре жизни.

В качестве первого шага я хотел бы преобразовать двумерный массив 0 или 1, представляющий форму, в вектор индексов, представляющих координаты формы во Вселенной.

У меня есть рабочий код, но я бы хотел сделать его немного более удобным для пользователя: 

const WIDTH: u32 = 64;
const HEIGHT: u32 = 64;

/// glider: [[0, 1, 0], [0, 0, 1], [1, 1, 1]]
fn make_ship(shape: Vec<Vec<u32>>) -> Vec<u32> {
    let mut ship: Vec<u32> = Vec::new();

    for row_idx in 0..shape.len() {
        for col_idx in 0..shape[row_idx].len() {
            let cell = shape[row_idx][col_idx];
            if cell == 1 {
                ship.push(col_idx as u32 + row_idx as u32 * WIDTH);
            }
        }
    }

    ship
}

#[test]
fn glider() {
    let glider  = vec![vec![0, 1, 0], vec![0, 0, 1], vec![1, 1, 1]];
    println!("{:?}", make_ship(glider));
}

test показывает мою проблему: многословие vec! с. В идеале я хотел бы иметь возможность написать это без всего vec!. Код make_ship не должен заботиться о размере массивов форм. Идеальный пример: 

let glider = [[0, 1, 0],
              [0, 0, 1],
              [1, 1, 1],];

Вопрос в том, как красиво выразить фигуру с помощью простых массивов и иметь функцию make_ship, берущую 2-мерные векторы произвольного размера?

Ответы [ 3 ]

0 голосов
/ 30 апреля 2018

Vec<Vec<_>> на самом деле не 2-мерный вектор, а "вектор векторов". Это имеет важные последствия (при условии, что внешний вектор интерпретируется как строки, а внутренний как столбцы):

  1. Строки могут иметь разную длину. Это часто не то, что вы хотели бы.
  2. Строки - это отдельные объекты, которые могут быть разбросаны по всей куче памяти.
  3. Чтобы получить доступ к элементу, вы должны следовать двум указаниям.

Я бы реализовал 2-мерный вектор, а не 1-мерный вектор с дополнительной информацией относительно его размеров. Что-то вроде: 

struct Vec2D<T> {
    n_rows: usize,  // number of rows
    n_cols: usize,  // number of columns (redundant, since we know the length of data)
    data: Vec<T>,   // data stored in a contiguous 1D array
}

Эту структуру можно инициализировать с помощью 

let glider = Vec2D {
    n_rows: 3,
    n_cols: 3,
    data: vec![0, 1, 0, 
               0, 0, 1, 
               1, 1, 1],
};

Или удобнее с функциями или макросами, которые принимают массивы массивов. (См. @ ljedrz ответ для вдохновения).

Чтобы получить доступ к элементу в структуре, вам понадобится немного математики для преобразования 2D-индекса в 1D-индекс: 

impl<T> Vec2D<T> {
    fn get(&self, row: usize, col: usize) -> &T {
         assert!(row < self.n_rows);
         assert!(col < self.n_cols);
         &self.data[row * self.n_cols + col]
    }
}

Хотя реализация вашего собственного двумерного типа массива - забавное упражнение, для продуктивного использования может быть более эффективно использовать существующее решение, такое как ndarray crate .

0 голосов
/ 30 апреля 2018

Другое решение заключается в прозрачной обработке Vec<T> и [T] с использованием AsRef: 

fn make_ship<T>(shape: &[T]) -> Vec<u32>
where
    T: AsRef<[u32]>,
{
    let mut ship: Vec<u32> = Vec::new();

    for row_idx in 0..shape.len() {
        let row = shape[row_idx].as_ref();
        for col_idx in 0..row.len() {
            let cell = row[col_idx];
            if cell == 1 {
                ship.push(col_idx as u32 + row_idx as u32 * WIDTH);
            }
        }
    }

    ship
}

Это обрабатывает следующее: 

let glider = vec![vec![0, 1, 0], vec![0, 0, 1], vec![1, 1, 1]];
let glider = [[0, 1, 0], [0, 0, 1], [1, 1, 1]];
let glider = [vec![0, 1, 0], vec![0, 0, 1], vec![1, 1, 1]];
let glider = vec![[0, 1, 0], [0, 0, 1], [1, 1, 1]];

Еще лучшее решение - вообще не заботиться о срезах / векторах и использовать итераторы: 

fn make_ship<'a, T, U>(shape: &'a T) -> Vec<u32>
where
    &'a T: std::iter::IntoIterator<Item = U>,
    U: std::iter::IntoIterator<Item = &'a u32>,
{
    let mut ship: Vec<u32> = Vec::new();

    for (row_idx, row) in shape.into_iter().enumerate() {
        for (col_idx, &cell) in row.into_iter().enumerate() {
            if cell == 1 {
                ship.push(col_idx as u32 + row_idx as u32 * WIDTH);
            }
        }
    }

    ship
}

, который также обрабатывает описанные выше случаи, но может также обрабатывать тип, такой как @ 1013 * @ kazemakase, если он предоставляет такие итераторы.

0 голосов
/ 30 апреля 2018

Уменьшение количества vec! с возможно с помощью пользовательского макроса : 

#[macro_export]
macro_rules! vec2d {
    ($($i:expr),+) => { // handle numbers
        {
            let mut ret = Vec::new();
            $(ret.push($i);)*
            ret
        }
    };

    ([$($arr:tt),+]) => { // handle sets
        {
            let mut ret = Vec::new();
            $(ret.push(vec!($arr));)*
            ret
        }
    };
}

fn main() {
    let glider = vec2d![[0, 1, 0],
                        [0, 0, 1],
                        [1, 1, 1]];

    let glider2 = vec2d![[0, 1, 0, 1],
                         [0, 0, 1, 0],
                         [1, 1, 1, 0],
                         [0, 1, 1, 0]];


    println!("{:?}", glider);  // [[0, 1, 0], [0, 0, 1], [1, 1, 1]]
    println!("{:?}", glider2); // [[0, 1, 0, 1], [0, 0, 1, 0], [1, 1, 1, 0], [0, 1, 1, 0]]
}

Ваша первоначальная функция также может использовать некоторые улучшения с помощью итераторов Rust: 

fn make_ship(shape: Vec<Vec<u32>>) -> Vec<u32> {
    shape
        .iter()
        .enumerate()
        .flat_map(|(row, v)| {
            v.iter().enumerate().filter_map(move |(col, x)| {
                if *x == 1 {
                    Some(col as u32 + row as u32 * WIDTH)
                } else {
                    None
                }
            })
        })
        .collect()
}
...