以最少的开销重命名目录的所有内容

Question

我目前处于需要重命名目录中的所有文件的位置。文件不更改名称的可能性很小，旧文件名与新文件名相同的可能性相当大，很可能导致重命名冲突。

因此，简单地遍历文件并重命名 old->new 不是一个选项。

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

此外，由于我正在处理喜欢放慢速度的慢速媒体和病毒扫描程序，因此我想尽量减少磁盘上的实际操作。除此之外，用户会不耐烦地等待做更多的事情。因此，如果可能的话，我想一次处理磁盘上的所有文件（通过巧妙地重新排序重命名操作）并避免指数时间恶作剧。

最后一点让我想到了一个 'good enough' 解决方案，我首先在我的目录中创建一个临时目录，然后将所有内容移动并重命名到该目录中，最后，我将所有内容移回旧文件夹中并删除临时目录。这给了我 O(2n) 的磁盘和操作复杂度。

如果可能的话，我希望将磁盘上的复杂度提高到 O(n)，即使它是以将内存中操作增加到 O(99999n) 为代价的。毕竟内存快了很多

我个人在图论方面不够熟悉，我怀疑整个 'rename conflict' 问题以前都已经解决了，所以我希望有人能给我指出一个满足我需要的算法。（是的，我可以尝试自己酿造，但我不够聪明，无法编写有效的算法，而且我可能会留下一个逻辑错误，该错误很少会出现在我的测试中。xD）

Answer 1

一种方法如下。

假设文件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

Answer 2

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

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

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

如果它的目标新名称没有冲突（新名称的文件不存在），那么只需重命名它
else（存在冲突）

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);
}

Answer 3

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

您可以在第一阶段构建旧文件名到新文件名的双向映射。

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

现在，为了构建该图，我们迭代 I 集。对于 I 的每个元素 e:

在图表中插入一个顶点表示文件 e 如果不存在则需要重命名
获取"old filename"o需要重命名为e
将表示 o 的顶点插入图中（如果它不存在的话）
在图中插入一条有向边 (e, o)。这条边表示"e must be renamed before o"。如果该边引入循环 (*)，请不要插入它并将 o 标记为需要 移动的文件-并重命名.

您现在必须遍历图形的根（没有内边的顶点）并使用它们作为起点执行 BFS 并执行每个重命名发现顶点的时间。重命名可以是普通重命名或移动重命名，具体取决于顶点是否已标记。

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

C++ Live Demo来说明图形处理。

以最少的开销重命名目录的所有内容

Rename all contents of directory with a minimum of overhead

algorithm

rename

graph-theory

batch-rename

示例代码