3
\$\begingroup\$

I've blatantly copied fejesjoco's solotion to this codegolf into Rust, and was hoping for some feedback.

Basically, it begins by generating a vector containing every possible 15-bit RGB color, and then randomizes it. In addition, a blank image buffer is created, and a 2-d vector is initialized to represent the image. The algorithm places the first pixel in the middle of the vector, then begins placing pixels directly next to the pixel they are closest in color to. I'm very new to Rust, and fairly new to programming in general, so I'm sure there's a lot that could be optimized here. Currently I'm initializing the whole array to a default gray that is not a a 15-bit color, so I can check if a pixel has been overwritten yet. This in particular seems suboptimal. Optimizing software isn't something I've ever really done before, so your help is greatly appreciated!

extern crate image;
extern crate rand;

use image::{ImageBuffer, Rgb};
use std::path::Path;
use std::collections::HashSet;
use rand::{thread_rng, Rng};

const NUMCOLORS: u8 = 32;
const WIDTH: u32 = 256;
const HEIGHT: u32 = 128;
const STARTX: u32 = 128;
const STARTY: u32 = 64;
// default color to initialize the picture to
const DEFCOL: Rgb<u8> = Rgb {data: [1, 1, 1]};

#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
struct Pt {
    x: u32,
    y: u32,
}

impl Pt {
    fn get_neighbors(&self) -> Vec<Pt> {
        let mut neighbors: Vec<Pt> = Vec::new();
        let x = self.x as i16;
        let y = self.y as i16;
        for dx in -1..2 {
            if dx + x == -1 || dx + x == WIDTH as i16 { continue; }
            for dy in -1..2 {
                if dy + y == -1 || dy + y == HEIGHT as i16 || (dy == 0 && dx == 0) { continue; }
                neighbors.push( Pt {x: (x + dx) as u32, y: (y + dy) as u32});
            }
        }
        neighbors
    }

    fn color_diff(&self, pixels: &Vec<Vec<Rgb<u8>>>, col: Rgb<u8>) -> u32 {
        self.get_neighbors()
            .iter()
            .filter(|pt| pixels[pt.x as usize][pt.y as usize] != DEFCOL)
            .map(|pt| coldiff(col, pixels[pt.x as usize][pt.y as usize]))
            .min()
            .unwrap()
    }
}

// Gets the difference between two colors
fn coldiff(col1: Rgb<u8>, col2: Rgb<u8>) -> u32 {
    let dr = col1[0] as i32 - col2[0] as i32;
    let dg = col1[1] as i32 - col2[1] as i32;
    let db = col1[2] as i32 - col2[2] as i32;
    (dr * dr + dg * dg + db * db) as u32
}

fn main() {
    // initialize the image to contain a default grey color
    let mut img: ImageBuffer<Rgb<u8>, Vec<u8>> = ImageBuffer::from_pixel(WIDTH, HEIGHT, DEFCOL);

    // Create a vector of all possible colors, then randomize it
    let mut cols: Vec<Rgb<u8>> = Vec::new();
    for r in 0..NUMCOLORS {
        for g in 0..NUMCOLORS {
            for b in 0..NUMCOLORS {
                cols.push( Rgb {data: [r * 8 as u8, g * 8 as u8, b * 8 as u8]});
            }
        }
    }
    thread_rng().shuffle(&mut cols);
    let mut pixels: Vec<Vec<Rgb<u8>>> = vec![vec![DEFCOL; HEIGHT as usize]; WIDTH as usize];
    let mut available: HashSet<Pt> = HashSet::new();

    let mut best_pt = Pt {x: STARTX, y: STARTY};
    pixels[best_pt.x as usize][best_pt.y as usize] = cols[0];

    for nei in best_pt.get_neighbors() {
        available.insert(nei);
    }

    for i in 1..(HEIGHT * WIDTH) {
        best_pt = *available.iter().min_by_key(|pt| pt.color_diff(&pixels, cols[i as usize])).unwrap();

        if i % 100 == 0 {
            println!("i = {}", i);

        }

        pixels[best_pt.x as usize][best_pt.y as usize] = cols[i as usize];

        available.remove(&best_pt);
        for nei in best_pt.get_neighbors() {
            if pixels[nei.x as usize][nei.y as usize] == DEFCOL {
                available.insert(nei);
            }
        }
    }

    for i in 0..HEIGHT {
        for j in 0..WIDTH {
            img.put_pixel(j, i, pixels[j as usize][i as usize]);
        }
    }

    let _ = img.save(Path::new("image9.png"));
}
\$\endgroup\$
  • \$\begingroup\$ I'm tempted to downvote because, of all questions, this one could easily have a pretty picture added and be relevant. :-p \$\endgroup\$ – Shepmaster Mar 25 '17 at 16:52
1
\$\begingroup\$
  1. Rust constants use underscores to separate words.

  2. If the start point is supposed to be the middle, encode that by saying width / 2, for example.

  3. coldiff could easily be read as "column". Avoid ambiguous abbreviations.

  4. Instead of documenting a section of code, extract a function and use the comment as the name. Note that this also constrains the area of mutability.

  5. The casts of r, g, b to u8 are redundant.

  6. Normally, I'd recommend using Iterator::collect instead of manually pushing to a vector, but it's a bit trickier because you are doing a Cartesian product. Itertools does have a cartesian_product, but you want the product of 3 iterators. Using Itertools would look something like:

    let mut cols: Vec<_> = (0..NUM_COLORS)
        .cartesian_product(0..NUM_COLORS)
        .cartesian_product(0..NUM_COLORS)
        .map(|((r, g), b)| {
            Rgb { data: [r * 8, g * 8, b * 8] }
        })
        .collect();
    

    The main benefit of doing this is that the vector will be pre-allocated to exactly the right number of elements, avoiding any extra reallocation.

    If you don't like the Itertools solution, you should instead use Vec::with_capacity to get the same allocation efficiency.

  7. Don't define types of variables unless needed. Let type inference do its job.

  8. Instead of initializing the output image to a gray, use ImageBuffer::from_fn. Note that this removes mutability as well.

  9. Don't ignore errors, especially errors that are highly likely to happen like file IO. Use expect to kill the program if you need to.

extern crate image;
extern crate rand;

use image::{ImageBuffer, Rgb};
use std::path::Path;
use std::collections::HashSet;
use rand::{thread_rng, Rng};

const NUM_COLORS: u8 = 32;
const WIDTH: u32 = 256;
const HEIGHT: u32 = 128;
const START_X: u32 = WIDTH / 2;
const START_Y: u32 = HEIGHT / 2;


const DEFAULT_COLOR: Rgb<u8> = Rgb { data: [1, 1, 1] };

#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
struct Pt {
    x: u32,
    y: u32,
}

impl Pt {
    fn get_neighbors(&self) -> Vec<Pt> {
        let mut neighbors = Vec::new();
        let x = self.x as i16;
        let y = self.y as i16;
        for dx in -1..2 {
            if dx + x == -1 || dx + x == WIDTH as i16 {
                continue;
            }
            for dy in -1..2 {
                if dy + y == -1 || dy + y == HEIGHT as i16 || (dy == 0 && dx == 0) {
                    continue;
                }
                neighbors.push(Pt {
                                   x: (x + dx) as u32,
                                   y: (y + dy) as u32,
                               });
            }
        }
        neighbors
    }

    fn color_diff(&self, pixels: &Vec<Vec<Rgb<u8>>>, col: Rgb<u8>) -> u32 {
        self.get_neighbors()
            .iter()
            .filter(|pt| pixels[pt.x as usize][pt.y as usize] != DEFAULT_COLOR)
            .map(|pt| color_diff(col, pixels[pt.x as usize][pt.y as usize]))
            .min()
            .unwrap()
    }
}

fn color_diff(col1: Rgb<u8>, col2: Rgb<u8>) -> u32 {
    let dr = col1[0] as i32 - col2[0] as i32;
    let dg = col1[1] as i32 - col2[1] as i32;
    let db = col1[2] as i32 - col2[2] as i32;
    (dr * dr + dg * dg + db * db) as u32
}

fn all_colors_random() -> Vec<Rgb<u8>> {

    let mut cols = Vec::new();
    for r in 0..NUM_COLORS {
        for g in 0..NUM_COLORS {
            for b in 0..NUM_COLORS {
                cols.push(Rgb { data: [r * 8, g * 8, b * 8] });
            }
        }
    }
    thread_rng().shuffle(&mut cols);
    cols
}

fn main() {
    let mut pixels = vec![vec![DEFAULT_COLOR; HEIGHT as usize]; WIDTH as usize];
    let mut available = HashSet::new();

    let cols = all_colors_random();

    let mut best_pt = Pt {
        x: START_X,
        y: START_Y,
    };
    pixels[best_pt.x as usize][best_pt.y as usize] = cols[0];

    for nei in best_pt.get_neighbors() {
        available.insert(nei);
    }

    for i in 1..(HEIGHT * WIDTH) {
        best_pt =
            *available.iter().min_by_key(|pt| pt.color_diff(&pixels, cols[i as usize])).unwrap();

        if i % 100 == 0 {
            println!("i = {}", i);

        }

        pixels[best_pt.x as usize][best_pt.y as usize] = cols[i as usize];

        available.remove(&best_pt);
        for nei in best_pt.get_neighbors() {
            if pixels[nei.x as usize][nei.y as usize] == DEFAULT_COLOR {
                available.insert(nei);
            }
        }
    }

    let img = ImageBuffer::from_fn(WIDTH, HEIGHT, |j, i| {
        pixels[j as usize][i as usize]
    });

    img.save(Path::new("image9.png")).expect("Unable to write image")
}

I'm not a fan of using the gray as a sentinel value. Instead, let's try a HashMap. This points out some other aspects...

  1. Just define a START_POINT constant; there's no need to split it up into two.

  2. We can use cartesian_product for the implementation of neighbors.

  3. We can even return a boxed iterator from neighbors, instead of allocating a Vec. If you really wanted to drive it down, you could create a custom iterator that requires no allocation.

  4. Note that by using a HashMap, we've reduced the need for casting of integers and indexing of arrays.

  5. Always prefer expect over unwrap. When something fails, you'll be happier.

  6. I introduced a type alias, this is one step towards having a real type.

  7. Instead of recalculate the height / width and indexing into the color array, iterate through the colors.

  8. There's no need to use a get_ prefix on a method. That's the default / assumed verb.

extern crate image;
extern crate rand;
extern crate itertools;

use std::collections::{HashMap, HashSet};
use std::path::Path;

use image::{ImageBuffer, Rgb};
use itertools::Itertools;
use rand::{thread_rng, Rng};

const NUM_COLORS: u8 = 32;
const WIDTH: u32 = 256;
const HEIGHT: u32 = 128;
const START_POINT: Pt = Pt { x: WIDTH / 2, y: HEIGHT / 2 };

#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
struct Pt {
    x: u32,
    y: u32,
}

impl From<(u32, u32)> for Pt {
    fn from(other: (u32, u32)) -> Self {
        Pt {
            x: other.0,
            y: other.1,
        }
    }
}

impl Pt {
    fn neighbors(&self) -> Box<Iterator<Item = Pt>> {
        let x = self.x as i16;
        let y = self.y as i16;

        let i = (-1..2).cartesian_product(-1..2)
            .filter(|&(dx, dy)| dx == 0 && dy == 0)
            .map(move |(dx, dy)| (dx + x, dy + y))
            .filter(|&(x, _)| x != -1 && x != WIDTH as i16)
            .filter(|&(_, y)| y != -1 && y != HEIGHT as i16)
            .map(|(x, y)| (x as u32, y as u32))
            .map(Into::into);

        Box::new(i)
    }

    fn color_diff(&self, pixels: &AssignedPixels, col: Rgb<u8>) -> u32 {
        self.neighbors()
            .filter_map(|neighbor| pixels.get(&neighbor))
            .map(|&pixel| color_diff(col, pixel))
            .min()
            .expect("Unable to do color diff")
    }
}

type AssignedPixels = HashMap<Pt, Rgb<u8>>;

fn color_diff(col1: Rgb<u8>, col2: Rgb<u8>) -> u32 {
    let dr = col1[0] as i32 - col2[0] as i32;
    let dg = col1[1] as i32 - col2[1] as i32;
    let db = col1[2] as i32 - col2[2] as i32;
    (dr * dr + dg * dg + db * db) as u32
}

fn all_colors_random() -> Vec<Rgb<u8>> {
    let mut colors = Vec::new();
    for r in 0..NUM_COLORS {
        for g in 0..NUM_COLORS {
            for b in 0..NUM_COLORS {
                colors.push(Rgb { data: [r * 8, g * 8, b * 8] });
            }
        }
    }
    thread_rng().shuffle(&mut colors);
    colors
}

fn main() {
    let colors = all_colors_random();
    let mut available = HashSet::new();
    let mut pixels = AssignedPixels::new();

    for color in colors {
        let best_pt = available.iter()
            .min_by_key(|pt: &&Pt| pt.color_diff(&pixels, color))
            .cloned()
            .unwrap_or(START_POINT);

        available.remove(&best_pt);
        available.extend(best_pt.neighbors().filter(|neighbor| {
            !pixels.contains_key(&neighbor)
        }));

        pixels.insert(best_pt, color);
    }

    let img = ImageBuffer::from_fn(WIDTH, HEIGHT, |x, y| {
        let pt = Pt { x: x, y: y };
        pixels[&pt]
    });

    img.save(Path::new("image9.png")).expect("Unable to write image")
}

How does it stack up in performance? The first version I posted takes an average of 4.1 seconds over 10 runs, while my "improved" version takes 8.9. Not that impressive, eh?

Some light profiling points to the call to pixels.get in color_diff as the main culprit. My suspicion is that it's pretty hard to beat the data locality of a giant slab of memory!

\$\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.