Theo dõi đệ quy qua một cây thư mục
Theo dõi biến cục bộ và kết quả trả về trong cây thư mục, so sánh bộ nhớ với danh sách nút chờ và xác định giới hạn khi chuyển sang hệ thống tệp thực.
Một hàm đếm tệp bằng đệ quy tạm dừng lời gọi hiện tại trong lúc lời gọi khác đếm thư mục con. Khi lời gọi con trả về, lời gọi cha tiếp tục đúng chỗ đã dừng. Nếu bạn đã biết vòng lặp và đang học đệ quy, theo dõi những lần tạm dừng này hữu ích hơn việc tưởng tượng hàm khởi động lại với mọi biến được dùng chung.
Ta dùng một cây trong bộ nhớ để lần theo trước. Tệp được biểu diễn bằng None; thư mục là từ điển ánh xạ tên sang tệp hoặc thư mục khác. Hàm đếm tệp, không đếm thư mục. Từ điển rỗng vì vậy là thư mục hợp lệ không chứa tệp nào. Mô hình này cố ý đơn giản hơn hệ thống tệp thật để quyền truy cập, liên kết và thay đổi đồng thời không che khuất cách lời gọi hoạt động.
Mỗi lời gọi có tổng tạm riêng
Giả sử thư mục gốc chứa readme.txt, thư mục src có hai tệp và thư mục rỗng drafts. Kết quả mong muốn là ba. Mỗi lần gọi có biến cục bộ total riêng; biến trùng tên trong lời gọi con không ghi đè biến của lời gọi cha.
def count_files(node):
if node is None:
return 1
total = 0
for child in node.values():
total += count_files(child)
return total
project = {
"readme.txt": None,
"src": {"app.py": None, "test_app.py": None},
"drafts": {},
}
assert count_files(project) == 3
assert count_files({}) == 0Nhánh None là một điều kiện dừng được viết tường minh. Thư mục rỗng là trường hợp dừng khác, thể hiện qua vòng lặp: không có mục con để duyệt, nên hàm trả về tổng khởi tạo bằng không. Viết if not node: return 1 sẽ nhầm từ điển rỗng với dấu hiệu của tệp và đếm thư mục rỗng thành một tệp.
Khi lời gọi gốc bắt đầu, tổng của nó bằng không. Mục con đầu tiên là tệp nên lời gọi đó trả về một ngay lập tức. Gốc cộng thêm một rồi gọi hàm cho src, tạm dừng với tổng vẫn là một. Lời gọi src tạo một biến tổng khác bằng không, nhận một từ mỗi tệp con rồi trả về hai. Chỉ lúc đó, gốc mới cộng để tổng của nó thành ba.
Cây có sáu nút: ba tệp và ba thư mục, tính cả gốc. Ngăn xếp trong hình chỉ chứa đường đang hoạt động gồm gốc, src và app.py. Nó không chứa mọi nút đã duyệt hoặc mọi nút cùng cha đang chờ.
Vì sao có thể cộng kết quả từ các nhánh
Chứng minh đi theo hình dạng dữ liệu. Một nút tệp chứa đúng một tệp là chính nó, và điều kiện dừng trả về một. Giả sử mỗi lời gọi con đếm đúng số tệp trong cây con của nó. Nếu các cây con không chồng lên nhau, mỗi tệp hậu duệ thuộc đúng một cây con. Cộng các kết quả sẽ cho số tệp của thư mục mà không bỏ sót hoặc đếm lặp.
Giả định không chồng lên nhau có vai trò thực sự. Nếu hai tên cùng trỏ tới một đối tượng, hàm vẫn xem chúng là hai mục và sẽ đếm qua cả hai. Nếu thư mục chứa tham chiếu quay lại chính nó, nhánh đó không đi đến điều kiện dừng. Chứng minh đang áp dụng cho cây hữu hạn, không có chu trình và mỗi nút khác gốc chỉ có một cha.
Hàm kết thúc vì mỗi bước gọi con đi xuống thấp hơn trong cây hữu hạn. Cuối cùng, đường đi phải đến tệp hoặc thư mục rỗng. Chỉ việc trong mã có một điều kiện dừng chưa đủ bảo đảm đệ quy kết thúc. Điều kiện ấy phải được đường gọi đang xét đi tới.
Tổng số lần thăm khác số khung đang tồn tại
Gọi N là tổng số nút tệp và thư mục, còn H là số nút lớn nhất trên một đường từ gốc đến lá. Mỗi nút nhận một lời gọi, mỗi mục trong thư mục được xét một lần. Nếu duyệt mục từ điển và cộng số có chi phí hằng số, tổng công việc là Θ(N). Số lời gọi đồng thời còn hoạt động là O(H).
Một thư mục có một triệu tệp con cần nhiều công việc nhưng ngăn xếp nông. Một chuỗi gồm một triệu thư mục lồng nhau có ngăn xếp sâu, dù mỗi thư mục chỉ có một con. Hai ví dụ có số lần thăm gần nhau nhưng rủi ro về ngăn xếp khác nhau: các lời gọi tạm dừng phụ thuộc độ sâu, không phụ thuộc độ rộng.
Python giới hạn độ sâu đệ quy của trình thông dịch để bảo vệ ngăn xếp bên dưới. Tài liệu sys.setrecursionlimit cảnh báo rằng đặt giới hạn quá cao có thể làm tiến trình bị lỗi nghiêm trọng. Tăng giới hạn không phải lời giải chung cho độ sâu đầu vào không kiểm soát. Một ngăn xếp được quản lý tường minh có thể lưu trạng thái trong bộ nhớ thông thường, nơi chương trình tự đặt giới hạn và báo lỗi phù hợp.
Danh sách nút chờ làm thay đổi đánh đổi bộ nhớ
Một cách khác là giữ các nút đang chờ xử lý. Lấy một nút ra, tăng bộ đếm nếu đó là tệp; nếu là thư mục, thêm các con của nó vào danh sách. Phiên bản này không dùng lời gọi đệ quy, nhưng có thể giữ nhiều nút cùng cha một lúc.
def count_files_pending(node):
pending = [node]
total, maximum_pending = 0, 1
while pending:
current = pending.pop()
if current is None:
total += 1
else:
pending.extend(current.values())
maximum_pending = max(maximum_pending, len(pending))
return total, maximum_pending
broad = {f'file{i}': None for i in range(4)}
deep = {'a': {'b': {'c': None}}}
assert count_files_pending(broad) == (4, 4)
assert count_files_pending(deep) == (1, 1)
assert count_files(broad) == 4
assert count_files(deep) == 1Cây rộng trong ví dụ có một thư mục và bốn tệp. Duyệt đệ quy chỉ cần tối đa hai khung lời gọi đang hoạt động. Phiên bản danh sách chờ lại giữ bốn mục tệp sau khi mở rộng thư mục. Cây sâu có ba thư mục và một tệp trên cùng một đường. Đệ quy cần bốn khung, trong khi danh sách chờ không bao giờ chứa quá một nút.
Hình so sánh số khung lời gọi với số mục trong danh sách chờ, không so sánh số byte. Một khung Python và một tham chiếu trong danh sách không chiếm cùng lượng bộ nhớ. Cả hai cách còn cùng tham chiếu đến cây đầu vào, và bộ nhớ của cây được tính riêng với phần phụ dành cho việc duyệt.
Danh sách chờ vẫn xử lý mỗi nút một lần nên tổng công việc là Θ(N). Tuy nhiên, nó có thể giữ O(N) mục, ngay cả với cây nông. Thay đệ quy bằng một ngăn xếp không tự bảo toàn cận bộ nhớ phụ O(H); cần xem mỗi mục trên ngăn xếp đại diện cho gì. Nếu lưu trạng thái bộ lặp con đang tạm dừng, ta có thể mô phỏng khung đệ quy và giữ cận theo độ sâu, nhưng cần quản lý nhiều trạng thái hơn danh sách nút đơn giản.
Dấu hiệu tệp không phải định danh tệp
Mọi tệp trong mô hình học tập đều dùng cùng dấu hiệu None. Bốn lần xuất hiện vẫn đại diện cho bốn mục tệp. Nếu dùng một tập toàn cục của id(node) để tránh thăm lại, bốn dấu hiệu đó sẽ bị coi là cùng một đối tượng và bị đếm thiếu. Khi cần đếm các tệp vật lý khác nhau, mô hình dữ liệu phải mang định danh phù hợp thay vì dấu hiệu dùng chung này.
Đối tượng thư mục được chia sẻ cũng tạo khác biệt. Nếu hai tên cùng trỏ đến một từ điển, bộ đếm duyệt từ điển đó qua cả hai tên. Nếu từ điển chứa chính nó, quá trình không kết thúc. Các giả định về cây hữu hạn loại hai trường hợp này khỏi chứng minh mỗi nút chỉ được thăm một lần. Phát hiện chu trình trên đường hiện tại và loại bỏ mọi mục từng thấy trước đó là hai chính sách khác nhau; chúng có thể cho số đếm khác nhau với các cây con được chia sẻ.
Để luyện tập, hãy giữ mô hình cây hữu hạn và lần theo cả hai hàm trên ví dụ rộng, sâu trước khi chạy. Sau mỗi bước, ghi lời gọi nào đang tạm dừng hoặc những mục nào còn chờ. Một kết quả đếm cuối cùng đúng chưa giải thích được chênh lệch bộ nhớ. Cần quan sát chuỗi trạng thái đã lưu để thấy nguyên nhân.
Chuyển mô hình sang hệ thống tệp thực
Duyệt hệ thống tệp cần quy tắc đối với liên kết tượng trưng. Đi theo liên kết có thể tạo chu trình hoặc đưa chương trình đến một đích đã đếm. os.walk của Python mặc định không đi theo liên kết thư mục; tài liệu cũng cảnh báo rằng bật chế độ đi theo liên kết không khiến hàm tự theo dõi các thư mục đã thăm.
Còn một quyết định khác: đếm mục trong thư mục hay đếm các tệp vật lý khác nhau? Liên kết cứng có thể tạo nhiều tên cho cùng một tệp. Loại trùng theo định danh tệp phù hợp sẽ thay đổi kết quả và cần thêm tập đã thăm, tức thêm bộ nhớ ngoài ngăn xếp lời gọi. Nếu một tệp bị xóa trong lúc duyệt, công cụ cũng phải quyết định dừng với lỗi, bỏ qua hay ghi nhận kết quả chưa đầy đủ.
Bạn có thể để các vấn đề đó ngoài bài tập đệ quy đầu tiên, rồi bổ sung tường minh khi xây công cụ thật. Để nắm cơ chế lời gọi, ghi tổng tạm cạnh từng khung ngay trước lúc một lời gọi con trả về. Kiểm thử gốc rỗng, một dấu hiệu tệp đơn lẻ và chuỗi thư mục dài. Dấu vết phải chỉ rõ kết quả được cộng ở đâu và lời gọi cha nào còn đang đợi.