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

Question

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

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

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

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

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

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

我个人在图论方面还不够熟练，我怀疑之前已经解决了整个“重命名冲突”问题，所以我希望有人能给我指出一个满足我需要的算法。 (是的，我可以尝试自己酿造，但我不够聪明，无法编写有效的算法，而且我可能会留下一个逻辑错误，该错误很少会出现在我的测试中。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