in operator 탐구.

요즘 알고리즘 공부를 하고있는데 파이썬보다는 c로 문제를 풀려고 노력중이다. 그런데 c로 코드를 짜던중 파이썬의 in operator가 c에는 없어서, 이걸 어떻게 만들어야하나 하고 생각하다가 갑자기 그럼 python의 in은 어떤 알고리즘으로 구현되있을까? 하는 생각이 들었다. 

in operator는 문자열 안에 특정 문자열이 들어있는지 검사하는 그런 operator이다.(리스트나 튜플, 딕셔너리의 경우에도 특정 원소가 있는지 검사.) 

문자열 관련해서 검색 알고리즘은 내가 알고있는건 kmp,보이어 무어밖에 없다. 이런 비스무레한걸 사용하려나..? 추측해보고 리스트나 튜플 같은경우에는 아무리 생각해봐도 하나하나 찾아보는것 이외에 특정 알고리즘을 생각할수가 없다. 그래서 c 코딩을 하다 말고 python의 in operator에 대해서 찾아봤다.

여기서 첫번째 답을 찾았다. 스트링과 관련된 in operator의 연산이다. 

답변자가 보이어 무어 알고리즘과 호스풀을 조합한거라고 하는데.. 찾아봐도 보이어 무어 호스풀 알고리즘 하나밖에 안나온다. 두개가 같은건가..? 나중에 알고리즘 카테고리에 정리해놔야겠다.

보이어 무어 호스풀 알고리즘 관련 소스코드 : http://blog.naver.com/rldk2002/110184977893

리스트의 경우에는 여기서 좋은 답을 찾을 수 있었는데 우연하게 내가 예상했던 대로 하나하나 다 탐색한다고 한다. 질문을 보면 알수 있는데 질문자가 이진 탐색으로 함? 하니까 답변자가 정렬되어 있는지 모르니까 이진 탐색을 할수없고 그냥 하나하나 탐색한다고 써놨다.

아래에 추가로 답변자가 적어놨는데 변함없는 리스트나 셋(set), 튜플 같은경우는 더 최적화됬다고 하는데 찾아보니 알고리즘의 변경으로 최적화가 됬다기보다는 다른 방법으로 최적화를 했다.

관련 자료 : https://docs.python.org/dev/whatsnew/3.2.html#optimizations

아래는 더 깊게 살펴보고 싶은 사람들을 위한 글...

in operator가 구현되어 있는 파이썬 소스코드를 찾았다.

https://hg.python.org/cpython/file/v2.7.9/Objects/abstract.c#l2377

/* Return -1 if error; 1 if ob in seq; 0 if ob not in seq.
 * Use sq_contains if possible, else defer to _PySequence_IterSearch().
 */
int
PySequence_Contains(PyObject *seq, PyObject *ob)
{
    Py_ssize_t result;
    if (PyType_HasFeature(seq->ob_type, Py_TPFLAGS_HAVE_SEQUENCE_IN)) {
        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);
}

다른건 대충 코딩을 해본 사람들이면 이해하겠고, 딱 봐도 if문에서 에러처리 비슷한걸 한 뒤 _PySequence_IterSearch 함수에서 탐색을 한다는걸 추측할수 있다.(이름도 IterSearch이다. Iter에서 알수있듯이 반복자로 어떻게 찾을것같다.) 

저 함수에 대한 구현은 여기서 찾을수 있었다. 관련 자료 찾다가 이 글도 발견했다. 함수에 관한 설명같으니 간단하게 읽어보자...

[#M_읽기|접기|

_PySequence_IterSearch() calls PyObject_GetIter() to  constuct an iterator on the sequence, then goes into an infinite loop (for (;;)) calling PyIter_Next() on the iterator until the item is found or the call to PyIter_Next() returns an error.

PyObject_GetIter() is also in abstract.c. If the object has an __iter__() method, that is called, otherwise PySeqIter_New() is called to construct an iterator.

PySeqIter_New() is implemented in iterobject.c. It's next() method is in iter_iternext(). This method calls __getitem__() on its wrapped object and increments an index for next time.

So, though the details are complex, I think it is pretty fair to say that the implementation uses a while loop (in _PySequence_IterSearch()) and a counter (wrapped in PySeqIter_Type) to implement 'in' on a container that defines __getitem__ but not __iter__.

By the way the implementation of 'for' also calls PyObject_GetIter(), so it uses the same mechanism to generate an iterator for a sequence that 

defines __getitem__().

in operator가 어떤 알고리즘으로 구성되는지 찾아보려다가 너무 깊게 들어온것 같다.

_M#]

결론.

1. 문자열을 검색시에는 보이어 무어와 호스풀을 조합한 알고리즘.

2. 리스트나 튜플 등을 찾을 때에는 그냥 하나하나 다 돌아가면서 검사.

3. 더 깊게 들어가고 싶으면 위에 설명 읽어보기.