重命名目录下所有内容，最小化开销。

Question

我目前需要重命名一个文件夹中的所有文件。文件不改变名称的可能性很小，旧文件名与新文件名相同的可能性相当大，这使得重命名冲突很可能发生。

因此，简单地循环文件并将旧名称重命名为新名称不是一个选项。

简单/明显的解决方案是将所有内容重命名为临时文件名：旧名称->tempX->新名称。当然，这在某种程度上转移了问题，因为现在有责任检查旧名称列表中的任何内容是否与临时名称列表重叠，并且临时名称列表中的任何内容是否与新列表重叠。

此外，由于我正在处理缓慢的媒体和喜欢减慢事情速度的病毒扫描器，我希望最小化磁盘上的实际操作。除此之外，用户会不耐烦地等待做更多的事情。因此，如果可能的话，我想一次性处理磁盘上的所有文件（通过智能地重新排序重命名操作），并避免指数时间花费。

这最后一点让我想到了一个“足够好”的解决方案，即首先在我的目录中创建一个临时目录，将所有内容移动-重命名到该目录中，最后将所有内容移动回旧文件夹并删除临时目录。这给我带来了O（2n）的磁盘和操作复杂度。

如果可能的话，即使以增加内存操作的O（99999n）为代价，我也希望将磁盘上的复杂性提高到O（n）。毕竟，内存速度更快。

我个人在图论方面不是很精通，并且我怀疑整个“重命名冲突”问题以前已经得到解决，因此我希望有人可以指向一个满足我的需求的算法。（是的，我可以尝试自己编写，但我不够聪明，可能会留下逻辑错误，这些错误很少发生，以至于它们可以通过我的测试。xD）

- Stigma

---

将整个文件结构读入内存，决定在内存中使用新名称，然后一次性写入所有更改是否可行？ - Yossi Vainshtein

我已经在内存中有一个旧名称和新名称的列表，所以这不是问题。内存并不是我关心的限制...至少在合理范围内。 - Stigma

Answer 1

我相信您对问题的图论建模感兴趣，以下是我的看法：

首先，您可以构建旧文件名到新文件名的双向映射作为第一阶段。

现在，您计算旧文件名和新文件名的交集集合I。出现在此集合中的每个目标“新文件名”都需要先重命名“旧文件名”。这是一个依赖关系，您可以在图中进行建模。

现在，要构建该图，我们遍历该I集合。对于I的每个元素e：

• 如果图中尚不存在代表需要重命名的文件e的顶点，则插入一个顶点
• 获取需要重命名为e的"旧文件名"o
• 如果尚不存在代表o的顶点，则插入一个顶点
• 在图中插入一个有向边(e, o)，表示"必须先重命名e再重命名o"。如果该边产生了循环(*)，则不要插入它，并将o标记为需要移动和重命名的文件。

现在您需要迭代图的根（没有入边的顶点）并使用它们作为起点执行BFS，每次发现一个顶点时执行重命名操作。重命名可以是普通的重命名或移动和重命名，具体取决于该顶点是否被标记。

最后一步是将移动和重命名的文件从其沙盒目录移回到目标目录。

C++ 实时演示 用于说明图形处理。

- Rerito

---

这是一个非常好的解释。由于我更专注于实现一个有效的解决方案，而另一个答案帮助得更多，所以我不能选择您作为“答案”。但无论如何，我想赞美您的出色帖子。谢谢。 - Stigma

Answer 2

一种方法如下。

假设文件A重命名为B且B是一个新名称，我们可以简单地重命名A。

假设文件A重命名为B，B重命名为C且C是一个新名称，我们可以按照相反的顺序遵循列表，将B重命名为C，然后将A重命名为B。

通常情况下，只要没有循环，这种方法就可以奏效。只需列出所有依赖项的列表，然后按相反的顺序进行重命名即可。

如果存在循环，则会出现以下情况：

A renames to B
B renames to C
C renames to D
D renames to A

在这种情况下，我们需要每个循环一个单独的临时文件。 将循环中的第一个文件A重命名为ATMP。 然后我们的修改列表变为：

ATMP renames to B
B renames to C
C renames to D
D renames to A

这个列表不再有循环，因此我们可以像以前一样按相反的顺序处理文件。

使用这种方法移动文件的总次数将是 n + 重新排列中的循环数。

示例代码

在Python中，可能会像这样：

D={1:2,2:3,3:4,4:1,5:6,6:7,10:11}  # Map from start name to final name

def rename(start,dest):
    moved.add(start)
    print 'Rename {} to {}'.format(start,dest)

moved = set()
filenames = set(D.keys())
tmp = 'tmp file'
for start in D.keys():
    if start in moved:
        continue
    A = [] # List of files to rename
    p = start
    while True:
        A.append(p)
        dest = D[p]
        if dest not in filenames:
            break
        if dest==start:
            # Found a loop
            D[tmp] = D[start]
            rename(start,tmp)
            A[0] = tmp
            break
        p = dest
    for f in A[::-1]:
        rename(f,D[f])

这段代码会打印出：

Rename 1 to tmp file
Rename 4 to 1
Rename 3 to 4
Rename 2 to 3
Rename tmp file to 2
Rename 6 to 7
Rename 5 to 6
Rename 10 to 11

- Peter de Rivaz

---

我选择了你的答案，因为你深入地涵盖了问题的各个方面：展示了链和循环的可能性。这使我能够最清晰地理解问题，同时在我的项目中实现适合我的需求的解决方案，并添加了一个简单的事务日志，以防出现错误时回滚。感谢你抽出时间写出如此深入的带有示例代码的答案。 :-) - Stigma

Answer 3

看起来你正在查看拓扑排序的子问题。然而，它更简单，因为每个文件只能依赖于另一个文件。假设没有循环：

假设map是从旧名称到新名称的映射：

在循环中，只需选择任何要重命名的文件，并将其发送到一个函数中：

1. 如果它的目标新名称不冲突（不存在具有新名称的文件），则只需重命名它

2. 否则（存在冲突）

   2.1 首先重命名冲突文件，通过递归将其发送到相同的函数中

   2.2 重命名此文件

一种类似Java伪代码的写法如下：

// map is the map, map[oldName] = newName;
HashSet<String> oldNames = new HashSet<String>(map.keys());    
while (oldNames.size() > 0)
{
   String file = oldNames.first(); // Just selects any filename from the set;
   renameFile(map, oldNames, file);
}
...
void renameFile (map, oldNames, file)
{
    if (oldNames.contains(map[file])
    {
       (map, oldNames, map[file]);
    }
    OS.rename(file, map[file]); //actual renaming of file on disk
    map.remove(file);
    oldNames.remove(file);
}

- Yossi Vainshtein

---

我认为你是对的，但需要进行小改进以检测循环。当尝试将1.txt重命名为2.txt并将2.txt重命名为1.txt时，你的代码会导致堆栈溢出（这不是一个双关语，真的）。 - Byzod