반복 탐색과 키 조회 비교

조회 비용을 비교하는 이유

ID 조회를 한 번만 할 때와 수백 번 할 때는 구조 선택의 근거가 다릅니다. 리스트는 앞에서부터 ID가 같은지 비교할 수 있고 딕셔너리는 키를 이용해 값을 찾습니다. 이번에는 시간 측정보다 비교 횟수를 세어 탐색이 입력 크기에 어떻게 반응하는지 확인합니다. 컴퓨터 부하에 따라 흔들리는 초 단위 결과 대신 명시적인 작업 단위를 정합니다. 기록 수 n과 target 위치를 따로 바꾸며 마지막 기록과 없는 기록을 구분합니다.

카운터 위치를 정합니다

comparisons는 함수 호출 시작에 0으로 초기화합니다. for record in records 안에서 ID 비교 직전에 1 증가시키고 같으면 결과와 비교 수를 반환합니다. 첫 ID면 1회, 마지막 ID면 n회, 없는 ID면 n회입니다. 빈 리스트는 비교 0회이고 없음 결과를 반환합니다. 찾은 뒤 break나 return이 없으면 첫 기록도 끝까지 훑게 되므로 작업량을 과대하게 셉니다. 이 카운터는 제목 복사나 반복문 준비 등 다른 작업의 수를 측정하지 않습니다.

같은 질문을 두 구조에 던집니다

목록과 딕셔너리는 같은 ID를 가진 같은 기록을 사용해야 합니다. 목록은 ID가 같은지 순서대로 비교하고 딕셔너리는 store.get(target)으로 조회합니다. 둘의 FOUND와 NOT_FOUND가 같다는 정확성을 먼저 확인한 뒤 비용을 이야기합니다. 딕셔너리 호출이 코드 한 줄이라는 것은 내부에서 한 번 비교한다는 뜻이 아닙니다. 실습 출력의 LIST 비교 수와 DICT 성공 여부는 서로 다른 측정 항목입니다. 내부 해시 비교 수를 측정한 것처럼 숫자 1을 붙이지 않습니다.

해시와 동등한 키

딕셔너리는 키의 해시값을 이용해 후보를 찾고 동등성 비교로 해당 키를 구별합니다. 내용이 같은 두 문자열은 같은 키로 조회됩니다. 같은 해시값을 가진 서로 다른 키가 생길 수 있어 해시값만으로 동등성을 결정하지 않습니다. 문자열 ID는 키로 쓸 수 있지만 리스트는 해시 가능한 키가 아니어서 TypeError: unhashable type: list가 발생합니다. 복합 식별자가 필요해도 이번 계약의 문자열 ID를 유지하고 데이터 구조 자체를 키로 넘기는 실수를 피합니다.

평균과 최악을 구분합니다

리스트 반복 탐색은 최악 O(n)입니다. 일반적인 해시 분포와 통상적인 비용 가정에서 딕셔너리 키 조회는 평균 O(1)로 설명합니다. 충돌 등이 집중된 최악 상황은 O(n)이 될 수 있으므로 항상 한 번 또는 항상 같은 시간이라고 쓰지 않습니다. O 표기는 입력 크기에 따른 증가 경향이며 정확한 초나 CPU 명령 수가 아닙니다. 이번 n=10과 n=100의 실험은 작성한 반복 탐색의 비교 수를 확인하는 증거이지 모든 Python 구현의 속도를 보장하지 않습니다.

색인을 만드는 비용도 있습니다

기존 목록에서 ID 딕셔너리를 만들려면 n건을 순회합니다. 이는 O(n) 작업과 추가 저장 공간을 요구합니다. 한 번 조회하고 버릴 작은 목록이면 구축 비용이 이득보다 클 수 있습니다. 반복 조회가 많은 저장소는 추가할 때부터 키로 관리할 이유가 생깁니다. 미션은 딕셔너리 하나를 원본으로 사용하므로 매 조회마다 새 인덱스를 만들지 않습니다. 목록을 만드는 list_records와 완료 필터는 전체를 순회하며 반환 기록을 복사하므로 ID 조회와 같은 비용이라고 설명하지 않습니다.

순서와 속도를 함께 검토합니다

순서가 필요하다는 이유만으로 딕셔너리를 배제하지 않습니다. 이 환경의 삽입 순서 보장을 사용해 추가 순서의 values를 순회할 수 있습니다. 반대로 위치 기반 슬라이싱이나 다양한 정렬 결과가 필요하면 리스트가 표현하기 쉽습니다. 업무의 질문이 특정 ID 한 건인지 전체 완료 기록인지 먼저 구분합니다. 구조 선택 문서는 두 작업의 빈도와 반환 형태를 설명해야 합니다. 무조건 빠른 구조라는 말보다 어떤 조회를 얼마나 자주 하는지 적는 것이 리뷰에 도움이 됩니다.

실험 입력과 경계

브라우저 입력은 첫 줄 n, 다음 줄 target입니다. n은 0 이상 정수이고 기록은 문자열 ID 0부터 n-1까지 자동 생성합니다. target은 정확한 문자열로 조회하므로 01은 1과 다른 키입니다. 첫 줄 출력은 LIST|FOUND 또는 NOT_FOUND|비교횟수이고 다음 줄은 DICT|FOUND 또는 NOT_FOUND입니다. 리스트 함수의 return 위치와 카운터를 완성하며 딕셔너리 출력은 제공된 코드로 확인합니다. 10건과 100건 마지막 ID, 첫 ID, 없는 ID, 빈 목록을 함께 검사합니다.

관찰 표를 먼저 적습니다

n이 10일 때 첫 ID 0은 1회, 마지막 ID 9는 10회, missing은 10회입니다. n이 100일 때 마지막 ID 99와 missing은 100회입니다. 빈 목록은 target이 무엇이든 0회입니다. 이 표를 기대값으로 적고 실제 출력과 비교합니다. 기대 횟수를 search 함수로 계산하면 잘못된 카운터를 정답에도 복제할 수 있습니다. 한 칸 부족하면 count를 비교 뒤에 증가시키거나 첫 기록을 세지 않은 줄을 살펴봅니다. 한 칸 많으면 반복 밖의 증가가 있는지 확인합니다.

없는 기록의 반환 위치를 확인합니다

for 안에서 첫 불일치에 None을 반환하면 뒤에 있는 기록을 찾지 못합니다. FOUND 반환은 일치 조건 안에 두고 NOT_FOUND 반환은 반복이 끝난 뒤에 둡니다. ID 0만 검사하면 이런 버그도 통과하므로 마지막 ID를 추가합니다. 카운터는 호출마다 새로 초기화해 두 번째 검색에 첫 검색의 횟수가 섞이지 않게 합니다. 미션에는 반복 탐색 카운터가 API로 들어가지는 않으며 문서에 별도 실험으로 남깁니다. 실제 store 조회와 실험 함수의 측정 목적을 구분합니다.

비용 설명의 전제를 적습니다

ID 문자열 길이가 크게 늘면 해시 계산과 문자열 비교 비용도 영향을 받습니다. 이번 실험은 짧은 ID를 사용하고 입력 크기는 기록 개수로 정의합니다. 평균 O(1) 설명은 이러한 연산 비용 가정을 포함한 모델입니다. 특정 수치로 딕셔너리가 몇 배 빠르다고 단정하지 않습니다. 구조 문서에는 반복 비교 횟수 표, 키 조회 선택 이유, 구축과 전체 순회의 비용, 평균과 최악의 차이를 함께 남깁니다. 사람이 읽을 때 get 호출 수를 내부 비교 수로 잘못 적지 않았는지 검토합니다.