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

  • CameronDev@programming.devOPM
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    19 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.

    • CameronDev@programming.devOPM
      link
      fedilink
      arrow-up
      2
      ·
      19 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