하루

오전 9시 30분에 튜터님의 재귀함수에 대한 가르침을 받았다.

vscode 확장프로그램인 live share를 설치하여 실시간으로 튜터님과 같이 코딩을 하였다.

이진탐색 문제를 재귀적으로 푸는 법을 배웠다.

재귀함수가 호출되는 순서를 하나하나 표를 그려가며 설명해 주셨다.

어떤 순서에 어떤 값이 반환되는지 완벽하게 이해했다.

---

TIL

튜터님의 이진탐색 수업을 듣다가 궁금함이 생겼다.

이진탐색의 시간복잡도는 $O(logN)$으로 알고 있다.

Python 에는 Keyword인 In 과 Not In 이 있다.

In은 원소가 자료형 안에 들어있는지 아닌지 Boolean 을 리턴해주는 keyword 이며,

Membership Operations 으로 분류되고 있다.

In 이라는 keyword도 분명히 탐색을 해서 True, False 를 반환할텐데, 어떤 탐색 알고리즘을 사용할까?

하는 궁금증이 생겼고

4시간이라는 시간을 들여 CPython github에 들어가 어떻게 구현되어있는지 찾아보았다.

다른 연산자들은 쉽게 구현코드를 찾을 수 있었지만, keyword들은 좀 복잡하게 되어있었다.

keyword 들이 TOKEN 번호가 정해져있고 여러 함수들을 거치는 것 같았다.

나는 그 이상으로 찾아 볼 수 없어서 튜터님과 함께 찾아보았다.

튜터님이 찾아주신 참고 자료는 아래 링크다.
https://stackoverflow.com/questions/12244074/python-source-code-for-built-in-in-operator

python의 연산자는 dis.dis() 함수를 사용하여 바이트코드를 확인한다.

In 연산자는 4, COMPARE_OP byte code가 되고,
Python/ceval.c 파일에 있는 Python evaluation loop에서 다뤄진다.

TARGET(COMPARE_OP)
    PyObject *right = POP();
    PyObject *left = TOP();
    PyObject *res = cmp_outcome(oparg, left, right);
    Py_DECREF(left);
    Py_DECREF(right);
    SET_TOP(res);
    if (res == NULL)
        goto error;
    PREDICT(POP_JUMP_IF_FALSE);
    PREDICT(POP_JUMP_IF_TRUE);
    DISPATCH();

중간에 있는 cmp_outcome() 는 같은파일 안에 정의되어있고,
Switch~case 구문 안의 한 case 로 In 이 있다.

case PyCmp_IN:
    res = PySequence_Contains(w, v);
    if (res < 0)
         return NULL;
    break;

PySequence_Contains() 함수는 Objects/abstract.c 파일에 정의되어있다.

int
PySequence_Contains(PyObject *seq, PyObject *ob)
{
    Py_ssize_t result;
    PySequenceMethods *sqm = seq->ob_type->tp_as_sequence;
    if (sqm != NULL && sqm->sq_contains != NULL)
        return (*sqm->sq_contains)(seq, ob);
    result = _PySequence_IterSearch(seq, ob, PY_ITERSEARCH_CONTAINS);
    return Py_SAFE_DOWNCAST(result, Py_ssize_t, int);
}

PySequence_IterSearch() 함수에서 탐색을 하는 것 같다. Objects/abstrct.c 파일에 정의 되어있고

포인터를 NULL 이 나올때 까지 넘기면서 순차 비교를 하는 것 같다.

그 외에 내가 찾아본 자료는 2016년도에 올라온 자료이다.
https://qkqhxla1.tistory.com/597

나와 똑같은 궁금증을 가졌던 분이 계셨다.

In 을 사용하여 문자열 탐색은 패턴매칭 알고리즘을 따른다.

s1 = 'abcdef'
s2 = 'bcd'
s2 in s1

True

Objects/stringlib/fastsearch.h 파일을 뜯어보면

주석으로 "based on a mix between boyer-moore and horspool" 이라는 문장이 보인다.

보이어-무어 알고리즘과 호스풀 알고리즘을 섞은 것 같다.

내가 아는 보이어-무어 알고리즘은 pattern의 마지막 문자부터 비교를 시작하고
text가 길이 n, pattern의 길이를 m이라 할 때,
pattern의 마지막 문자가 text에 없는 문자이면 m만큼 skip을 할 수 있는 빠른 알고리즘이다.

최적의 시간은 $O(m)$ 이고, 보통 n/m개의 문자를 비교하므로 $O(n/m)$

최악의 경우, $O(nm)$ 이 걸린다.

https://stackoverflow.com/questions/10468467/what-algorithm-is-used-when-using-the-in-operator-in-python-to-search-a-list

이 글을 보면,

dict 과 set 처럼 hash 된 key를 가지지 않는 list 같은 자료형에서는,

정렬이 되어 있는지 알 수 없으므로, 이진 탐색과 같은 알고리즘을 사용하지 못해서

순차 탐색으로 구현 해 놓은 것 같다고 한다.

이진탐색과 재귀를 공부하던 중 생긴 궁금증으로, 이렇게 깊게 들여다 본 적은 정말 오랜만이다.

많은 공부가 된 것 같다.