Năm Dạng của MOAD-0001

MOAD-0001 xuất hiện dưới năm dạng đã được ghi nhận trên hơn 60 hệ sinh thái phần mềm. Cấu trúc: một phép kiểm tra thành viên sử dụng một vùng chứa tuần tự, được lồng bên trong một vòng lặp trên cùng vùng chứa hoặc vùng chứa liên quan.

Năm Dạng

Cả năm trường hợp đều có cùng cấu trúc: một phép kiểm tra thành viên được lồng trong vòng lặp, sử dụng một container yêu cầu quét tuyến tính để trả lời câu hỏi thành viên.

Danh sách từ khóa quét

Kiểm toán MOAD-0001 nghĩa là tìm kiếm các từ khóa kiểm tra thành viên bên trong vòng lặp:

- Python: in với biến list, .count(), list.index()

- Java: ArrayList.contains(), List.contains(), LinkedList.contains()

- JavaScript: Array.includes(), Array.indexOf(), Array.find()

- C++: std::vector::find(), vòng lặp thủ công với phép so sánh ==

- Go: slices.Contains(), vòng lặp thủ công trên slice

Giải pháp trong mọi trường hợp: thay thế container tuần tự bằng container băm. list → set. ArrayList → HashSet. Array → Set. vector → unordered_set. slice → map[T]struct{}.

Một từ khóa. Một phép thay thế. Không thay đổi hành vi. Tăng tốc 1.000× khi N=1.000.

Kiểm toán một đoạn mã

Áp dụng nhận diện mẫu MOAD-0001 cho một đoạn mã thực tế.

Một dòng lệnh, Bốn ngôn ngữ [BLOCK_TYPE fix_and_limits/the_fix]

Cách khắc phục MOAD-0001 trong bốn ngôn ngữ: [BLOCK_TYPE fix_and_limits/the_fix]

```python [BLOCK_TYPE fix_and_limits/the_fix]

Python

visited = [] # TRƯỚC: kiểm tra thành viên O(N)

visited = set() # AFTER: O(1) membership

```java
// Java
List<Node> visited = new ArrayList<>();    // BEFORE
Set<Node> visited = new HashSet<>();       // AFTER

// JavaScript
const visited = [];      // TRƯỚC: Array.includes() O(N)
const visited = new Set(); // SAU: Set.has() O(1)
// visited.push(n) → visited.add(n)
// visited.includes(n) → visited.has(n)

// Go
visited := []NodeID{}              // TRƯỚC: slices.Contains() O(N)
visited := make(map[NodeID]struct{}) // SAU: map lookup O(1)
// _, ok := visited[n]  for membership check
// visited[n] = struct{}{}  for insertion

Trong mọi trường hợp: cùng hành vi, cùng kết quả đầu ra, cùng các bài kiểm tra đều vượt qua. Chỉ tốc độ tăng trưởng thay đổi.

Những Gì Bản Sửa KHÔNG Thay Đổi

- Hành vi logic của thuật toán: duyệt theo chiều sâu vẫn duyệt theo chiều sâu

- Tính đúng đắn của đầu ra: các nút được duyệt theo đúng thứ tự (trong DFS)

- Kết quả kiểm thử: mọi bài kiểm tra tính đúng đắn vẫn tiếp tục vượt qua

Những gì Bản sửa THAY ĐỔI

- Kiểm tra thành viên: O(N) → O(1)

- Tổng vòng lặp: O(N²) → O(N)

- Với N=1.000: nhanh hơn 1.000 lần

- Với N=10.000: nhanh hơn 10.000 lần

Một giới hạn: Thứ tự

Các container kiểu hash (set, HashSet, unordered_set) không giữ nguyên thứ tự chèn. Trong Python 3.7+, dict giữ nguyên thứ tự chèn; set thông thường thì không. Trong Java, HashSet không giữ thứ tự; LinkedHashSet thì có.

Nếu cần cả thứ tự lẫn kiểm tra thành viên: duy trì hai cấu trúc. Một set (hoặc HashSet) để kiểm tra thành viên O(1). Một list (hoặc ArrayList) riêng để duyệt theo thứ tự. Hoặc dùng LinkedHashSet trong Java, cung cấp cả hai.

Đối với MOAD-0001 trong duyệt đồ thị: visited chỉ trả lời câu hỏi nhị phân (đã gặp nút này chưa?). Thứ tự không quan trọng đối với câu hỏi thành viên. Thứ tự duyệt đến từ stack hoặc queue, không phải từ visited.

Thành viên so với Thứ tự

Trong thuật toán thành phần liên thông mạnh Tarjan, onStack theo dõi các nút còn nằm trên ngăn xếp gọi DFS hiện tại. Nó phải trả lời hai câu hỏi: (1) thành viên — nút này hiện có nằm trên ngăn xếp không? (2) khi kết thúc một đường DFS, lần lượt pop các nút theo thứ tự cho đến khi gặp nút này.

Một cài đặt ngây thơ dùng List cho onStack, trả lời câu hỏi thành viên bằng contains() — O(N) mỗi lần kiểm tra, tổng O(N²) cho đồ thị lớn.

Tại sao đây là một Disclosure, không phải một Patch

MOAD-0001 tồn tại ở hơn 1.000 trang web đã được xác minh trên hơn 60 hệ sinh thái phần mềm. Duyệt đồ thị trong các công cụ build, loại bỏ tuyến trùng lặp trong các daemon định tuyến mạng, phát hiện va chạm trong game engines, phân bổ tài nguyên trong các bộ lập lịch hệ điều hành.

Mỗi trang: mã đúng. Mỗi trang: tăng trưởng O(N²) đang chờ N vượt qua ngưỡng.

Quy trình Disclosure

Một bản vá mà không có disclosure upstream chỉ sửa được một trang. Mẫu hình sẽ tái xuất hiện ở phiên bản tiếp theo, thư viện tiếp theo, bản chuyển sang ngôn ngữ tiếp theo. Disclosure: đặt tên cho mẫu hình, ghi nhận nó dưới dạng CWE-407 (Algorithmic Complexity: Inefficient Algorithmic Complexity), công bố các heuristic nhận diện và cách sửa chỉ một dòng. Sau đó mọi lập trình viên đọc disclosure đều có thể nhận diện và sửa instance của chính họ.

Hamming gọi đây là 'cho cá hay dạy câu cá.' Bản vá cho một con cá. Disclosure — MOAD-0001 được đặt tên, mẫu hình được ghi nhận, cách sửa được khái quát hóa — dạy heuristic.

Phần Mở Rộng Permacomputer

Hamming làm việc với các giải pháp điểm: sửa bộ lọc này, cải thiện đoạn mã kia. Unhamming bổ sung lớp tiết lộ: đặt tên cho mô hình, công bố heuristic, và trao nó cho cộng đồng. [BLOCK_TYPE fix_and_limits/the_disclosure]

Nguyên tắc tri thức-kết hợp áp dụng ở quy mô hệ sinh thái. Một nhà nghiên cứu đặt tên cho một mô hình. Một trăm nhà phát triển nhận ra nó trong codebase của họ. Một nghìn dòng mã O(N²) trở thành O(N). Hạ tầng trở nên nhanh hơn cho tất cả những ai xây dựng trên nền tảng đó. [BLOCK_TYPE fix_and_limits/the_disclosure]

Đây là con rồng đang lớn: cùng ngọn lửa (làm việc trên những vấn đề quan trọng, tri thức kết hợp, tư duy hệ thống), nhưng khác chuyến bay (tiết lộ mở, sở hữu chung, không cần nhà tài trợ).