Day 9: Disk Fragmenter

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • @[email protected]OPM
    link
    fedilink
    2
    edit-2
    3 days ago

    Found a cheaty way to get sub 1s:

        fn defrag2(p0: &mut [i64]) {
            let mut i = *p0.last().unwrap();
            while i > 3000 {  // Stop defragging here, probably cant find free spots after this point
                let (old_pos, size) = find_file(p0, i);
                if let Some(new_pos) = find_slot(p0, size, old_pos) {
                    move_file(p0, i, size, old_pos, new_pos);
                }
                i -= 1;
            }
        }
    

    Might be possible to correctly do this in the find_slot code, so that if it fails to find a slot, it never searches for that size again.

    edit:

    fn defrag2(p0: &mut [i64]) {
            let mut i = *p0.last().unwrap();
            let mut max_size = 10;
            while i > 0 {
                let (old_pos, size) = find_file(p0, i);
                if size <= max_size {
                    if let Some(new_pos) = find_slot(p0, size, old_pos) {
                        move_file(p0, i, size, old_pos, new_pos);
                    } else {
                        max_size = size - 1;
                    }
                }
                if max_size == 0 {
                    return;
                }
                i -= 1;
            }
        }
    

    500ms, I can go to sleep now.

    • @[email protected]OPM
      link
      fedilink
      23 days ago

      haha, kept going at it, got it down to 4ms, by tracking where the searches ended, and starting from there next time.

      Definitely done now :D