1
xiaoming1992 2021-05-26 23:00:54 +08:00
我只能想到笨办法,两层 for 循环,逐个判断是不是空目录。。。
|
2
0ZXYDDu796nVCFxq 2021-05-26 23:15:40 +08:00
有序吗?
有序的话直接双指针,慢指针为目录,快指针为文件,判断文件是否 startswith(目录) 时间复杂度 O(n) |
3
renmu123 2021-05-26 23:19:39 +08:00 via Android 1
因为目录是树,如果某个节点不是文件且没有子节点,那么应该就能认定其为空目录
|
5
SingeeKing 2021-05-27 02:31:39 +08:00 via iPhone
对时间空间不是特别敏感的话,直接构建一个 trie 树然后输出叶子结点
|
6
xuanbg 2021-05-27 06:07:57 +08:00
遍历集合生成一个含文件的集合,然后取差集不就好了吗
|
8
no1xsyzy 2021-05-27 09:31:15 +08:00
因为「有序」,可知上层目录必定出现在下层目录之前
搞个 set,遍历列表,添加自己,删掉上层。 或者也不用搞 set,新建一个 list,反正能删的肯定是最后一个,检测一下最后一个是上层就 pop 掉就成。 |
9
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 ?) |
10
Rheinmetal 2021-05-27 10:03:57 +08:00
如果可以改进流程 学学 everything wiztree
|
11
aijam 2021-05-27 10:15:53 +08:00
搞个 trie,找出所有子节点
|
12
Vegetable 2021-05-27 10:19:20 +08:00
寻找所有叶子节点?
去 leetcode 搜了一下,这道题有点像。 https://leetcode-cn.com/problems/remove-sub-folders-from-the-filesystem/ |
13
mingl0280 2021-05-27 11:17:08 +08:00 via Android
……简单粗暴的办法,你自己建个树改下 dirent
|
14
imn1 OP @no1xsyzy #9
输入和你一样,输出 7 就可以了,5/6 都有空的子目录,只是我现在只能做到 5/6/7,单独 7 还没想到 主要想尝试优化一下时间,我原来用双循环+collentions.Counter 可以仅输出 7,但比 groupby 用时稍多一点 |
15
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) 的滑动窗口迭代器) |
16
no1xsyzy 2021-05-27 13:16:30 +08:00
@no1xsyzy 不好意思 s/latter\.split(os\.sep)/latter.rsplit(os.sep,1)/
|
17
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=='\\' 排序就更混乱了,它在大小写之间…… |
18
liprais 2021-05-27 13:30:09 +08:00
把你的路径做成接邻表,没有子节点然后是目录的就是你要的
|
19
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/? 如果是有序并且这个顺序是 目录->目录文件->子目录->子目录文件 这种 简单的滑动比较就可以了 无序可以考虑构建个多叉树,全部填充完再遍历 |
20
imn1 OP @gstqc #19
Y 排序是字符串排序,windows 路径符是\,所以有#17 所说的问题,前面的例子只是偷懒写成 unix 路径 / 补充一个: 输入 /dir1/dir5 /dir1/dir5/dir6 期望只输出 /dir1/dir5/dir6 目前做到是两个都输出了 |
21
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/,都可以找到匹配的文件 因为是有序的,所以不断滑动两个指针进行比较就行 |
22
3dwelcome 2021-05-27 15:17:27 +08:00
windows 上你用 dir /s 就可以了啊,这个命令会列出目录下所有<DIR>的路径。
然而,只有对于非空目录,才会有" D:\Users\Administrator 的目录"这种单行文本输出。 所以你找所有空目录,只要用全部<DIR>路径减去所有非空目录,剩下的就是空目录列表了。 |
23
3dwelcome 2021-05-27 15:19:50 +08:00
哦,dir /s 有点问题,就算空目录,还是会输出 0 File(s) 0 bytes,汗。
|
24
yazoox 2021-05-27 17:48:27 +08:00
|
25
yazoox 2021-05-27 17:50:17 +08:00
楼主,你代码已经写出来了?附言 4 就是 python 代码?我咋看不懂啊......
|
26
imn1 OP @yazoox #25
中间是个列表表达式,太长分了行而已,能用表达式我都不用 for 语句的,表达式也能执行函数,一样的 如果从上下行计算的话,需要一些移动函数(rolling),pandas 有,但暂时没见过单纯 python 实现的 |
27
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) ``` (如果需要优化可以修改为迭代器,需要简化可以手动复制函数填充进表达式) |
28
imn1 OP @O5oz6z3 #27
没有试,因为看到 pathlib 大目录树我个人不建议用 pathlib,至少目前是,我这个是个十万文件的大目录树,所以想寻求不使用 IO 的方法,如果只是小目录,我都懒得理,还不如省点时间做下一个事项 pathlib 逐个构建对象,即使是 purepath 也是消耗,已经有人在 python 提了 issue,等官方优化吧 pathlib 的优点是代码简单很多,递归树才一行,写 os.scandir 要好几行 如果要限定递归层级或者过滤,scandir 更加麻烦,pathlib 改改 glob 的字符参数就行了 PS: pathlib 递归树比 scandir 慢几倍 不过无序那部份我花时间研究一下 |
29
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) ``` 因为没法测试,所以不知道到底行不行得通。 |