1
\$\begingroup\$

This implementation is the result of solving exercise 4-6 "Monge Arrays" from the book Introduction to algorithms.

Definition of a Monge Array:

An m x n array A of real numbers is a Monge array if for all \$i\$, \$j\$, \$k\$, and \$l\$ such that \$1 \le i \lt k \le m\$ and \$1 \le j \lt l \le n\$, we have \$A[i, j] + A[k, l] \le A[i, l] + A[k, j]\$.

Relevant parts of problem 4-6:

d. Here is a description of a divide-and-conquer algorithm that computes the left- most minimum element in each row of an m x n Monge array A:

Construct a submatrix A' of A consisting of the even-numbered rows of A. Recursively determine the leftmost minimum for each row of A'. Then compute the leftmost minimum in the odd-numbered rows of A. Explain how to compute the leftmost minimum in the odd-numbered rows of A (given that the leftmost minimum of the even-numbered rows is known) in \$O(m + n)\$ time.

e. Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution is \$O(m + nlog(m))\$.

I am especially interested in making my code more idiomatic and clean although any improvements to the algorithm are also welcome.

fn min(monge: &Vec<i32>, from: usize, to: usize) -> usize{

    let mut min = monge[from];

    (from + 1..to).fold(from, |m,i| {

        if(monge[i] < min){
            min = monge[i]; 
            i 
        } else{ m } 
    })
}


fn minimums(monge: &Vec<i32>, leftmost: & mut Vec<usize>, rows: usize, columns: usize, factor: usize)
{

    if rows == 1 {  
        leftmost[0] = min(monge, 0, columns) % columns;
    }
    else {

        let mid = rows - (rows / 2);
        minimums(monge, leftmost, mid, columns, 2 * factor);          

        let get = |i, j| (i * columns) + j;

        for row in (0..)
                       .map(|x| factor * (2 * x + 1))
                       .take_while(|&x| x < (rows - 1)) {

            leftmost[row] =  min(monge, 
                                 get(row ,leftmost[row - factor]), 
                                 get(row, leftmost[row + factor] + 1)) % columns; 
        }

        if rows % 2 == 0 {

            let row = factor * (rows - 1);
            leftmost[row] = min(monge,
                                get(row , leftmost[row - factor]),
                                get(row, columns)) % columns; 
        }

    }
}

fn main() {

    let row = 7;
    let x = vec!
    [10,17,13,28,23,
     17,22,16,29,23,
     24,28,22,34,24,
     11,13,6,17,7,
     45,44,32,37,23,
     36,33,19,21,6,
     75,66,51,53,34];

    let mut leftmost = vec![0;row];

    minimums(&x, &mut leftmost, row,5, 1);

    for x in leftmost { 
        println!("{}", x);    
    }

}
\$\endgroup\$
1
\$\begingroup\$
  1. Read compiler warnings and fix them:

    src/main.rs:7:11: 7:27 warning: unnecessary parentheses around `if` condition, #[warn(unused_parens)] on by default
    src/main.rs:7         if(monge[i] < min){
                            ^~~~~~~~~~~~~~~~
    
  2. Spaces before braces

    fn min(...) -> usize{ // No
    fn min(...) -> usize { // Yes
    
  3. Be consistent about brace indentation

    // No
    if {
        1
    } else { 2 }
    
    // Yes
    if {
        1
    } else {
        2
    }
    
  4. mut is stuck to the &

    & mut Vec<usize> // No
    &mut Vec<usize> // Yes
    
  5. else lives on the same line as the previous curly brace

    // No
    if true {
        1
    }
    else {
        2
    }
    
    // Yes
    if true {
        1
    } else {
        2
    }
    
  6. No need to leave blank space at the beginning of a block

    // No
    fn foo() {
    
        let a = 1;
    
    // Yes
    fn foo() {
        let a = 1;
    
  7. Keep the macro braces attached to the macro name, and indent the body if it's going to be multiline. Leave a trailing comma, and use spaces after the comma

    let x = vec![
        10, 17, 13, 28, 23, 
        17, 22, 16, 29, 23, 
        24, 28, 22, 34, 24, 
        11, 13,  6, 17,  7, 
        45, 44, 32, 37, 23, 
        36, 33, 19, 21,  6, 
        75, 66, 51, 53, 34,
    ];
    
  8. Leave spaces after commas in function calls as well, but not before

    // No
    get(row ,leftmost[row - factor]),
    
    // Yes
    get(row, leftmost[row - factor]),
    
  9. A single space around =

    leftmost[row] =  min(...); // No
    leftmost[row] = min(...); // Yes
    
  10. Never take a &Vec<T> as an argument, use a &[T] instead. This allows more types to be provided

  11. Your min function is poorly named. The name seems to suggest it will return the minimum value, when it actually returns the index of the minimum value. Rename it to something intention-revealing. Maybe index_of_minimum

  12. Space after a ; in an array or vector

    vec![0;row]; // No
    vec![0; row]; // Yes
    
  13. Instead of having multiple lines in a for x in y clause, create a variable to store that in.

    // Poor name because I'm not sure what it really is
    let x_rows = (0..)
        .map(|x| factor * (2 * x + 1))
        .take_while(|&x| x < (rows - 1));
    
    for row in x_rows {
    
  14. Eventually, min_by will be stabilized, and you can use it:

    // May be off-by-one errors here
    let (min_index, _) =
        monge.iter()
        .enumerate()
        .skip(from)
        .take(to - from)
        .min_by(|&(_, v)| v)
        .unwrap();
    min_index
    

I'm sure there's more that can be suggested, but my brain is tired for now ^_^.

fn index_of_minimum(monge: &[i32], from: usize, to: usize) -> usize {
    let mut min = monge[from];

    (from + 1..to).fold(from, |m,i| {
        if monge[i] < min {
            min = monge[i];
            i
        } else {
            m
        }
    })
}

fn minimums(monge: &[i32], leftmost: &mut Vec<usize>, rows: usize, columns: usize, factor: usize) {
    if rows == 1 {
        leftmost[0] = index_of_minimum(monge, 0, columns) % columns;
    } else {
        let mid = rows - (rows / 2);
        minimums(monge, leftmost, mid, columns, 2 * factor);

        let get = |i, j| (i * columns) + j;

        let x_rows = (0..)
            .map(|x| factor * (2 * x + 1))
            .take_while(|&x| x < (rows - 1));

        for row in x_rows {
            leftmost[row] = index_of_minimum(monge,
                                get(row, leftmost[row - factor]),
                                get(row, leftmost[row + factor] + 1)) % columns;
        }

        if rows % 2 == 0 {
            let row = factor * (rows - 1);
            leftmost[row] = index_of_minimum(monge,
                                get(row, leftmost[row - factor]),
                                get(row, columns)) % columns;
        }
    }
}

fn main() {
    let row = 7;
    let x = vec![
        10, 17, 13, 28, 23,
        17, 22, 16, 29, 23,
        24, 28, 22, 34, 24,
        11, 13,  6, 17,  7,
        45, 44, 32, 37, 23,
        36, 33, 19, 21,  6,
        75, 66, 51, 53, 34,
    ];

    let mut leftmost = vec![0; row];

    minimums(&x, &mut leftmost, row, 5, 1);

    for x in leftmost {
        println!("{}", x);
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.