Читання коду для темпів зростання
Перегляд коду для коректності в порівнянні з переглядом коду для складності
Перегляд коду для коректності виявляє логічні помилки: неправильні умови, індекси, що відрізняються на одиницю, відсутні перевірки нульових значень. Перегляд коду з урахуванням складності виявляє інший клас дефектів: код, який працює коректно при N = 100, але росте катастрофічно при N = 100,000.
Цей урок пов'язує до глибшого розслідування у курсі unhamming: The Missing Chapter: Algorithmic Complexity охоплює Big O у контексті виробничих дефектів, & MOAD-0001: The Sedimentary Defect відображає шаблон у 60+ програмних екосистемах.
Два евристики перегляду
Вкладені цикли множать складність. Два вкладені цикли над N елементів дають O(N²). Три дають O(N³). При переглядові: спочатку підрахуйте глибину вкладеності циклів.
Послідовний контейнер у гарячому циклі. Будь-яка перевірка .contains(), .includes(), .find() або in list всередині циклу коштує O(N) за перевірку. За N ітерацій: O(N²) всього. Цей шаблон з'являється у виробничому коді у десятках екосистем — компілятор GHC Haskell, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Та сама помилка, різні кодові бази.
Перегляд: find_duplicates
Перегляньте наступну функцію Python для складності:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: Осадовий дефект
Той самий дефект, шістдесят екосистем
Шаблон if x not in list: list.append(x) всередину циклу з'являється — з'являвся — у виробничому коді у десятках програмних екосистем:
- GHC (компілятор Haskell): розв'язувач залежностей, O(N²) при N = 50,000 пакунків, 17-хвилинне компіляння
- Python pip: розв'язування конфліктів залежностей
- Apache Maven: дедублікація classpath
- Rust Cargo: уніфікація функцій
- TypeScript компілятор: дозвіл модулів
- Godot / Redot ігровий движок: обхід графу вузлів
Жодна з цих команд не зробила помилку. Вони писали коректний код при малому N. N виріс. Код затвердів. Шаблон має назву: MOAD-0001, Осадовий дефект. Осад: коректний, безпечний у тонких шарах. З часом шари накопичуються та затвердівають.
Виправка
У кожному випадку: замініть послідовний контейнер на геш-контейнер. Один рядок. Нульова зміна поведінки при коректних вхідних даних. 100–1,000× прискорення при реальному світі N.
Виправка працює, тому що дві операції повинні залишатися швидкими:
1. Перевірка членства: чи цей елемент був бачений раніше?
2. Впорядкований вихід: повернути елементи в порядку їх появи (іноді потрібно, іноді ні).
Набір обробляє (1) за O(1). Якщо (2) також важливо, ведіть окремий список для впорядкованого виходу та набір для перевірки членства. Дві структури даних, кожна робить одну роботу.
Відповідь рецензентові
Запит на витяг виправляє MOAD-0001 у функції обходу графу проекту. Рецензент коментує:
> "Набори не зберігають порядок вставки — це змінює поведінку."
Шаблон інтерв'ю аналізу
Очікуваний формат
Аналіз алгоритмічної складності з'являється у інтерв'ю інженерів програмного забезпечення. Сильна відповідь слідує чотирьохчастинному шаблону:
1. Вкажіть поточну складність — O(?) для часу, O(?) для простору.
2. Поясніть чому — визначте конкретну конструкцію, відповідальну (вкладений цикл, лінійний скан у циклі, рекурсивне розгалуження).
3. Запропонуйте оптимізацію — назвіть змінення та структуру даних або алгоритм, який він вводить.
4. Вкажіть нову складність — після виправки, яка часова & просторова складність?
Приклад:
Код: [функція, яка перевіряє членство у списку всередину циклу]
Поточно: O(N²) — `item in seen_list` це O(N) за перевірку × N ітерацій
Оптимізація: замініть seen_list на seen_set (геш-набір)
Після: O(N) — перевірка членства набору це O(1)Ця навичка передається далі інтерв'ю: перегляд коду з урахуванням складності, дизайн архітектури, налагодження продуктивності, аудити безпеки. Будь-яка система, яка обробляє вхідні дані змінної розміру отримує користь від цього.
Цей урок пов'язує вперед до курсу unhamming, який застосовує цей точний шаблон для розслідування виробничих дефектів у 60+ проектах з відкритим вихідним кодом.
Інтерв'ю: Проаналізуйте has_common_element
Застосуйте чотирьохчастинний формат інтерв'ю до цієї функції:
def has_common_element(list_a, list_b):
for item in list_a:
for other in list_b:
if item == other:
return True
return False