Пять форм MOAD-0001

MOAD-0001 встречается в пяти задокументированных формах в более чем 60 программных экосистемах. Структура: проверка членства с использованием последовательного контейнера, вложенная в цикл по той же или связанной коллекции.

Пять форм

Все пять форм имеют одинаковую структуру: проверка принадлежности, вложенная в цикл, с использованием контейнера, требующего линейного сканирования для ответа на вопрос о принадлежности.

Ключевые слова сканирования

Аудит MOAD-0001 подразумевает поиск ключевых слов проверки принадлежности внутри циклов:

- Python: in с переменной типа list, .count(), list.index()

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

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

- C++: std::vector::find(), ручной цикл с оператором ==

- Go: slices.Contains(), ручной цикл по слайсу

Исправление во всех случаях: замените последовательный контейнер на хеш-контейнер. list → set. ArrayList → HashSet. Array → Set. vector → unordered_set. slice → map[T]struct{}.

Одно ключевое слово. Одна подстановка. Никаких изменений поведения. Ускорение в 1 000× при N=1 000.

Аудит фрагмента кода

Примените распознавание паттерна MOAD-0001 к реальному фрагменту кода.

One Line, Four Languages [BLOCK_TYPE SECTION/STEP]

The fix for MOAD-0001 in four languages: [BLOCK_TYPE SECTION/STEP]

```python [BLOCK_TYPE SECTION/STEP]

Python

visited = [] # BEFORE: O(N) membership

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

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

// JavaScript
const visited = [];      // ДО: Array.includes() O(N)
const visited = new Set(); // ПОСЛЕ: Set.has() O(1)
// visited.push(n) → visited.add(n)
// visited.includes(n) → visited.has(n)

// Go
visited := []NodeID{}              // ДО: slices.Contains() O(N)
visited := make(map[NodeID]struct{}) // ПОСЛЕ: map lookup O(1)
// _, ok := visited[n]  для проверки принадлежности
// visited[n] = struct{}{}  для вставки

Во всех случаях: одинаковое поведение, одинаковый вывод, тесты проходят. Меняется только скорость роста.

Что исправление НЕ меняет

- Логическое поведение алгоритма: поиск в глубину остаётся поиском в глубину

- Корректность вывода: те же узлы посещаются в том же порядке (в рамках DFS)

- Результаты тестов: все тесты, проверяющие корректность, продолжают проходить

Что исправление ИЗМЕНЯЕТ

- Проверка членства: O(N) → O(1)

- Общее время цикла: O(N²) → O(N)

- При N=1,000: в 1 000 раз быстрее

- При N=10,000: в 10 000 раз быстрее

Одно ограничение: Порядок

Хэш-контейнеры (set, HashSet, unordered_set) не сохраняют порядок вставки. В Python 3.7+ dict сохраняет порядок вставки; обычный set — нет. В Java HashSet не сохраняет порядок; LinkedHashSet — сохраняет.

Если порядок важен наряду с проверкой принадлежности: поддерживайте две структуры. set (или HashSet) для O(1)-проверок принадлежности. Отдельный list (или ArrayList) для упорядоченного обхода. Или используйте LinkedHashSet в Java, который даёт оба свойства.

Для MOAD-0001 в обходе графа: visited отвечает на бинарный вопрос (был ли этот узел уже посещён?). Порядок не важен для вопроса о принадлежности. Порядок обхода определяется стеком или очередью, а не visited.

Принадлежность vs Порядок

В алгоритме Тарьяна для поиска сильно связных компонентов onStack отслеживает, какие узлы остаются в текущем стеке вызовов DFS. Он должен отвечать на два вопроса: (1) принадлежность — находится ли этот узел сейчас в стеке? (2) в конце DFS-пути — выталкивать узлы в порядке до появления этого узла.

Наивная реализация использует List для onStack, отвечая на вопрос о принадлежности с помощью contains() — O(N) на проверку, O(N²) всего для больших графов.

Почему это Disclosure, а не патч

MOAD-0001 присутствует более чем в 1000 подтверждённых местах в 60+ программных экосистемах. Обход графа в инструментах сборки, дедупликация маршрутов в сетевых демонах, обнаружение коллизий в игровых движках, распределение ресурсов в планировщиках операционных систем.

Каждое место: корректный код. Каждое место: O(N²)-рост, ожидающий, пока N пересечёт порог.

Пайплайн Disclosure

Патч без раскрытия upstream исправляет одно место. Паттерн повторяется в следующей версии, следующей библиотеке, следующем порте на другой язык. Disclosure: назвать паттерн, задокументировать его как CWE-407 (Algorithmic Complexity: Inefficient Algorithmic Complexity), опубликовать эвристики распознавания и однострочное исправление. Тогда каждый разработчик, прочитавший disclosure, сможет распознать и исправить свой собственный случай.

Хэмминг называл это «дать рыбу или научить ловить рыбу». Патч даёт рыбу. Disclosure — MOAD-0001 назван, паттерн задокументирован, исправление обобщено — учит эвристике.

Расширение Permacomputer

Хэмминг работал над точечными решениями: исправить этот фильтр, улучшить этот код. Unhamming добавляет слой раскрытия: назвать паттерн, опубликовать эвристику и передать её в общее пользование.

Принцип накопления знаний применяется здесь в масштабе экосистемы. Один исследователь называет паттерн. Сто разработчиков узнают его в своих кодовых базах. Тысяча строк кода O(N²) превращаются в O(N). Инфраструктура становится быстрее для всех, кто на ней строит.

Это дракон растёт: тот же огонь (работа над важными проблемами, накопление знаний, системное мышление), другой полёт (открытое раскрытие, общее владение, без необходимости в патроне).