python - 从路径列表中删除冗余条目

Question

我有一个文件和目录列表。我正在尝试编写一个函数来删除条目，其中也存在祖先目录的条目。到目前为止，我所拥有的似乎有效，但我认为它效率低下，因为它会测试每个文件的完整目录列表。

也许那里有一个图书馆可以做到这一点，但我找不到它。目的是让用户选择要上传的文件和目录列表。

从示例中可以看出，目录是条目的子集。我宁愿只提供条目。

import os

def remove_redundant_entries(entries, directories):
    result = []
    for entry in entries:
        # make a copy and successively get the dirname and test it
        partial_path = entry
        found = False
        while partial_path != os.sep:
            partial_path = os.path.dirname(partial_path)
            if partial_path in directories:
                found = True
                break
        if not found:
            result.append(entry)
    return result


entries = [
    "/home/fred/work/f1.txt",
    "/home/fred/work/f2.txt",
    "/home/fred/play/f3.txt",
    "/home/fred/play",
    "/home/jane/dev/f1.txt",
    "/home/jane"]

directories = [
    "/home/fred/play",
    "/home/jane"]

print remove_redundant_entries(entries, directories)

# result:
['/home/fred/work/f1.txt', '/home/fred/work/f2.txt', '/home/fred/play', '/home/jane']

如果您知道一个库或者可以提供更好算法的线索，我将不胜感激。同时，我将尝试基于对条目进行排序的方法，因为祖先在列表中应该始终排在他们的 child 之前。

编辑:- 结果

我使用测试集通过探查器运行所有解决方案 10,000 次 - 并添加一个文件 /home/fred/work/f2.txt.bak 以测试确保常规文件名确实导致另一个被丢弃。

我的原始代码:在 0.394 秒内调用 1060004 次函数

Stephen Rauch 的回答 - 第一次成功:3250004 次函数调用在 2.089 秒内

carrdelling 的回答 - 对于相似的文件名不起作用:480004 次函数调用在 0.146 秒内

carrdelling 的编辑答案 - 适用于所有情况:680004 次函数调用在 0.231 秒内

感谢所有做出贡献的人!

Answer 1

如果您对输入的条目列表进行排序，那么问题就更简单了:

def remove_redundant_entries(entries):

    split_entries = sorted(entries)

    valid_entries = []

    for entry in split_entries:

        if any(entry.startswith(p) for p in valid_entries):
            continue
        valid_entries.append(entry)

    return valid_entries

注意 any short-circuits一旦一个比较为真(除非绝对必要，否则您不会与整个列表进行比较)。此外，由于列表是经过排序的，因此可以保证输出将具有最少数量(和最高级别)的路径。

编辑:

如果您还需要能够在列表中保留同一文件夹中的多个文件(即使某些文件名是其他文件名的子集)，您只需修改排序标准:

split_entries = sorted(entries, key=lambda x: (x.count(os.sep), -len(x)))

这样，树中较高的文件夹会出现得更早(因此您最终会得到最少的路径数)，但在文件夹中，名称较长的文件会出现得更早 - 因此它们不会被丢弃因为文件名称较短(类似前缀)。