[python] 어떤 float <integer 비교가 다른 것들보다 4 배 느린 이유는 무엇입니까?
float를 정수와 비교할 때 일부 값 쌍은 비슷한 크기의 다른 값보다 평가하는 데 훨씬 오래 걸립니다.
예를 들면 다음과 같습니다.
>>> import timeit
>>> timeit.timeit("562949953420000.7 < 562949953421000") # run 1 million times
0.5387085462592742
그러나 float 또는 integer가 특정 양만큼 작거나 커지면 비교가 훨씬 빠르게 수행됩니다.
>>> timeit.timeit("562949953420000.7 < 562949953422000") # integer increased by 1000
0.1481498428446173
>>> timeit.timeit("562949953423001.8 < 562949953421000") # float increased by 3001.1
0.1459577925548956
비교 연산자를 변경해도 (예 : 사용 ==또는 >대신) 눈에 띄는 방식으로 시간에 영향을 미치지 않습니다.
이것은되지 단독으로 크거나 작은 값을 따기 빠른 비교를 초래할 수 있기 때문에 나는 그것이 비트가 줄을 어떤 불행한 방법까지 의심 때문에, 크기에 관련.
분명히,이 값들을 비교하는 것은 대부분의 사용 사례에서 충분히 빠릅니다. 왜 파이썬이 다른 것보다 어떤 값 쌍으로 더 많은 어려움을 겪고 있는지 궁금합니다.
답변
float 객체에 대한 Python 소스 코드의 주석은 다음을 인정합니다.
float와 정수를 비교할 때 특히 그렇습니다. float와 달리 Python의 정수는 임의로 클 수 있고 항상 정확하기 때문입니다. 정수를 부동 소수점으로 캐스트하려고하면 정밀도가 떨어지고 비교가 정확하지 않을 수 있습니다. 부동 소수점을 정수로 캐스트하려고하면 분수 부분이 손실되므로 작동하지 않습니다.
이 문제를 해결하기 위해 Python은 일련의 검사를 수행하여 검사 중 하나가 성공하면 결과를 반환합니다. 두 값의 부호를 비교 한 다음 정수가 “너무 큰”부동 소수점인지 여부를 비교 한 다음 부동 소수점 지수를 정수 길이와 비교합니다. 이러한 검사가 모두 실패하면 결과를 얻기 위해 비교할 두 개의 새 Python 객체를 구성해야합니다.
float v를 integer / long 과 비교할 때 w최악의 경우는 다음과 같습니다.
v와w, (모두 양수 또는 모두 음수) 같은 부호를- 정수
w는size_t유형 으로 보유 할 수있는 충분한 비트 수 (일반적으로 32 또는 64 비트)를 갖습니다. - 정수
w는 최소 49 비트입니다. - float의 지수는
v의 비트 수와 같습니다w.
그리고 이것이 바로 우리가 질문의 가치에 대해 가지고있는 것입니다.
>>> import math
>>> math.frexp(562949953420000.7) # gives the float's (significand, exponent) pair
(0.9999999999976706, 49)
>>> (562949953421000).bit_length()
49
우리는 49가 float의 지수와 정수의 비트 수 둘 다임을 알 수 있습니다. 두 숫자 모두 양수이므로 위의 네 가지 기준이 충족됩니다.
더 큰 (또는 더 작은) 값 중 하나를 선택하면 정수의 비트 수 또는 지수의 값이 변경 될 수 있으므로 Python은 값 비싼 최종 검사를 수행하지 않고 비교 결과를 확인할 수 있습니다.
이는 언어의 CPython 구현에만 해당됩니다.
더 자세한 비교
이 float_richcompare함수는 두 값 v과 의 비교를 처리합니다 w.
아래는 기능이 수행하는 검사에 대한 단계별 설명입니다. 파이썬 소스의 주석은 함수의 기능을 이해하려고 할 때 실제로 매우 도움이되므로 관련이있는 곳에 남겨 두었습니다. 또한 이러한 확인 사항을 답변 맨 아래 목록에 요약했습니다.
주요 아이디어는 파이썬 객체를 매핑하는 것입니다 v및 w이 적절한 C의 두 배에, i그리고 j다음 쉽게 올바른 결과를 제공하기 위해 비교 될 수있다. Python 2와 Python 3은 동일한 아이디어를 사용 하여이 작업을 수행합니다 (이전은 처리 int및 long유형을 별도로 처리합니다 ).
가장 먼저 할 일은 v확실히 파이썬 float 인지 확인 하고 C double에 매핑하는 것 i입니다. 다음으로 함수는 wfloat 인지 확인 하고이를 C double에 매핑합니다 j. 다른 모든 검사를 건너 뛸 수 있으므로이 기능에 가장 적합한 시나리오입니다. 기능도 검사 여부를 확인할 수 v있다 inf거나 nan:
static PyObject*
float_richcompare(PyObject *v, PyObject *w, int op)
{
double i, j;
int r = 0;
assert(PyFloat_Check(v));
i = PyFloat_AS_DOUBLE(v);
if (PyFloat_Check(w))
j = PyFloat_AS_DOUBLE(w);
else if (!Py_IS_FINITE(i)) {
if (PyLong_Check(w))
j = 0.0;
else
goto Unimplemented;
}
이제 우리는 w이러한 검사에 실패하면 파이썬 플로트가 아니라는 것을 알고 있습니다. 이제 함수가 파이썬 정수인지 확인합니다. 이 경우 가장 쉬운 테스트는 부호 v와 부호를 추출하는 것 입니다 w( 00 -1이면 음수 1이면 양수 이면 반환 ). 부호가 다르면 비교 결과를 반환하는 데 필요한 모든 정보입니다.
else if (PyLong_Check(w)) {
int vsign = i == 0.0 ? 0 : i < 0.0 ? -1 : 1;
int wsign = _PyLong_Sign(w);
size_t nbits;
int exponent;
if (vsign != wsign) {
/* Magnitudes are irrelevant -- the signs alone
* determine the outcome.
*/
i = (double)vsign;
j = (double)wsign;
goto Compare;
}
}
이 검사가 실패하면, 다음 v과 w같은 기호가 있습니다.
다음 점검은 정수의 비트 수를 계산합니다 w. 비트가 너무 많으면 플로트로 보유 할 수 없으므로 float보다 크기가 커야합니다 v.
nbits = _PyLong_NumBits(w);
if (nbits == (size_t)-1 && PyErr_Occurred()) {
/* This long is so large that size_t isn't big enough
* to hold the # of bits. Replace with little doubles
* that give the same outcome -- w is so large that
* its magnitude must exceed the magnitude of any
* finite float.
*/
PyErr_Clear();
i = (double)vsign;
assert(wsign != 0);
j = wsign * 2.0;
goto Compare;
}
반면에 정수 w가 48 개 이하의 비트를 가지면 안전하게 C double j로 바꾸고 비교할 수 있습니다.
if (nbits <= 48) {
j = PyLong_AsDouble(w);
/* It's impossible that <= 48 bits overflowed. */
assert(j != -1.0 || ! PyErr_Occurred());
goto Compare;
}
이 시점부터 w49 비트 이상의 비트 가 있음을 알고 있습니다. w양의 정수 로 취급하는 것이 편리 하므로 필요에 따라 부호와 비교 연산자를 변경하십시오.
if (nbits <= 48) {
/* "Multiply both sides" by -1; this also swaps the
* comparator.
*/
i = -i;
op = _Py_SwappedOp[op];
}
이제 함수는 float의 지수를 살펴 봅니다. float는 significand * 2 지수 로 표시 될 수 있고 significand는 0.5와 1 사이의 숫자를 나타냅니다.
(void) frexp(i, &exponent);
if (exponent < 0 || (size_t)exponent < nbits) {
i = 1.0;
j = 2.0;
goto Compare;
}
이것은 두 가지를 확인합니다. 지수가 0보다 작은 경우 float는 1보다 작습니다 (정수보다 크기가 작음). 또는 지수가 비트 수보다 작 으면 significand * 2 지수 가 2 nbit 보다 작으므로 w그 값을 갖습니다 .v < |w|
이 두 가지 검사에 실패하면 함수는 지수가의 비트 수보다 큰지 여부를 확인합니다 w. 이 프로그램이 유효수 * 2 의 지수는 2보다 큰 nbits 등 v > |w|:
if ((size_t)exponent > nbits) {
i = 2.0;
j = 1.0;
goto Compare;
}
이 검사에 실패하면 float의 지수가 v정수의 비트 수와 같다는 것을 알 수 w있습니다.
두 값을 비교할 수있는 유일한 방법은 v및 에서 두 개의 새로운 Python 정수를 구성하는 것 w입니다. 아이디어는의 소수 부분을 버리고 v정수 부분을 두 배로 한 다음 하나를 추가하는 것입니다. w또한 두 배가되며이 두 개의 새로운 Python 객체를 비교하여 올바른 반환 값을 얻을 수 있습니다. 작은 값을 가진 예제를 사용하면 4.65 < 4비교에 의해 결정됩니다 (2*4)+1 == 9 < 8 == (2*4)(거짓 반환).
{
double fracpart;
double intpart;
PyObject *result = NULL;
PyObject *one = NULL;
PyObject *vv = NULL;
PyObject *ww = w;
// snip
fracpart = modf(i, &intpart); // split i (the double that v mapped to)
vv = PyLong_FromDouble(intpart);
// snip
if (fracpart != 0.0) {
/* Shift left, and or a 1 bit into vv
* to represent the lost fraction.
*/
PyObject *temp;
one = PyLong_FromLong(1);
temp = PyNumber_Lshift(ww, one); // left-shift doubles an integer
ww = temp;
temp = PyNumber_Lshift(vv, one);
vv = temp;
temp = PyNumber_Or(vv, one); // a doubled integer is even, so this adds 1
vv = temp;
}
// snip
}
}
간결하게하기 위해 파이썬이 새로운 객체를 생성 할 때 수행해야하는 추가 오류 확인 및 가비지 추적 기능을 생략했습니다. 말할 필요도없이, 이것은 추가 오버 헤드를 추가하고 질문에서 강조 표시된 값이 다른 것보다 상당히 느린 이유를 설명합니다.
다음은 비교 기능에 의해 수행되는 점검 요약입니다.
하자 vfloat를하고 배는 C로 캐스팅. 이제 w플로트이기도합니다.
-
여부를 확인
w하다nan나inf. 그렇다면의 종류에 따라이 특수 케이스를 별도로 처리하십시오w. -
그렇지 않은 경우, 비교
v와wC의 두 배 그들의 표현에 의해 직접.
w정수인 경우 :
-
v및 의 부호를 추출합니다w. 그것들이 다르다면 우리는 알고v있고w다르며 더 큰 가치입니다. -
( 부호가 동일합니다. )
w비트가 너무 많아서 부동 소수점을 초과하지 않는지 확인하십시오size_t. 그렇다면w보다 큰 크기를 갖습니다v. -
w비트가 48 개 이하 인지 확인하십시오 . 그렇다면 정밀도를 잃지 않고 C 배로 안전하게 캐스팅 할 수 있습니다v. -
(
w48 비트 이상이 있습니다.w비교 연산을 적절히 변경하여 양의 정수로 취급 합니다. ) -
float의 지수를 고려하십시오
v. 지수가 음이면,v보다 적은1양의 정수보다 따라서 이하. 그렇지 않으면 지수가 비트w수보다 적 으면보다 작아야w합니다. -
지수의 경우
v의 비트 수보다 큰w후v보다 크다w. -
( 지수는의 비트 수와 동일합니다
w. ) -
최종 점검. 분할
v의 정수 및 분수 부분으로. 정수 부분을 두 배로하고 분수 부분을 보상하기 위해 1을 더하십시오. 이제 정수를 두 배로 늘리십시오w. 대신이 두 정수를 비교하여 결과를 얻으십시오.
답변
사용 gmpy2이 가능한 임의 정밀도 수레와 정수로하여보다 균일 비교 성능을 얻을 수 있습니다 :
~ $ ptipython
Python 3.5.1 |Anaconda 4.0.0 (64-bit)| (default, Dec 7 2015, 11:16:01)
Type "copyright", "credits" or "license" for more information.
IPython 4.1.2 -- An enhanced Interactive Python.
? -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help -> Python's own help system.
object? -> Details about 'object', use 'object??' for extra details.
In [1]: import gmpy2
In [2]: from gmpy2 import mpfr
In [3]: from gmpy2 import mpz
In [4]: gmpy2.get_context().precision=200
In [5]: i1=562949953421000
In [6]: i2=562949953422000
In [7]: f=562949953420000.7
In [8]: i11=mpz('562949953421000')
In [9]: i12=mpz('562949953422000')
In [10]: f1=mpfr('562949953420000.7')
In [11]: f<i1
Out[11]: True
In [12]: f<i2
Out[12]: True
In [13]: f1<i11
Out[13]: True
In [14]: f1<i12
Out[14]: True
In [15]: %timeit f<i1
The slowest run took 10.15 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 441 ns per loop
In [16]: %timeit f<i2
The slowest run took 12.55 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 152 ns per loop
In [17]: %timeit f1<i11
The slowest run took 32.04 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 269 ns per loop
In [18]: %timeit f1<i12
The slowest run took 36.81 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 231 ns per loop
In [19]: %timeit f<i11
The slowest run took 78.26 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 156 ns per loop
In [20]: %timeit f<i12
The slowest run took 21.24 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 194 ns per loop
In [21]: %timeit f1<i1
The slowest run took 37.61 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 275 ns per loop
In [22]: %timeit f1<i2
The slowest run took 39.03 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 259 ns per loop
