파이썬 부동 소수점 값을 가능한 최소로 증가시킵니다.
부동 소수점 값을 사전 키로 사용하고 있습니다.
때때로, 아주 가끔 (아마도 절대 안되지만 절대 절대 안되는 것은 아님) 충돌이있을 것입니다. 가능한 한 적은 양으로 부동 소수점 값을 증가시켜이 문제를 해결하고 싶습니다. 어떻게 할 수 있습니까?
C에서 나는 이것을 달성하기 위해 가수의 비트를 회전시킬 것이지만 파이썬에서는 불가능하다고 가정합니다.
파이썬 부동 소수점 값을 가능한 최소로 증가시킵니다.
당신은 미쳤지 않고 이것을 할 수 있어야합니다. 슬프게도 Python 2.X와 Python3000 모두에서 현재 Python 수학 라이브러리의 단점입니다. math.nextafter(x,y)파이썬 에는 있어야 하지만 그렇지 않습니다. 대부분의 C 컴파일러에 기능이 있기 때문에 추가하는 것은 간단합니다.
nextafter (x, y)의 함수 (Y)의 방향으로 다음 이산 다른 표현할 부동 소수점 값을 다음 X를 반환한다. nextafter () 함수는 플랫폼에서 작동하거나 다음 값이 불가능 함을 나타내는 합리적인 값을 반환하도록 보장됩니다.
nextafter()기능의 일부 POSIX 및 ISO C99 표준이며 카메라 C에서 () _nextafter . C99 호환 표준 수학 라이브러리, Visual C, C ++, Boost 및 Java는 모두 IEEE 권장 nextafter () 함수 또는 메서드를 구현합니다. (.NET에 nextafter ()가 있는지 솔직히 알 수 없습니다. Microsoft는 C99 또는 POSIX에 대해별로 신경 쓰지 않습니다.)
파이썬이 수학 모듈에 대한 대부분의 C99 수학 함수 및 동작을 지원하는 방향으로 가고있는 것처럼 보이므로 제외하는 nextafter()것이 궁금합니다. 다행히 쉬운 해결 방법이 있습니다.
없음 비트 만지작 기능이있어 완전히 또는 올바르게 등 위에 0.0 가지만 값 마이너스 0.0 subnormals, 무한대, 음의 값 또는 언더 플로우로서, 에지의 경우에 대처하지 여기서 C에서 nextafter ()를 참조 구현 인 그것이 당신의 방향이라면 올바른 비트 twiddling을 수행하는 방법에 대한 아이디어를 제공합니다.
nextafter()Python에서 제외 된 POSIX 수학 함수 를 얻 거나 다른 두 가지 확실한 해결 방법이 있습니다 .
Numpy 사용 :
>>> import numpy
>>> numpy.nextafter(0,1)
4.9406564584124654e-324
>>> numpy.nextafter(.1, 1)
0.10000000000000002
>>> numpy.nextafter(1e6, -1)
999999.99999999988
>>> numpy.nextafter(-.1, 1)
-0.099999999999999992
시스템 수학 DLL에 직접 연결 :
import ctypes
import sys
from sys import platform as _platform
if _platform == "linux" or _platform == "linux2":
_libm = ctypes.cdll.LoadLibrary('libm.so.6')
_funcname = 'nextafter'
elif _platform == "darwin":
_libm = ctypes.cdll.LoadLibrary('libSystem.dylib')
_funcname = 'nextafter'
elif _platform == "win32":
_libm = ctypes.cdll.LoadLibrary('msvcrt.dll')
_funcname = '_nextafter'
else:
# these are the ones I have access to...
# fill in library and function name for your system math dll
print "Platform", repr(_platform), "is not supported"
sys.exit(0)
_nextafter = getattr(_libm, _funcname)
_nextafter.restype = ctypes.c_double
_nextafter.argtypes = [ctypes.c_double, ctypes.c_double]
def nextafter(x, y):
"Returns the next floating-point number after x in the direction of y."
return _nextafter(x, y)
assert nextafter(0, 1) - nextafter(0, 1) == 0
assert 0.0 + nextafter(0, 1) > 0.0
그리고 정말로 순수한 파이썬 솔루션을 원한다면 :
# handles edge cases correctly on MY computer
# not extensively QA'd...
import math
# 'double' means IEEE 754 double precision -- c 'double'
epsilon = math.ldexp(1.0, -53) # smallest double that 0.5+epsilon != 0.5
maxDouble = float(2**1024 - 2**971) # From the IEEE 754 standard
minDouble = math.ldexp(1.0, -1022) # min positive normalized double
smallEpsilon = math.ldexp(1.0, -1074) # smallest increment for doubles < minFloat
infinity = math.ldexp(1.0, 1023) * 2
def nextafter(x,y):
"""returns the next IEEE double after x in the direction of y if possible"""
if y==x:
return y #if x==y, no increment
# handle NaN
if x!=x or y!=y:
return x + y
if x >= infinity:
return infinity
if x <= -infinity:
return -infinity
if -minDouble < x < minDouble:
if y > x:
return x + smallEpsilon
else:
return x - smallEpsilon
m, e = math.frexp(x)
if y > x:
m += epsilon
else:
m -= epsilon
return math.ldexp(m,e)
또는 Mark Dickinson의 탁월한 솔루션을 사용하십시오.
분명히 Numpy 솔루션이 가장 쉽습니다.
첫째, "충돌에 대한 대응"은 매우 나쁜 생각입니다.
충돌하는 경우 사전의 값은 개별 항목이 아니라 공통 키가있는 항목 목록이어야합니다.
"해시 프로빙"알고리즘은 충돌을 해결하기 위해 하나 이상의 "작은 증분"을 반복해야합니다.
그리고 순차 해시 프로브는 비효율적 인 것으로 알려져 있습니다.
이것을 읽으십시오 : http://en.wikipedia.org/wiki/Quadratic_probing
둘째, 사용 math.frexp및 sys.float_info.epsilon별도 가수와 지수와 바이올린합니다.
>>> m, e = math.frexp(4.0)
>>> (m+sys.float_info.epsilon)*2**e
4.0000000000000018
import sys
>>> sys.float_info.epsilon
2.220446049250313e-16
가능한 경우 플로트 (또는 타임 스탬프)가 고유하다고 가정하지 않는 것이 좋습니다. 계수 반복기, 데이터베이스 시퀀스 또는 기타 서비스를 사용하여 고유 한 식별자를 발급합니다.
값을 증가시키기 위해 충돌 키에 튜플을 사용하십시오. 순서대로 유지해야하는 경우 모든 키는 중복이 아닌 튜플이어야합니다.
잠시 동안 부동 소수점 값을 증가시키고 싶은 이유를 잊어 버리면 Autopulated의 자체 답변이 아마도 정확하다고 생각합니다.
그러나 문제 영역의 경우, 수레를 사전 키로 사용하는 아이디어에 대한 대부분의 응답자의 잘못된 점을 공유합니다. Decimal (주요 의견에서 제안한대로) 사용에 대한 이의가 "무거운"솔루션이라는 것이라면 DIY 타협을 제안합니다. 타임 스탬프에 실제 해상도가 무엇인지 파악하고 자릿수를 선택합니다. 적절하게 커버하려면 모든 타임 스탬프에 필요한 양을 곱하여 정수를 키로 사용할 수 있습니다. 타이머 정밀도를 초과하는 추가 숫자 또는 두 자리를 감당할 수 있다면 충돌이 없거나 더 적을 것이라고 확신 할 수 있으며 충돌이 있으면 1을 더할 수 있습니다 (일부 리가 마롤 대신 다음 부동 소수점 값).
더 나은 대답 (이제 나는 재미로 이것을하고 있습니다 ...), 비트를 뒤틀어 동기를 부여했습니다. 음수 값의 부분 사이의 캐리 및 오버플로를 처리하는 것은 다소 까다 롭습니다.
import struct
def floatToieee754Bits(f):
return struct.unpack('<Q', struct.pack('<d', f))[0]
def ieee754BitsToFloat(i):
return struct.unpack('<d', struct.pack('<Q', i))[0]
def incrementFloat(f):
i = floatToieee754Bits(f)
if f >= 0:
return ieee754BitsToFloat(i+1)
else:
raise Exception('f not >= 0: unsolved problem!')
부동 타임 스탬프를 수정하는 대신 Mark Ransom 이 튜플 (x,y)이 x=your_unmodified_time_stamp및 로 구성된 위치를 제안 하는 것처럼 모든 키에 튜플을 사용하십시오 y=(extremely unlikely to be a same value twice).
그래서:
x수정되지 않은 타임 스탬프이며 동일한 값을 여러 번 사용할 수 있습니다.y당신이 사용할 수있는:- 큰 범위의 임의의 정수,
- 직렬 정수 (0,1,2 등),
- UUID .
2.1 (큰 범위의 임의의 정수)이 이더넷에서 잘 작동하지만 2.2 (시리얼 라이저) 또는 2.3 (UUID)을 사용합니다. 쉽고 빠르며 방탄입니다. 2.2와 2.3의 경우 충돌 감지가 필요하지 않습니다 (이더넷과 마찬가지로 2.1에서도 여전히 사용할 수 있습니다.)
2.2의 장점은 부동 타임 스탬프가 동일한 데이터 요소를 구분하고 정렬 할 수도 있다는 것입니다.
그런 다음 x정렬 유형 작업을 위해 튜플에서 추출 하면 튜플 자체가 해시 / 사전에 대한 충돌없는 키입니다.
편집하다
예제 코드가 도움이 될 것 같습니다.
#!/usr/bin/env python
import time
import sys
import random
#generator for ints from 0 to maxinteger on system:
serializer=(sn for sn in xrange(0,sys.maxint))
#a list with guranteed collisions:
times=[]
for c in range(0,35):
t=time.clock()
for i in range(0,random.choice(range(0,4))):
times.append(t)
print len(set(times)), "unique items in a list of",len(times)
#dictionary of tuples; no possibilities of collisions:
di={}
for time in times:
sn=serializer.next()
di[(time,sn)]='Element {}'.format(sn)
#for tuples of multiple numbers, Python sorts
# as you expect: first by t[0] then t[1], until t[n]
for key in sorted(di.keys()):
print "{:>15}:{}".format(key, di[key])
산출:
26 unique items in a list of 55
(0.042289, 0):Element 0
(0.042289, 1):Element 1
(0.042289, 2):Element 2
(0.042305, 3):Element 3
(0.042305, 4):Element 4
(0.042317, 5):Element 5
# and so on until Element n...
충돌 키 k의 경우 다음을 추가합니다. k / 2 50
흥미로운 문제입니다. 추가해야하는 양은 충돌 값의 크기에 따라 분명히 달라 지므로 정규화 된 추가는 최하위 비트에만 영향을줍니다.
It's not necessary to determine the smallest value that can be added. All you need to do is approximate it. The FPU format provides 52 mantissa bits plus a hidden bit for 53 bits of precision. No physical constant is known to anywhere near this level of precision. No sensor is able measure anything near it. So you don't have a hard problem.
In most cases, for key k, you would be able to add k/253, because of that 52-bit fraction plus the hidden bit.
But it's not necessary to risk triggering library bugs or exploring rounding issues by shooting for the very last bit or anything near it.
So I would say, for colliding key k, just add k / 250 and call it a day.1
1. Possibly more than once until it doesn't collide any more, at least to foil any diabolical unit test authors.
I think you mean "by as small an amount possible to avoid a hash collision", since for example the next-highest-float may already be a key! =)
while toInsert.key in myDict: # assumed to be positive
toInsert.key *= 1.000000000001
myDict[toInsert.key] = toInsert
That said you probably don't want to be using timestamps as keys.
Instead of resolving the collisions by changing the key, how about collecting the collisions? IE:
bag = {}
bag[1234.] = 'something'
becomes
bag = collections.defaultdict(list)
bag[1234.].append('something')
would that work?
Here it part of it. This is dirty and slow, but maybe that is how you like it. It is missing several corner cases, but maybe this gets someone else close.
The idea is to get the hex string of a floating point number. That gives you a string with the mantissa and exponent bits to twiddle. The twiddling is a pain since you have to do all it manually and keep converting to/from strings. Anyway, you add(subtract) 1 to(from) the last digit for positive(negative) numbers. Make sure you carry through to the exponent if you overflow. Negative numbers are a little more tricky to make you don't waste any bits.
def increment(f):
h = f.hex()
# decide if we need to increment up or down
if f > 0:
sign = '+'
inc = 1
else:
sign = '-'
inc = -1
# pull the string apart
h = h.split('0x')[-1]
h,e = h.split('p')
h = ''.join(h.split('.'))
h2 = shift(h, inc)
# increase the exponent if we added a digit
h2 = '%s0x%s.%sp%s' % (sign, h2[0], h2[1:], e)
return float.fromhex(h2)
def shift(s, num):
if not s:
return ''
right = s[-1]
right = int(right, 16) + num
if right > 15:
num = right // 16
right = right%16
elif right < 0:
right = 0
num = -1
else:
num = 0
# drop the leading 0x
right = hex(right)[2:]
return shift(s[:-1], num) + right
a = 1.4e4
print increment(a) - a
a = -1.4e4
print increment(a) - a
a = 1.4
print increment(a) - a
After Looking at Autopopulated's answer I came up with a slightly different answer:
import math, sys
def incrementFloatValue(value):
if value == 0:
return sys.float_info.min
mant, exponent = math.frexp(value)
epsilonAtValue = math.ldexp(1, exponent - sys.float_info.mant_dig)
return math.fsum([value, epsilonAtValue])
Disclaimer: I'm really not as great at maths as I think I am ;) Please verify this is correct before using it. Also I'm not sure about performance
some notes:
epsilonAtValuecalculates how many bits are used for the mantissa (the maximum minus what is used for the exponent).- I'm not sure if the
math.fsum()is needed but hey it doesn't seem to hurt.
It turns out that this is actually quite complicated (maybe why seven people have answered without actually providing an answer yet...).
I think this is the right solution, it certainly seems to handle 0 and positive values correctly:
import math
import sys
def incrementFloat(f):
if f == 0.0:
return sys.float_info.min
m, e = math.frexp(f)
return math.ldexp(m + sys.float_info.epsilon / 2, e)
'developer tip' 카테고리의 다른 글
| PDO를 사용하여 MySQL에서 숫자 유형을 얻는 방법은 무엇입니까? (0) | 2020.11.30 |
|---|---|
| Picturebox에서 스크롤바를 얻는 방법 (0) | 2020.11.30 |
| MKMapView : Annotation Pin 대신 사용자 지정보기 (0) | 2020.11.30 |
| 직접 URL 액세스에서 파일을 방지하는 방법은 무엇입니까? (0) | 2020.11.30 |
| HTML, 자바 스크립트 및 Ajax 요청으로 jQuery를 사용하여 Amazon s3에 이미지 업로드 (PHP 없음) (0) | 2020.11.30 |