python에서 string 타입의 equal이 어떻게 동작하는지 궁금해 찾아보며 공부한 내용을 기록합니다.
파이썬은 문법은 파이썬을 따르지만, 그 내부 동작 원리는 C언어를 기본으로 합니다.
아래의 링크에서 모든 파이썬 API가 내부적으로는 C언어로 만들어져 있는 것을 확인할 수 있죠
https://github.com/python/cpython
많고 많은 함수 중 제가 집중해본 함수는 unicode_eq 라는 함수입니다.
출처: https://github.com/python/cpython/blob/main/Objects/stringlib/eq.h
해당 함수는 아래와 같이 생겼습니다.
Py_LOCAL_INLINE(int)
unicode_eq(PyObject *a, PyObject *b)
{
if (PyUnicode_GET_LENGTH(a) != PyUnicode_GET_LENGTH(b))
return 0;
if (PyUnicode_GET_LENGTH(a) == 0)
return 1;
if (PyUnicode_KIND(a) != PyUnicode_KIND(b))
return 0;
return memcmp(PyUnicode_1BYTE_DATA(a), PyUnicode_1BYTE_DATA(b),
PyUnicode_GET_LENGTH(a) * PyUnicode_KIND(a)) == 0;
}
크게 어려운 함수가 아닌 것처럼 보이나, 하나씩 보면 굉장히 논리적으로 빈틈없이 설계되어 있는 것을 확인할 수 있습니다.
1.
PyUnicode_GET_LENGTH(a) != PyUnicode_GET_LENGTH(b) return 0;
이 함수는 우선 PyObject인 a, b의 길이가 다르면 return 0, 즉 False를 해버립니다.
문자열을 다 확인할 필요도 없이 길이가 다르다면 바로 False를 return 해주는 것이죠.
2.
PyUnicode_GET_LENGTH(a) == 0 return 1;
1번에서 return 이 안되었다는 것은 a와 b의 unicode 길이는 같다는 것입니다.
그런데 여기서 a의 길이가 0 이라는 것은 b도 0이라는 것이겠죠?
이 때 a와 b가 모두 길이가 0이려면 두 문자열은 모두 빈 문자열 밖에 될 수 없습니다.
그래서 a와 b는 같다. 즉 return 1을 해주는 것입니다.
3.
PyUnicode_KIND(a) != PyUnicode_KIND(b) return 0;
3번 까지 왔다는 것은 a와 b가 unicode의 길이가 같고, 그 길이가 1이상인 값입니다.
하지만, 여기서 KIND? 가 무엇이냐?
파이썬에서는 문자열의 길이를 1바이트, 2바이트, 4바이트 등으로 나누어 저장하게 되고, 이에 따라 KIND가 바뀌게 됩니다.
아래 함수를 추가적으로 확인해보면 됩니다.
enum PyUnicode_Kind {
/* Return values of the PyUnicode_KIND() function: */
PyUnicode_1BYTE_KIND = 1,
PyUnicode_2BYTE_KIND = 2,
PyUnicode_4BYTE_KIND = 4
};
즉 여기서 unicode의 길이는 어찌저찌 같아질 수 있었겠지만, 그 바이트의 크기가 다르다면 엄연히 다른 문자열이겠죠?
따라서 return 0, False값을 return 해줍니다..
4.
return memcmp(PyUnicode_1BYTE_DATA(a), PyUnicode_1BYTE_DATA(b),
PyUnicode_GET_LENGTH(a) * PyUnicode_KIND(a)) == 0;
여기까지 온다면 a와 b는 즉 unicode의 길이가 1이상으로 같고, 그 Byte KIND도 동일하겠죠?
마지막 memcmp, 즉 메모리에 있는 값의 비교를 해주는 것입니다.
실제 값의 비교는 위에서 모~~든 가능한 가지치기가 이러난 이후에 진행됩니다.
이렇게 언어 속도의 최적화를 내부적으로 하고 있는 것 같습니다.
memcmp(비교할 1번 포인터, 비교할 2번 포인터, 비교할 Byte 크기)
memcmp의 return 값으로 1번 포인터와 2번 포인터가 Byte 크기 만큼 모든 값이 같다면, 0 이 return 되고
그렇지 않은경우 앞의 값이 더 크다면 양수, 작다면 음수를 return 합니다.
이런 내용은 외울 필요는 없고, 아래의 문서에서 확인할 수 있을 정도로 될 것 같습니다.
https://cplusplus.com/reference/cstring/memcmp/
따라서!! 4번에서 memcmp의 값이 0 이라면, 결과적으로 a와 b의 값은 같아서 1(True)이 return 될 것이고.
다르다면! False, 즉 0의 값이 return 되어 모든 unicode의 비교가 끝나게 됩니다.
정리
맨 처음 해당 함수를 봤을 때
"Pyunicode_GET_LENGTH(a) == 0 보다 KIND의 비교를 먼저 해서
return 0인 경우를 먼저 체크해줘야 하는 것이 아닌가?"
라고 생각했습니다.
하지만, 코드를 보며 좀 더 생각해보면, unicode 길이 비교 -> 빈문자열 -> 종류 -> 실제 비교
의 순서를 통해 논리적인 가지치기를 하고있다는 것을 알았습니다.
또한 이 논리에는 빈틈이 없었구요..
그러고보니, 제가 정리해본 자바에서 equals() 연산자를 비교했을 때와
굉장히 유사한 순서로 비교가 이루어지고 있었습니다.
(Python, JAVA의 비교도 재밌을 것 같습니다.)
이런 과정으로 가장 큰 연산(시간이 오래 걸리는)을 가장 마지막으로 미루는 것이
하나의 최적화 방법이구나 깨달은 날입니다.
끘!!
'CS' 카테고리의 다른 글
시간 복잡도를 믿고, 나를 의심하기 (2) | 2024.04.07 |
---|