성장률을 위해 코드 읽기
정확성을 위한 코드 리뷰 vs 복잡도를 위한 코드 리뷰
정확성을 위한 코드 리뷰는 논리 오류를 찾습니다: 잘못된 조건, off-by-one 인덱스, 누락된 null 체크. 복잡도 인식 코드 리뷰는 다른 클래스의 결함을 찾습니다: N = 100에서 정확하게 작동하지만 N = 100,000에서 급격하게 증가하는 코드.
이 수업은 unhamming 과정의 더 깊은 조사와 연결됩니다: 빠진 장: 알고리즘 복잡도는 프로덕션 결함의 맥락에서 Big O를 다루고, & MOAD-0001: 퇴적질 결함은 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: 퇴적질 결함
같은 결함, 60개 생태계
if x not in list: list.append(x) 패턴은 루프 내부에서 나타납니다 — 수십 개의 소프트웨어 생태계 전반의 프로덕션 코드에 나타났습니다:
- GHC (Haskell 컴파일러): 의존성 리졸버, N = 50,000 패키지에서 O(N²), 17분 빌드
- Python pip: 의존성 충돌 해결
- Apache Maven: 클래스패스 중복 제거
- Rust Cargo: 기능 통합
- TypeScript 컴파일러: 모듈 해결
- Godot / Redot 게임 엔진: 노드 그래프 탐색
이 팀들 중 어느 것도 실수를 하지 않았습니다. 그들은 작은 N에서 정확한 코드를 작성했습니다. N이 증가했습니다. 코드가 경화되었습니다. 패턴의 이름이 있습니다: MOAD-0001, 퇴적질 결함. 퇴적물: 얇은 층에서는 정확하고 무해합니다. 시간이 지남에 따라 층이 축적되고 경화됩니다.
수정
모든 경우에: 순차 컨테이너를 해시 컨테이너로 바꾸십시오. 한 줄. 정확한 입력에서 0 동작 변경. 실제 N에서 100–1,000× 속도 증가.
수정이 작동하는 이유는 두 가지 작업이 빠르게 유지되어야 하기 때문입니다:
1. 멤버십 확인: 이 요소를 이전에 본 적이 있습니까?
2. 정렬된 출력: 요소를 나타난 순서대로 반환 (때로는 필요, 때로는 필요 없음).
세트는 (1)을 O(1)에서 처리합니다. (2)도 중요한 경우 정렬된 출력을 위해 별도의 리스트와 멤버십 확인을 위해 세트를 유지하십시오. 각각 한 가지 작업을 수행하는 두 개의 데이터 구조.
리뷰어에게 응답하기
풀 요청이 프로젝트의 그래프 탐색 함수에서 MOAD-0001을 수정합니다. 리뷰어가 댓글을 달았습니다:
> "세트는 삽입 순서를 보존하지 않습니다 — 이것은 동작을 변경합니다."
인터뷰 분석 패턴
예상되는 형식
알고리즘 복잡도 분석은 소프트웨어 엔지니어링 인터뷰에 나타납니다. 강한 답변은 네 부분 패턴을 따릅니다:
1. 현재 복잡도 명시 — 시간 O(?), 공간 O(?).
2. 왜인지 설명 — 책임 있는 특정 구성 식별 (중첩 루프, 루프 내 선형 스캔, 재귀 분기).
3. 최적화 제안 — 변경 이름 및 도입하는 데이터 구조 또는 알고리즘.
4. 새로운 복잡도 명시 — 수정 후 시간 & 공간 복잡도는 무엇입니까?
예:
코드: [루프 내 리스트에서 멤버십을 확인하는 함수]
현재: O(N²) — `item in seen_list`는 N번의 반복당 O(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