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

  • ystael@beehaw.org
    link
    fedilink
    arrow-up
    1
    ·
    5 days ago

    J

    Mostly-imperative code in J never looks that nice, but at least the matrix management comes out fairly clean. Part 2 is slow because I didn’t cache the lengths of free intervals or the location of the leftmost free interval of a given length, instead just recalculating them every time. One new-ish construct today is dyadic ]\. The adverb \ applies its argument verb to sublists of its right argument list, the length of those sublists being specified by the absolute value of the left argument. If it’s positive, the sublists overlap; if negative, they tile. The wrinkle is that monadic ] is actually the identity function – we actually want the sublists, not to do anything with them, so we apply the adverb \ to ]. For example, _2 ]\ v reshapes v into a matrix of row length 2, without knowing the target length ahead of time like we would need to for $.

    data_file_name =: '9.data'
    input =: "."0 , > cutopen fread data_file_name
    compute_intervals =: monad define
       block_endpoints =. 0 , +/\ y
       block_intervals =. 2 ]\ block_endpoints
       result =. (<"2) 0 2 |: _2 ]\ block_intervals
       if. 2 | #y do. result =. result 1}~ (}: &.>) 1 { result end.
       result
    )
    'file_intervals free_intervals' =: compute_intervals input
    interval =: {. + (i. @: -~/)
    build_disk_map =: monad define
       disk_map =. (+/ input) $ 0
       for_file_int. y do.
          disk_map =. file_int_index (interval file_int)} disk_map
       end.
       disk_map
    )
    compact =: dyad define
       p =. <: # y  NB. pointer to block we're currently moving
       for_free_int. x do.
          for_q. interval free_int do.
             NB. If p has descended past all compacted space, done
             if. p <: q do. goto_done. end.
             NB. Move content of block p to block q; mark block p free
             y =. (0 , p { y) (p , q)} y
             NB. Decrement p until we reach another file block
             p =. <: p
             while. 0 = p { y do. p =. <: p end.
          end.
       end.
       label_done.
       y
    )
    disk_map =: build_disk_map file_intervals
    compacted_map =: free_intervals compact disk_map
    checksum =: +/ @: (* (i. @: #))
    result1 =: checksum compacted_map
    
    move_file =: dyad define
       'file_intervals free_intervals' =. x
       file_length =. -~/ y { file_intervals
       target_free_index =. 1 i.~ ((>: & file_length) @: -~/)"1 free_intervals
       if. (target_free_index < # free_intervals) do.
          'a b' =. target_free_index { free_intervals
          if. a < {. y { file_intervals do.
             c =. a + file_length
             file_intervals =. (a , c) y} file_intervals
             free_intervals =. (c , b) target_free_index} free_intervals
          end.
       end.
       file_intervals ; free_intervals
    )
    move_compact =: monad define
       for_i. |. i. # > 0 { y do. y =. y move_file i end.
       y
    )
    move_compacted_map =: build_disk_map > 0 { move_compact compute_intervals input
    result2 =: checksum move_compacted_map