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

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

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

编辑： - 结果

我使用测试集通过探查器运行了 10,000 次所有解决方案 - 并且添加一个文件/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

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

感谢所有做出贡献的人！

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短路(除非绝对必要，否则您不会再次比较整个列表)。此外，由于列表已排序，因此可以保证输出将具有最小数量(和最高级别)的路径。

编辑：

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

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

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

Answer 2

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

法典：

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)