[PYTHON] 파이썬_리스트 검색

 

안녕하세요

겉바속촉입니다

!^^!

 

 

!!파이썬 시작하기!!

 

 

 

 

리스트 검색에 대해서

알아보도록 하겠습니다

 

 

 

---

 

 

 

 

리스트 검색

 

• 리스트의 특정 항목을 검색하는 INDEX 메서드
• 리스트 앞에서부터 차례로 각 항목을 확인 --> 선형 검색
• 정렬되지 않은 리스트에서 어떤 항목을 찾는 데 쓰입니다
• 중복 값이 있다면 가장 왼쪽에 있는 값을 반환해줍니다
• while 루프 사용

 

 

 

 

간단한 예시를 볼게요

리스트를 다음과 같이 만들었습니다

그리고 각각 보시면 제가 노, 주 가 있는 지 검색해본거에요!!

 

 

 

 

---

 

 

내가 원하는 값의 인덱스 찾기

 

 

방법1. while 루프를 사용한 선형 검색

 

search.py 

from typing import Any

def linear_search(lst: list, value: Any) -> int:
    '''lst에서 처음으로 나오는 인덱스를 반환하거나 lst에 value가 없는 경우 -1을 반환한다.'''

    # 0   1   2   3   4   5
    # [1,  2,  3,  4,  5,  6]
    # len => 6

    i = 0    #lst 내에서 검사할 다음 항목의 인덱스
    while i != len(lst) and lst[i] !=value:
        i = i + 1

    if i == len(lst):
        return -1
    else:
        return i

lst = [ 2, -3, 5, 9, 8, -6, 4, -15 ]
value = 5
index = linear_search(lst, value)
print(index)

 

앞에서부터 순차적으로 하나씩 검사하는 로직 구성

여기서 주의할 점 --> i 가 리스트의 length와 동일하면 안됨!!!

 

내가 찾고자하는 값은 5 이것의 인덱스는 세번째 위치해있기 때문에 2!!!

 

 

결과

 

 

 

 

 

---

 

 

 

방법2. for 루프를 사용한 선형 검색

 

for루프 -> 시작과 끝이 명확한 경우에 많이 씁니다

 

 

search.py

from typing import Any

def linear_search_for(lst: list, value: Any) -> int:
    for i in range(len(lst)):
        if lst[i] == value:
            return i

    return -1


lst = [ 2, -3, 5, 9, 8, -6, 4, -15 ]
value = 5
index = linear_search(lst, value)
print(index)

 

리스트의 length를 구해서 range로 0-7까지 구했습니다

그래서 리스트의 인덱스에 0-7을 넣어

내가 원하는 값과 일치하는 지 확인

 

 

일치한다면 그때의 인덱스 값 출력!

 

내가 찾고자하는 값은 5 이것의 인덱스는 세번째 위치해있기 때문에 2!!!

 

 

결과

 

 

 

 

---

 

 

 

방법3. 센티널 검색

 

 

 

while 루프를 이용하는 선형 검색에서 while 루프를 수행할 때마다 

루프 마감을 체크하기 위해  i != len(lst) 행위를 반복

 

불필요한 검증이 매번 루프에 포함되어있다는 것!!!

그럼 이러한 행위를 제거해서 더 효율적으로 만들려면 어떻게 해야할까요??

 

while  i != len(lst)  and lst[i] != value:

 

for루프 처럼 값이 있다 없다만 체크하게 해주면 되지 않을 까요??

 

리스트 마지막에 검색할 값을 추가

==> 리스트의 끝을 신경쓰지 않고 루프를 수행할 수 있도록 하는 기법

==> 그것이 바로 센티널

 

 

 

search.py

from typing import Any

def linear_search_sentinel(lst: list, value: Any) -> int:
    #센티널을 리스트 마지막에 추가
    lst.append(value)

    i = 0
    while lst[i] != value:           //이제 length를 확인할 필요없이 원하는 값과 일치하는지만 확인
        i = i + 1



    # 센티널을 제거
    lst.pop()               #리스트를 원래 상태로 만듦


    # 일치하는 값의 위치가 센티널과 동일한 지를 확인
    if i == len(lst):                //내가 찾는 값이 맨 마지막에서 찾아졌는 지 확인
        return -1
    else:
        return i


lst = [ 2, -3, 5, 9, 8, -6, 4, -15 ]
value = 5
index = linear_search(lst, value)
print(index)

 

 

내가 찾고자하는 값은 5 이것을 리스트 마지막에 추가해줌 --> 이게 바로 센티널

그리고 len 신경끄고 인덱스 번호 추가시키면서 5가 있나 확인

 

센티널 다시 제거해서 원래 리스트로 만들어주기

 

이제 아까 나온 인덱스 값이 리스트의 현재 len과 동일하다면 삐익

그렇지 않다면 그 전에 동일한 값이 나왔다는 것!!

 

그때의 인덱스 값 i를 출력

 

 

내가 찾고자하는 값은 5 이것의 인덱스는 세번째 위치해있기 때문에 2!!!

 

 

결과

 

 

 

 

 

---

 

 

 

이제 방법 3가지 중에서 어떤 것이 제일 좋은 지 해볼게요

 

즉 검색 시간을 측정하는 함수를 만들어 주는 거쥬!!

 

1. time_it 메서드

 

time_it(search: Callable[[list, Any], Any], L: list, v: Any) -> float:

search에는 Callable 함수가 들어오는데 list와 Any가 파라메타 타입이고 Any를 반환

파라메타 list 에 L 넣어주는 데 list 타입

파라메타 Any 에 v 넣어주는 데  Any 타입

 

그래서 최종 반환은 경과시간 float 형태

 

 

t1 = 시작할 때 타임 

t2 = search 호출 후 타임

 

차이를 구해서 1000을 곱해서 출력 (mmSec단위여서)

 

 

2. print_time 메서드

 

index 찾는 시간, 방법 3가지의 시간,

위의 방법 1, 방법2, 방법 3을 각각 가져와서 L, v 입력

 

그런데 속도가 데이터양에 따라서도 달라지기 때문에

range를 천만개를 만들어줍니다

그래서 내가 찾고자 하는 값이 앞쪽, 중간, 뒤쪽에 있을 때 어떻게 달라지는 지도 확인할게요

 

 L = list(range(10000001))    

 print_times(10, L)
 print_times(5000000, L)
 print_times(10000000, L)

 

import time
from typing import Callable, Any

def time_it(search: Callable[[list, Any], Any], L: list, v: Any) -> float:
    t1 = time.perf_counter()
    search(L, v)
    t2 = time.perf_counter()

    return (t2 - t1) * 1000.0


def print_times(v: Any, L: list) -> None:
    t1 = time.perf_counter()
    L.index(v)
    t2 = time.perf_counter()
    index_time = (t2 - t1) * 1000.0

    while_time = time_it(linear_search_while, L, v)
    for_time = time_it(linear_search_for, L, v)
    sentinel_time = time_it(linear_search_sentinel, L, v)

    print("{0}\t{1:.2f}\t{2:.2f}\t{3:.2f}\t{4:.2f}\t".format(
        v, while_time, for_time, sentinel_time, index_time))



L = list(range(10000001))    

print_times(10, L)
print_times(5000000, L)
print_times(10000000, L)

 

결과는 다음과 같습니다

 

 

for루프가 성능이 좋고

while이 가장 느리네요

센티널이 while보다는 빠르구요!!

 

내장되어 있는 index는 선형검색보다는 가장 빠른 것 같죠?!