Code Review: Транспортная задача

Тех.вопросы
1

Добрый день.
Хотелось бы увидеть дельные замечания к нему.
Интересует оценка по всем возможным параметрам, например: оптимальность, читаемость (название функций и переменных), понятность комментариев (и в каких местах необходимо убрать или добавить) и т.п.
Также хочется узнать общее впечатление о коде.

Это реализация решения транспортной задачи. Первоначальный план составляется с помощью метода наименьшей стоимости, затем план улучшается с помощью метода потенциалов.
Если по каким-то причинам вы не понимаете о чем идет речь, то вы можете ознакомится с задачей: http://www.resolventa.ru/data/metodstud/transproblem.pdf

Ссылка на reviewable.io

Пример входного файла:

160 30 90
100 40 80 60
4 8 10 5
4 6 2 3
4 4 6 5
2

Ссылка на код

3

  • Вместо .ok().expect(...) уже можно писать просто .expect(...).

  • Vec<Vec<>> - лучше заменить на один буфер.

  • use std::io::prelude::*; - тож странная штука

  • Несколько табов закралось.

1 лайк
5

В смысле не использовать двумерные массивы? Не то что бы я не знал о таком подходе, но это не удобно и так ли велика экономия?

6

Наверное, это субъективно все, но мне больше по душе абстрагироваться от внутреннего представления - https://github.com/ozkriff/zoc/blob/940cf6/src/core/src/map.rs#L20-L23

Да и координаты тоже объединять в единую сущность “позиция” - https://github.com/ozkriff/zoc/blob/940cf6/src/core/src/map.rs#L45-L49

7

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

use std::ops::{Index, IndexMut};

use std::vec::Vec;

// TODO error handling
#[derive(Default)]
pub struct Pixmap {
    w: usize,
    h: usize,

    data: Vec<i32>,
}

impl Pixmap {
    pub fn new(w: usize, h: usize, fill_value: i32) -> Pixmap {
        Pixmap {
            w: w,
            h: h,
            data: vec![fill_value; w*h],
        }
    }

    pub fn fill(&mut self, fill_value: i32) {
        self.data = vec![fill_value; self.w*self.h]
    }

    pub fn width(&self) -> usize {
        self.w
    }
    pub fn height(&self) -> usize {
        self.h
    }

    pub fn get(&self, x: i32, y: i32) -> i32 {
        if x < 0 || y < 0 {
            return 0;
        }
        if x >= self.w as i32 || y >= self.h as i32 {
            return 0;
        }

        self[x as usize][y as usize]
    }
}

impl Index<usize> for Pixmap {
    type Output = [i32];

    #[inline]
    fn index<'a>(&'a self, _index: usize) -> &'a Self::Output {
        let i = _index * self.w;

        &self.data[i..i + self.w]
    }
}

impl IndexMut<usize> for Pixmap {
    #[inline]
    fn index_mut<'a>(&'a mut self, _index: usize) -> &'a mut Self::Output {
        let i = _index * self.w;

        &mut self.data[i..i + self.w]
    }
}

#[test]
fn test_slice() {
    let w = 100;
    let h = 100;

    let mut p = Pixmap::new(w, h, 0);

    p[10][10] = 10;

    assert!(p[10][10] == p.data[10 * w + 10]);
}

К тому же, чаще всего, сишные апи именно в таком формате жрут многомерные массивы.

8

Если честно, это такая муть для меня. Вроде звучит здорово, но это ломает мне все итераторы.
Особенно вот здесь и здесь.
И тут начинаются варианты, как это можно исправить. Можно реализовать свой итератор, но внутри него все равно будет доступ по индексу и тогда появляется вопрос, а зачем я вообще использую итераторы для доступа.
Ведь я только только отказался от индексов по совету @defuz. Конечно там и без этого было что изменить, но суть не в этом.
Можно индексировать такими выражениями (i/self.cost.w,i%self.cost.w), но действительно ли оправданно использовать деление на каждой итерации цикла вместо хранения вложенного вектора? Да и читабельность резко снижается.

9

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

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

Если это сделать никак не получится, то по крайней мере можно ввести тип Matrix, пусть даже внутри будет все тот же Vec<Vec<_>>.

1 лайк
10

Можно, добавление идет в самом начале и его можно сделать во время инициализации, но я так и не понял что мне делать с итераторами? Получается проще все сделать через индексы.