보초법

제로베이스 데이터 취업 스쿨 2주차 스터디노트 7호

영어로는 Sentinel Method라고 한다.

수업에서 내용을 듣고는 띠용? 했다.

찾고자 하는 값을 왜 굳이 마지막 index에 추가하는건데?
그러면 더 효율적이라고?

# seq라는 list에서 v 값을 찾는 코드
def linear_search(v, seq):
	idx = 0
	while True:
		if idx == len(seq):
			return -1
		if seq[idx] == v:
    		return idx
		idx += 1

위의 코드에서는 반복문이 한번 돌 때마다 2개의 조건을 판단을 해야 한다.
보초법을 한번 사용해보자.

# seq라는 list에서 v 값을 찾는 코드
def linear_search(v, seq):
    seq.append(v)
	idx = 0
	while True:
		if seq[idx] == v:
			break
		idx += 1
	if idx == len(seq) - 1:
    	return -1
	return idx

위의 코드에서는 반복문이 한번 돌 때마다 조건 1개만 판단한다.
마지막에만 2가지 조건을 판단한다.

정말 신박한 아이디어인데,
왠만하면 선형탐색을 하진 않을테니...
공부하는 의미가 있나?
그래도 궁금해서 견딜 수가 있어야지.

사실 앞선 예제도 보초법 설명을 위해 억지로 만들어낸 경향이 없잖아 있다.
for문 쓰면 if문이 2개 들어갈 필요도 없지 않나?

def linear_search(v, seq):
	for idx, item in enumerate(seq):
    	if item == v:
        	return idx
	else:
    	return -1

찾아보니 for문이 while문보다 performance도 좋은데...

뭐 아무튼 작은 sequence 데이터가 수많이 있고,
그 sequence의 length를 알 수 없는데,
순차 탐색을 해야 할 일이 많다면
유용하게 쓰일 수 있을 듯 하다.

다만, 요즘 세상은 하드웨어 성능이 워낙 좋으니,
퍼포먼스보다는 가독성을 우선시하는 경향이 없잖아 있지 않나?
진짜 퍼포먼스가 중요하다면,
모듈이 있던 없던 데이터 전처리를 C++로 해야 할 것이다.
(그게 훨씬 효율적일테니까)
뭐... 돈이 훨씬 많이 들긴 하겠지?

아무튼 보초법은 쓸 일이 왠만하면 없을거라는 소리.