시리즈 | LLD - 2. 덧셈의 시간복잡도는 O(logN)입니다.
Python에서 '수'를 나타내는 자료형은 int형과 float형이다.
이러한 값들은 어떠한 데이터로 C++수준에서 작동할까?
먼저 python에서 1000**1000을 계산해 보자. 놀랍게도 잘 출력된다.
C++에서는 이러한 값을 저장할 수 있는 기본 타입을 제공하지 않는다.
Unsigned long long 은 0~2^64-1의 값을 가지는데, log(2^64-1)는 약 64log2이고, log(1000^1000)=3000이다.
그렇다면 python에서는 어떤 타입으로 정수형을 저장하는 것 일까?
간단하게는 단순히 각 정수에 할당된 공간을 늘리는 방법이 있다.
typedef unsinged long long ull;
struct BigInt {
ull a0;
ull a1;
(...)
ull a?;
}그렇다면 이번에는 1000**100000를 계산해 보자
>>> 1000**10000
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limitsys.set_int_max_str_digits를 호출해서 출력 자릿수의 한계를 늘리라고 한다.
실제로 sys.set_int_max_str_digits(100000000)를 호출하면 잘 출력됨을 알 수 있다.
어떻게 함수의 호출 만으로 최대 값이 늘어난 것일까?
CPython에서 정의를 찾아보면 다음과 같다. [링크]
typedef struct _PyLongValue {
uintptr_t lv_tag; /* Number of digits, sign and flags */
digit ob_digit[1];
} _PyLongValue;
struct _longobject {
PyObject_HEAD
_PyLongValue long_value;
};Copyright (c) Python Software Foundation. Licensed under the PSF License v2.
놀랍게도 CPython에서는 array로 정수를 저장한다!
이 덕분에 python에서는 자릿수에 대한 제약이 없다.
실제로 덧셈의 정의를 살펴보면 [링크]
static PyLongObject *
long_add(PyLongObject *a, PyLongObject *b)
{
if (_PyLong_BothAreCompact(a, b)) {
stwodigits z = medium_value(a) + medium_value(b);
return _PyLong_FromSTwoDigits(z);
}
PyLongObject *z;
if (_PyLong_IsNegative(a)) {
(...)
}
else {
if (_PyLong_IsNegative(b))
z = x_sub(a, b);
else
z = x_add(a, b);
}
return z;
}Copyright (c) Python Software Foundation. Licensed under the PSF License v2.
와 같이 부호에 따라 관리하며 실제 계산은 x_add와 x_sub를 이용함을 알 수 있다.
함수 x_add를 살펴보면 [링크]
static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
Py_ssize_t size_a = _PyLong_DigitCount(a), size_b = _PyLong_DigitCount(b);
PyLongObject *z;
Py_ssize_t i;
digit carry = 0;
/* Ensure a is the larger of the two: */
if (size_a < size_b) {
{ PyLongObject *temp = a; a = b; b = temp; }
{ Py_ssize_t size_temp = size_a;
size_a = size_b;
size_b = size_temp; }
}
z = long_alloc(size_a+1);
if (z == NULL)
return NULL;
for (i = 0; i < size_b; ++i) {
carry += a->long_value.ob_digit[i] + b->long_value.ob_digit[i];
z->long_value.ob_digit[i] = carry & PyLong_MASK;
carry >>= PyLong_SHIFT;
}
for (; i < size_a; ++i) {
carry += a->long_value.ob_digit[i];
z->long_value.ob_digit[i] = carry & PyLong_MASK;
carry >>= PyLong_SHIFT;
}
z->long_value.ob_digit[i] = carry;
return long_normalize(z);
}Copyright (c) Python Software Foundation. Licensed under the PSF License v2.
와 같이 실제로 각 digit 당 계산하고 있음을 알 수 있다.
여기서 for문 2개가 중첩이 아닌 나열되어 있고, 자릿수에 따라 반복 횟수가 증가하므로 시간 복잡도는 O(logN)임을 알 수 있다.
그렇다면 파이썬에서 덧셈을 이용한 알고리즘 등은 일반적인 시간 복잡도와 다를까?
사실은 대부분의 경우 그렇지 않다.
ob_digits이 digit[]으로 정의되어 혼동될 수 있으나, digit의 정의를 찾아보면 [링크]
typedef uint32_t digit;Copyright (c) Python Software Foundation. Licensed under the PSF License v2.
로, uint32_t의 타입을 가진다.
uint32_t는 컴파일러와 상관 없이 32bit사용을 강제하는 타입이므로 약 32bit 내에 표현 가능한 값은 한 번의 loop만 거치게 된다.
따라서 대부분의 상황에서 O(1)의 성능을 가짐을 알 수 있다.
다만, 앞에서 살펴 보았듯이 캐스팅, 포인터 접근 등 다양한 단계가 있으므로 C++에 비해서는 현저히 느린 것은 사실이다.
Comments ()