磁盘碎片

代码来临 2024 年第 9 天

第 1 部分

三相拳套。令人兴奋！？

我所看到的各个阶段的详细说明：

1. 将内存表示为列表
2. 将值从末尾移动到开头
3. 走线计算校验和

没有一个感觉特别困难。

其中一些实际上看起来像是另一个有趣的算法挑战！

列清单

我想把这个：

12345

进入此：

0..111....22222

我需要考虑：

• 使用循环
• 检查偶数和奇数索引
• 从 0 开始将值加 1

这是我的磁盘生成算法：

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

就像魅力一样！

将值从结束移动到开始

让这一切变得更容易的是拥有磁盘上所有空位置的列表。

我需要在两个地方更新我的算法：

1. 一个新变量：let empty = []
2. 插入 . 后的新操作：empty.push(disk.length - 1)

在示例中测试它会显示每个 .!

的预期索引号

这是当我将值从列表末尾移动到开头并向前移动时将迭代的列表。

但是等等。

这可能比我想象的更困难。

我如何知道何时停止尝试移动值？

• 我是否迭代空索引列表？我什么时候应该停止？
• 我是否向后迭代磁盘？我什么时候应该停止？

顿悟：神奇的数字 10

这是简短示例的最后状态：

022111222......

第一个例子：

0099811188827773336446555566..............

这意味着有一个点，所有 id 都在左边，所有空白都在右边。

我如何检查该状态？

输入：数字 10。

连续空白空间的数量永远不会高于 9。

所以，如果我遇到一个空白空间，向前查找 9 个空格（或到磁盘列表的末尾），并看到所有空白空间，我就知道我已经完成了碎片化。

我想我知道如何编写这个算法的其余部分！

编写我的碎片算法

这是工作算法：

let diskI = disk.length - 1
let emptyI = 0
while (true) {
    while (disk[diskI] == '.') {
        diskI--
    }
    disk[empty[emptyI]] = disk[diskI]
    disk[diskI] = '.'
    emptyI++
    diskI--
    if (disk.slice(empty[emptyI],empty[emptyI] + 10).every(el => el == '.')) {
        break;
    }
}

工作原理：

Two trackers: 
- one for my place in the disk
- one for my place in the list of empty slots
Do until manually escaped
  Do as long as the current place in the disk is an empty slot
    Adjust the tracker one to the left
  Swap the values at each tracker
  Decrement the disk tracker
  Increment the empty tracker
  If there are 9 empty slots contiguous with the current empty slot
    Escape the loop

幸运的是，我看到了与两个示例相同的输出！

计算校验和

这看起来相当简单明了：

let part1 = disk.slice(0, disk.indexOf('.')).reduce((checksum, id, position) => {
    checksum += (+id * position)
    return checksum
}, 0)

伪代码：

Extract all values up to the first empty cell
Iterate through each value, amassing a total
Increment the accumulator by the product of the value and its index

成功！它为示例输入生成正确的答案！

它对我的拼图输入也会有同样的作用吗？

...

是的！！！

呜呼！！！

第二部分会有什么转折？轻微的规则调整还是规模上的挑战？

第2部分

一个有趣的转折

是零件。现在完整了。

这肯定需要对我的算法进行一些调整。

可能更强大地跟踪间隙和块的大小。

实施我的第一个策略

我正在跟踪每个空的位置。

我想我需要跟踪每个空的位置以及大小。

那会是什么样子？

刮掉那个。也许是新策略。

使用第一个示例：

12345

文件块大小为奇数：

0..111....22222

空单元格大小是偶数：

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

从奇数末尾和偶数开头开始，寻找大于等于奇数的偶数：

022111222......

我立即找到匹配的。

结果：

• 奇数移动
• 偶数减少
• 但是现在两个奇数没有间隙了
• 并且我丢失了第二个2s ID

0099811188827773336446555566..............

这个策略肯定行不通。

实施我的第二个策略

我不喜欢这个对性能的影响。

但我相信它会起作用......只要它完成运行。

对于磁盘输入中的每个数字，我将记录为列表项：

1. 文件块或空单元格
2. 长度
3. ID

举个例子：

let diskI = disk.length - 1
let emptyI = 0
while (true) {
    while (disk[diskI] == '.') {
        diskI--
    }
    disk[empty[emptyI]] = disk[diskI]
    disk[diskI] = '.'
    emptyI++
    diskI--
    if (disk.slice(empty[emptyI],empty[emptyI] + 10).every(el => el == '.')) {
        break;
    }
}

将成为：

Two trackers: 
- one for my place in the disk
- one for my place in the list of empty slots
Do until manually escaped
  Do as long as the current place in the disk is an empty slot
    Adjust the tracker one to the left
  Swap the values at each tracker
  Decrement the disk tracker
  Increment the empty tracker
  If there are 9 empty slots contiguous with the current empty slot
    Escape the loop

呃，让我们清理一下：

let part1 = disk.slice(0, disk.indexOf('.')).reduce((checksum, id, position) => {
    checksum += (+id * position)
    return checksum
}, 0)

我将通过数据类型区分间隙和文件块。

移动文件块在更改后的示例输入中将如下所示：

Extract all values up to the first empty cell
Iterate through each value, amassing a total
Increment the accumulator by the product of the value and its index

每 10 万次迭代都会涉及到：

• 在大数组中搜索项目
• 就地改变数组

两者都是非常昂贵的任务。

但这是我能想到解决这个难题的唯一方法。

所以，这就是我的方法。

编写我的策略

这是获取上述数据架构的 JavaScript：

2333133121414131402

我将如何开始和结束我的主循环？

从文件 ID 号最高的文件开始，按照文件 ID 号递减的顺序尝试将每个文件移动一次

似乎从后到前移动就可以满足我的需要。

这个 for 循环骨架应该可以工作：

[2,4,1,4,2,5,5,3,5,2]

查找、移动和替换

[3,3,3,1,1,1,1,1,0]

if 中的第二个子句是我最后一次调试。太早设置最低 ID 了。

编码磁盘打印机

我意识到我必须近乎实时地看到我的磁盘碎片。至少有一个日志，就像示例演练中一样。

值得庆幸的是，编码并不困难。只是我混合了两个索引并看到一些真正奇怪的输出的部分：

12345

• 我建立了一个字符串
• 基于磁盘中项目的类型
• 无论哪种方式，我都会创建一个数组并用 .s 或块的 ID 填充它

效果很好！我可以看到文件被移动到的位置，并更轻松地排除代码故障！

喜欢我所看到的

0..111....22222

看起来我的文件移动算法有效！

最后一步是计算新的校验和。

最后，更多数学

通过双重归约：

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

• 第一个reduce为我提供了一个由ids和.s组成的分散数组
• 当项目是 id 时，第二个reduce 执行适当的数学计算，而当项目是 .

有效吗？

关于示例拼图输入？是的！

关于我的拼图输入？

...

是啊SSSS！

哇。我很惊讶。我为第 2 部分提交的数字几乎与第 1 部分相同。我认为会更高。

我没有兴趣进一步调查。

我宁愿带着我的两颗来之不易的金星一起走到第十天。

再见第九天！

以上是磁盘碎片的详细内容。更多信息请关注PHP中文网其他相关文章！