从路径列表中删除冗余项

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']

如果你知道一个库或能给一个更好的算法的线索，我会很感激。同时，我将尝试一些基于条目排序的方法，因为在列表中祖先应该总是在他们的孩子之前。你知道吗

编辑：-结果

我用测试集在profiler中运行了10000次所有的解决方案，并添加了一个文件/home/fred/work/f2.txt.bak以测试确保一个常规文件名确实会导致另一个文件名被丢弃。你知道吗

我的原始代码：1060004 function calls in 0.394 seconds

斯蒂芬·劳赫的答案——第一次成功：3250004 function calls in 2.089 seconds

carrdelling的答案-这对于类似的文件名不起作用：480004 function calls in 0.146 seconds

卡德林编辑的答案-适用于所有情况：680004 function calls in 0.231 seconds

感谢所有的贡献者！你知道吗

Answer 1

可以使用集合更有效地查找已存在的，如：

代码：

def remove_redundant_entries(entries):
    present = set()
    result = []
    for entry in sorted(entries):
        path = os.path.abspath(entry).split(os.sep)
        found = any(
            tuple(path[:i+1]) in present for i in range(len(path)))
        if not found:
            result.append(entry)
            present.add(tuple(path))
    return result

测试代码：

import os

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"]

result = remove_redundant_entries(entries)
expected = ['/home/fred/work/f1.txt', '/home/fred/work/f2.txt',
            '/home/fred/play', '/home/jane']
assert set(result) == set(expected)

Answer 2

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

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

注意anyshort-circuits一旦一个比较为真（除非严格必要，否则它不会再比较整个列表）。此外，由于列表是按顺序排列的，因此可以保证输出具有最少数量（和最高级别）的路径。你知道吗

编辑：

如果您还需要在列表中保留同一文件夹中的多个文件（即使某些文件名是其他文件名的子集），则只需修改排序条件：

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

这样，树中较高的文件夹会出现得更早（因此路径数最少），但在文件夹中，名称较长的文件会出现得更早，因此不会因为名称较短（类似前缀）的文件而被丢弃。你知道吗