已知目录树全文件、目录路径列表，不使用 IO 求空目录

暂时只想到这个
{k for k,v in itertools.groupby(paths, lambda x: x.rpartition(os.sep)[0]) if len(tuple(v))<2}

但这个会把 /abc/empty1/empty2/empty3，整个 empty1 及子目录不含文件，输出为
{
"/abc/empty1/empty2/empty3",
"/abc/empty1/empty2",
"/abc/empty1",
"/abc"
}

有待优化

第 3 条附言 · 2021-05-27 14:07:30 +08:00

前一个附言的写法有 bug，漏掉最内层的空目录，实际上 empty3 下面还有 empty4，漏掉了
如果目录都以 os.sep 结尾，这个能找出来

因为是字符串列表，排序也是按字符排序

这题有点钻牛角尖了，权当刷题玩吧

第 4 条附言 · 2021-05-27 17:21:19 +08:00

parent = os.path.basename
res = set()
[
res.symmetric_difference_update({k, parent(k)}) # 去掉 res 中已存在的父级目录
for k,v in itertools.groupby(paths,
lambda x: parent(x+os.sep if '.' in os.path.basename(x) else x))
if len(tuple(v))==1
]

return sorted(res-{root, parent(root)}) # 去除树的入口根路径及其父路径

paths 为全文件目录列表，需要排正序
如果列表已经能区分出目录（结尾为 os.sep ），lambda 可以简单些

暂时这样吧，有 bug 再写过

路径

文件

列表

29 条回复 • 2021-05-27 19:00:17 +08:00

xiaoming1992

2021-05-26 23:00:54 +08:00

我只能想到笨办法，两层 for 循环，逐个判断是不是空目录。。。

0ZXYDDu796nVCFxq

2021-05-26 23:15:40 +08:00

有序吗？
有序的话直接双指针，慢指针为目录，快指针为文件，判断文件是否 startswith(目录)
时间复杂度 O(n)

renmu123

2021-05-26 23:19:39 +08:00 via Android

因为目录是树，如果某个节点不是文件且没有子节点，那么应该就能认定其为空目录

imn1

2021-05-27 00:37:10 +08:00

@gstqc #2
有序

@renmu123 #3
这个需要 IO，现在假设就是硬盘离线，只有文件列表，无法检测是否存在文件

SingeeKing

2021-05-27 02:31:39 +08:00 via iPhone

对时间空间不是特别敏感的话，直接构建一个 trie 树然后输出叶子结点

xuanbg

2021-05-27 06:07:57 +08:00

遍历集合生成一个含文件的集合，然后取差集不就好了吗

shyrock

2021-05-27 09:21:50 +08:00

@xuanbg #6 我觉得这个是正解。

no1xsyzy

2021-05-27 09:31:15 +08:00

因为「有序」，可知上层目录必定出现在下层目录之前
搞个 set，遍历列表，添加自己，删掉上层。
或者也不用搞 set，新建一个 list，反正能删的肯定是最后一个，检测一下最后一个是上层就 pop 掉就成。

no1xsyzy

2021-05-27 09:45:53 +08:00

发现其实没理解问题，现明晰一下：

输入样例：
```
1 /abc/empty1
2 /abc/empty1/empty2
3 /abc/empty1/empty2/empty3
4 /abc/file.ext
```
输出样例：
```
5 /abc/empty1
6 /abc/empty1/empty2
7 /abc/empty1/empty2/empty3
```

输入是否是整个层级？还是末端层级？（即，输入是否包含 L1-2 ？）
输出是否要包含子目录？（即，输出是否包含 L6-7 ？）

Rheinmetal

2021-05-27 10:03:57 +08:00

如果可以改进流程学学 everything wiztree

aijam

2021-05-27 10:15:53 +08:00

搞个 trie，找出所有子节点

Vegetable

2021-05-27 10:19:20 +08:00

寻找所有叶子节点？
去 leetcode 搜了一下，这道题有点像。
https://leetcode-cn.com/problems/remove-sub-folders-from-the-filesystem/

mingl0280

2021-05-27 11:17:08 +08:00 via Android

……简单粗暴的办法，你自己建个树改下 dirent

imn1

2021-05-27 12:27:32 +08:00

@no1xsyzy #9
输入和你一样，输出 7 就可以了，5/6 都有空的子目录，只是我现在只能做到 5/6/7，单独 7 还没想到

主要想尝试优化一下时间，我原来用双循环+collentions.Counter 可以仅输出 7，但比 groupby 用时稍多一点

no1xsyzy

2021-05-27 13:15:05 +08:00

你可以
[former
for former, latter in itertools.zip_longest(paths, paths[1:])
if like_dirname(former) and (latter is None or latter.split(os.sep)[0] != former)]

理论上来说，比较相邻两个，如果前一个不是后一个的父级，则包含前一个，再带上最后一个。
再筛选一下名字像是目录名的。
paths 列表比较长的话可能涉及拷贝有效率问题，可以把 paths[1:] 改成 ipaths 并且在前面加上这两行（也就是造两个同一个列表的正好差一位的迭代器）
ipaths = iter(paths)
next(ipaths)
（或者随手写一个 window(iterable, n=2) 的滑动窗口迭代器）

no1xsyzy

2021-05-27 13:16:30 +08:00

@no1xsyzy 不好意思 s/latter\.split(os\.sep)/latter.rsplit(os.sep,1)/

no1xsyzy

2021-05-27 13:25:41 +08:00

想到可能有个问题，如果排序是按照字符串而不是目录的话，ASCII 排序有 14 个符号处于 '/' 之前。
/abc/not_empty
/abc/not_empty(but_jump_in)
/abc/not_empty(but_jump_in)/anything
/abc/not_empty/anything
这样的话就会有问题。发现不太确定你的有序是什么意思。
如果是 windows 下，os.sep=='\\' 排序就更混乱了，它在大小写之间……

liprais

2021-05-27 13:30:09 +08:00

把你的路径做成接邻表，没有子节点然后是目录的就是你要的

0ZXYDDu796nVCFxq

2021-05-27 14:19:38 +08:00

还是上个样例数据吧
假如

/dir1/
/dir1/file1
/dir1/file2
/dir1/dir2/
/dir1/dir3/
/dir1/dir3/file3
/dir1/dir4/

输出结果是 /dir1/dir2/, /dir1/dir4/？

如果是有序并且这个顺序是目录->目录文件->子目录->子目录文件这种
简单的滑动比较就可以了

无序可以考虑构建个多叉树，全部填充完再遍历

imn1

2021-05-27 14:36:33 +08:00

@gstqc #19
Y
排序是字符串排序，windows 路径符是\，所以有#17 所说的问题，前面的例子只是偷懒写成 unix 路径 /

补充一个：
输入
/dir1/dir5
/dir1/dir5/dir6
期望只输出
/dir1/dir5/dir6

目前做到是两个都输出了

0ZXYDDu796nVCFxq

2021-05-27 15:01:26 +08:00

@imn1 双指针就可以了
假如输入数据是
/dir1/
/dir1/file1
/dir1/file2
/dir1/dir2/
/dir1/dir3/
/dir1/dir3/file3
/dir1/dir4/

规律就是 /dir1/dir2/, /dir1/dir4/ 都没有以这两个目录开头的文件
而 /dir1/, /dir1/dir3/，都可以找到匹配的文件

因为是有序的，所以不断滑动两个指针进行比较就行

3dwelcome

2021-05-27 15:17:27 +08:00

windows 上你用 dir /s 就可以了啊，这个命令会列出目录下所有<DIR>的路径。

然而，只有对于非空目录，才会有" D:\Users\Administrator 的目录"这种单行文本输出。

所以你找所有空目录，只要用全部<DIR>路径减去所有非空目录，剩下的就是空目录列表了。

3dwelcome

2021-05-27 15:19:50 +08:00

哦，dir /s 有点问题，就算空目录，还是会输出 0 File(s) 0 bytes，汗。

yazoox

2021-05-27 17:48:27 +08:00

@gstqc 双指针一般情况可以。但楼主如果是实际生产中的需求，可能不行。见#17 楼 @no1xsyzy 的情况，又指针就处理不了了。

yazoox

2021-05-27 17:50:17 +08:00

楼主，你代码已经写出来了？附言 4 就是 python 代码？我咋看不懂啊......

imn1

2021-05-27 18:00:38 +08:00

@yazoox #25
中间是个列表表达式，太长分了行而已，能用表达式我都不用 for 语句的，表达式也能执行函数，一样的

如果从上下行计算的话，需要一些移动函数(rolling)，pandas 有，但暂时没见过单纯 python 实现的

O5oz6z3

2021-05-27 18:20:41 +08:00

没给出样例，问题描述也很含糊，目录树是按字符顺序还是路径关系排序、子目录是否以分隔符结尾、目录中只含有空目录是否也算作空目录……
但还是试着写了写，不知道行不行：
```python
from pathlib import Path
from itertools import zip_longest
# from pprint import pprint as pp

is_dir = lambda n: not Path(n).suffix
get_parent = lambda n: str(Path(n).parent)

# paths = ?
print('如果按路径关系排序')
result = [ k for k, v in zip_longest(paths, paths[1:], fillvalue='')
if is_dir(k) and not v.startswith(k) ]
# pp(result)

print('如果无序')
result = { k for k in paths if is_dir(k) }
for v in paths:
k = get_parent(v)
result.discard(k)
# pp(result)
```
（如果需要优化可以修改为迭代器，需要简化可以手动复制函数填充进表达式）

imn1

2021-05-27 18:53:49 +08:00

@O5oz6z3 #27
没有试，因为看到 pathlib
大目录树我个人不建议用 pathlib，至少目前是，我这个是个十万文件的大目录树，所以想寻求不使用 IO 的方法，如果只是小目录，我都懒得理，还不如省点时间做下一个事项

pathlib 逐个构建对象，即使是 purepath 也是消耗，已经有人在 python 提了 issue，等官方优化吧
pathlib 的优点是代码简单很多，递归树才一行，写 os.scandir 要好几行
如果要限定递归层级或者过滤，scandir 更加麻烦，pathlib 改改 glob 的字符参数就行了

PS: pathlib 递归树比 scandir 慢几倍

不过无序那部份我花时间研究一下

O5oz6z3

2021-05-27 19:00:17 +08:00

@imn1
1. 这份代码里面没有 IO 操作，使用 pathlib 只是为了方便字符串层面的路径操作。
2. pathlib 构建对象确实有性能问题，但这只是其中一种实现，lambda 代码可以用你写的 os...来代替。

顺便因为缩进问题，修改一下无序部分的代码：
```python
print('如果无序')
result = { k for k in paths if is_dir(k) }
temp = [ result.discard(get_parent(v)) for v in paths ]
# pp(result)
```
因为没法测试，所以不知道到底行不行得通。