In below, the method place_pieces() takes 12+ seconds, but the Java codes with the same logics of exactly sovling the same problem only takes 3.7 seconds, although it outputs the same result as Java version does. I try to pinpoint the bottleneck, so I measured the time each block of codes takes in the core method. What I found is that all blocks are quite time-consuming except for t2 - t1. I don't understand why this is happening and how to improve, please help me out.
One weird thing is that all println!() statements basically print time dif larger than zero in VSCode using cargo run command, but in the command line(Windows 10) they all basically print zero, but the total time taken by place_pieces() method doesn't appear much different after commenting out the four println!() statements in the method place_a_piece(). What the hell is going on?
fn place_pieces(&mut self, config:&Config2) -> Vec<StateInShape>{
let mut states_in_shape:Vec<StateInShape>=Vec::new();
let mut ids:HashSet<&str>=HashSet::with_capacity(90000);
let mut remaining_piece_ids:Vec<u8>=Vec::new();
let mut cells_to_occupy:Vec<usize>=Vec::with_capacity(4);
for piece_num in &self.piece_ids_sorted_by_free_degree {
remaining_piece_ids.push(*piece_num);
}
let mut state_in_shape=StateInShape{
id:"",
offsets:[33;10],
cells:[33;20],
};
state_in_shape.id(self, None);
ids.insert(&state_in_shape.id);
states_in_shape.push(state_in_shape);
return self.place_pieces_recursion(states_in_shape, &mut ids, &mut remaining_piece_ids, config, &mut cells_to_occupy);
}
fn place_pieces_recursion(&mut self, mut states_in_shape:Vec<StateInShape>, ids:&mut HashSet<&str>, remaining_piece_ids:&mut Vec<u8>, config:&Config2, cells_to_occupy:&mut Vec<usize>) -> Vec<StateInShape>{
println!("Remaining pieces {0:?}, size of states_in_shape {1}", remaining_piece_ids, states_in_shape.len());
if remaining_piece_ids.len()==0 {
return states_in_shape;
}
let mut temp_states:Vec<StateInShape>=Vec::with_capacity(90000);
let piece_num=remaining_piece_ids.remove(0);
let t11=common::current_milliseconds();
for state in states_in_shape.iter_mut() {
self.place_a_piece(&mut temp_states, state, piece_num, ids, cells_to_occupy);
}
let t22=common::current_milliseconds();
println!("place_a_piece t22 - t11 = {}", t22 - t11);
return self.place_pieces_recursion(temp_states, ids, remaining_piece_ids, config, cells_to_occupy);
}
fn place_a_piece(&self, temp_states:&mut Vec<StateInShape>, state:&mut StateInShape, piece_id_to_place:u8, ids:&mut HashSet<&str>, cells_to_occupy:&mut Vec<usize>) {
let piece=*self.map_piece_id_to_piece.get(&piece_id_to_place).unwrap();
for offset in 0..state.cells.len() {
let t1=common::current_milliseconds();
// Check if it is a blank cell
let piece_id=state.cells[offset];
if piece_id != 33 {
continue;
}
// This piece cannot be placed at 'offset' due to crossing border
if !self.map_piece_id_and_offset_to_occupied.contains_key(&(piece_id_to_place, offset as u8)){
continue;
}
let t2=common::current_milliseconds();
println!("t2 - t1 = {}", t2 - t1);
// Check if the cells which will be occupied by this piece are all blank
let mut can_be_placed=true;
cells_to_occupy.clear();
for occupied_cell_num in self.map_piece_id_and_offset_to_occupied.get(&(piece_id_to_place, offset as u8)).unwrap() {
if state.cells[*occupied_cell_num as usize] !=33 {
can_be_placed=false;
break;
}
cells_to_occupy.push(*occupied_cell_num as usize);
}
if !can_be_placed {
continue;
}
let t3=common::current_milliseconds();
println!("t3 - t2 = {}", t3 - t2);
// Make a new ShapeInState.id prio to spawning a new ShapeInState to avoid duplicated ShapeInState.id
let mut cells=state.cells.clone();
for cell in cells_to_occupy.iter_mut() {
cells[*cell]=piece.id;
}
let new_id=state.id(self, Some(&cells));
if ids.contains(new_id) {
continue;
}
let t4=common::current_milliseconds();
println!("t4 - t3 = {}", t4 - t3);
// Everything is OK, now spwan a new StateInShape
let mut new_state_in_shape=state.clone();
new_state_in_shape.offsets[piece.id as usize]=offset as u8;
for cell in cells_to_occupy.iter_mut() {
new_state_in_shape.cells[*cell]=piece.id;
}
new_state_in_shape.id(self, None);
ids.insert(&new_state_in_shape.id);
// Put a new StateInShape into temp_states to be preared for recursion
temp_states.push(new_state_in_shape);
let t5=common::current_milliseconds();
println!("t5 - t4 = {}", t5 - t4);
}
}