П’ять форм 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²) загалом для великих графів.

Чому це розкриття, а не патч

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

Кожен сайт: коректний код. Кожен сайт: O(N²)-зростання, що чекає, поки N перевищить поріг.

Конвеєр розкриття

Патч без розкриття upstream виправляє лише один сайт. Шаблон повторюється в наступній версії, наступній бібліотеці, наступному портуванні мовою. Розкриття: назвати шаблон, задокументувати його як CWE-407 (Algorithmic Complexity: Inefficient Algorithmic Complexity), опублікувати евристики розпізнавання та однорядкове виправлення. Тоді кожен розробник, який прочитає розкриття, зможе розпізнати та виправити власний екземпляр.

Геммінг називав це «дати рибу чи навчити ловити рибу». Патч дає рибу. Розкриття — MOAD-0001 названо, шаблон задокументовано, виправлення узагальнено — навчає евристиці.

Розширення пермакомп’ютера

Геммінг працював над точковими рішеннями: виправити цей фільтр, покращити цей код. Антигеммінг додає шар розкриття: назвати патерн, опублікувати евристику та передати її у спільне надбання.

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

Це дракон, що росте: той самий вогонь (працювати над важливими проблемами, складне знання, системне мислення), інший політ (відкрите розкриття, спільна власність, без потреби в патроні).