V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
imn1
V2EX  ›  Python

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

  •  
  •   imn1 · 2021-05-26 22:34:20 +08:00 · 2709 次点击
    这是一个创建于 1277 天前的主题,其中的信息可能已经有所发展或是发生改变。
    windows 路径
    已知整个目录树所有子目录、文件的路径,str 列表
    不考虑虚拟路径(软链硬链 mount/lnk 等)

    不实际检查文件 IO,就是 is_dir()这些,单纯通过字符串之间关系,求出没有文件的空目录
    有没有较快的方案?
    第 1 条附言  ·  2021-05-27 00:36:09 +08:00
    补充几个条件:
    1. 硬盘离线,不能检测文件,这个需求就是应对这个情况
    2. 列表有序
    3. 文件还是目录以是否有扩展名假定,忽略真实的情况,就是无扩展名的文件也视为目录,有扩展名的目录视为文件,其实在其他模块已经限定了文件和目录存入时满足这个条件,所以不需纠结这点
    第 2 条附言  ·  2021-05-27 02:20:47 +08:00
    暂时只想到这个
    {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
        1
    xiaoming1992  
       2021-05-26 23:00:54 +08:00
    我只能想到笨办法,两层 for 循环,逐个判断是不是空目录。。。
    0ZXYDDu796nVCFxq
        2
    0ZXYDDu796nVCFxq  
       2021-05-26 23:15:40 +08:00
    有序吗?
    有序的话直接双指针,慢指针为目录,快指针为文件,判断文件是否 startswith(目录)
    时间复杂度 O(n)
    renmu123
        3
    renmu123  
       2021-05-26 23:19:39 +08:00 via Android   ❤️ 1
    因为目录是树,如果某个节点不是文件且没有子节点,那么应该就能认定其为空目录
    imn1
        4
    imn1  
    OP
       2021-05-27 00:37:10 +08:00
    @gstqc #2
    有序

    @renmu123 #3
    这个需要 IO,现在假设就是硬盘离线,只有文件列表,无法检测是否存在文件
    SingeeKing
        5
    SingeeKing  
       2021-05-27 02:31:39 +08:00 via iPhone
    对时间空间不是特别敏感的话,直接构建一个 trie 树然后输出叶子结点
    xuanbg
        6
    xuanbg  
       2021-05-27 06:07:57 +08:00
    遍历集合生成一个含文件的集合,然后取差集不就好了吗
    shyrock
        7
    shyrock  
       2021-05-27 09:21:50 +08:00
    @xuanbg #6 我觉得这个是正解。
    no1xsyzy
        8
    no1xsyzy  
       2021-05-27 09:31:15 +08:00
    因为「有序」,可知上层目录必定出现在下层目录之前
    搞个 set,遍历列表,添加自己,删掉上层。
    或者也不用搞 set,新建一个 list,反正能删的肯定是最后一个,检测一下最后一个是上层就 pop 掉就成。
    no1xsyzy
        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 ?)
    Rheinmetal
        10
    Rheinmetal  
       2021-05-27 10:03:57 +08:00
    如果可以改进流程 学学 everything wiztree
    aijam
        11
    aijam  
       2021-05-27 10:15:53 +08:00
    搞个 trie,找出所有子节点
    Vegetable
        12
    Vegetable  
       2021-05-27 10:19:20 +08:00
    寻找所有叶子节点?
    去 leetcode 搜了一下,这道题有点像。
    https://leetcode-cn.com/problems/remove-sub-folders-from-the-filesystem/
    mingl0280
        13
    mingl0280  
       2021-05-27 11:17:08 +08:00 via Android
    ……简单粗暴的办法,你自己建个树改下 dirent
    imn1
        14
    imn1  
    OP
       2021-05-27 12:27:32 +08:00
    @no1xsyzy #9
    输入和你一样,输出 7 就可以了,5/6 都有空的子目录,只是我现在只能做到 5/6/7,单独 7 还没想到

    主要想尝试优化一下时间,我原来用双循环+collentions.Counter 可以仅输出 7,但比 groupby 用时稍多一点
    no1xsyzy
        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) 的滑动窗口迭代器)
    no1xsyzy
        16
    no1xsyzy  
       2021-05-27 13:16:30 +08:00
    @no1xsyzy 不好意思 s/latter\.split(os\.sep)/latter.rsplit(os.sep,1)/
    no1xsyzy
        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=='\\' 排序就更混乱了,它在大小写之间……
    liprais
        18
    liprais  
       2021-05-27 13:30:09 +08:00
    把你的路径做成接邻表,没有子节点然后是目录的就是你要的
    0ZXYDDu796nVCFxq
        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/?

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

    无序可以考虑构建个多叉树,全部填充完再遍历
    imn1
        20
    imn1  
    OP
       2021-05-27 14:36:33 +08:00
    @gstqc #19
    Y
    排序是字符串排序,windows 路径符是\,所以有#17 所说的问题,前面的例子只是偷懒写成 unix 路径 /

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

    目前做到是两个都输出了
    0ZXYDDu796nVCFxq
        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/,都可以找到匹配的文件

    因为是有序的,所以不断滑动两个指针进行比较就行
    3dwelcome
        22
    3dwelcome  
       2021-05-27 15:17:27 +08:00
    windows 上你用 dir /s 就可以了啊,这个命令会列出目录下所有<DIR>的路径。

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

    所以你找所有空目录,只要用全部<DIR>路径减去所有非空目录,剩下的就是空目录列表了。
    3dwelcome
        23
    3dwelcome  
       2021-05-27 15:19:50 +08:00
    哦,dir /s 有点问题,就算空目录,还是会输出 0 File(s) 0 bytes,汗。
    yazoox
        24
    yazoox  
       2021-05-27 17:48:27 +08:00
    @gstqc 双指针一般情况可以。但楼主如果是实际生产中的需求,可能不行。见#17 楼 @no1xsyzy 的情况,又指针就处理不了了。
    yazoox
        25
    yazoox  
       2021-05-27 17:50:17 +08:00
    楼主,你代码已经写出来了?附言 4 就是 python 代码?我咋看不懂啊......
    imn1
        26
    imn1  
    OP
       2021-05-27 18:00:38 +08:00
    @yazoox #25
    中间是个列表表达式,太长分了行而已,能用表达式我都不用 for 语句的,表达式也能执行函数,一样的

    如果从上下行计算的话,需要一些移动函数(rolling),pandas 有,但暂时没见过单纯 python 实现的
    O5oz6z3
        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)
    ```
    (如果需要优化可以修改为迭代器,需要简化可以手动复制函数填充进表达式)
    imn1
        28
    imn1  
    OP
       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
        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)
    ```
    因为没法测试,所以不知道到底行不行得通。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2728 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 86ms · UTC 06:53 · PVG 14:53 · LAX 22:53 · JFK 01:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.