[CLI/Python] find prune path - cắt giảm bài toán tìm kiếm 10 lần

`find` là câu lệnh dùng để tìm file dựa theo tên, vốn không kém tiếng "khó dùng", nhưng vẫn được dùng, do nó được cài sẵn ở mọi hệ điều hành Unixoid (Unix/Linux).

find - huyền thoại

Một lệnh find đơn giản để tìm các file .py trong thư mục /usr

$ time -p find /usr/ -name '*.py' | wc -l
11013
real 0,39
user 0,15
sys 0,24

11013 file này gồm file từ nhiều thư mục khác nhau.

$ time -p find /usr/ -name '*.py' | cut -f-3 -d '/' | sort | uniq -c | sort -nr | head
   9286 /usr/lib
   1644 /usr/share
     78 /usr/src
      5 /usr/local
real 0,39
user 0,17
sys 0,24

Cấu trúc thư mục:

 $ time -p find /usr/ | cut -f-3 -d '/' | sort | uniq -c | sort -nr | head
 150407 /usr/share
  59798 /usr/src
  44392 /usr/lib
  29949 /usr/local
   4168 /usr/include
   2355 /usr/bin
    260 /usr/sbin
    260 /usr/lib32
      9 /usr/libexec
      7 /usr/games
real 0,42
user 0,29
sys 0,26

Giả sử không muốn kết quả chứa các file trong /usr/lib, cách đơn giản nhất là thêm điều kiện lọc:

$ time -p find /usr/ -name '*.py' -not -path '/usr/lib/*' | wc -l
1727
real 0,41
user 0,19
sys 0,21

Cách làm này đơn giản, hiển nhiên, nhưng có 1 vấn đề: chậm.
Nó luôn phải duyệt qua 200k files trong /usr, và chỉ in ra các file thỏa mãn điều kiên.

$ time -p find /usr/ | wc -l
291606
real 0,35
user 0,10
sys 0,26

Tất nhiên trong bài toán ví dụ này, 0.35s dù có chậm vẫn OK, nhưng nếu với input đủ lớn hay ổ cứng đủ chậm khiến việc find này mất 17s , liệu có cách nhanh hơn?

Có một cách làm khác cũng vẫn dùng find, nhưng "khó" hơn một chút: dùng option -prune.

$ man find | grep -A1 -- '       -prune'
       -prune True; if the file is a directory, do not descend into it.  If -depth is given, false; no effect.  Because -delete implies -depth, you cannot
              usefully use -prune and -delete together.

prune giúp bỏ qua các thư mục.

$ time -p find /usr/ -name src -type d -prune -o -path /usr/share -prune -o -name '*.py' -print | wc -l
9289
real 0,14
user 0,06
sys 0,08

Thời gian chạy chỉ còn 1 nửa sau khi bỏ qua thư mục lớn nhất /usr/share và các thư mục tên src.

Thêm -prune sau mỗi option lọc path muốn bỏ qua, -o là `or` để thêm nhiều điều kiện, cuối cùng luôn phải có -o điều_kiện_chọn_file -print.

fd - a new find

fd-find là câu lệnh mới xuất hiện, viết bằng rust, và nhanh hơn find nhiều lần,
có sẵn những "default" hợp lý như tự động bỏ qua các file ẩn hay file trong .gitignore, ... thích hợp khi dùng trong các thư mục code hàng ngày https://github.com/sharkdp/fd

Python os.walk

Function để duyệt qua các thư mục trong 1 thư mục "os.walk" hỗ trợ việc prune path bằng cách xóa các thư mục không muốn từ dirs, trích doc của os.walk:

    import os
    from os.path import join, getsize
    for root, dirs, files in os.walk('python/Lib/email'):
        print root, "consumes",
        print sum([getsize(join(root, name)) for name in files]),
        print "bytes in", len(files), "non-directory files"
        if 'CVS' in dirs:
            dirs.remove('CVS')  # don't visit CVS directories

Hết.

HVN at https://pymi.vn and https://www.familug.org

Tham khảo:
- https://stackoverflow.com/a/16595367/807703