Я использую значения с плавающей запятой в качестве словарных клавиш.
Иногда, очень иногда (и, возможно, никогда, но не обязательно никогда), будут столкновения. Я бы хотел их решить, увеличив значение с плавающей запятой как можно меньше. Как я могу это сделать?
В C я бы покрутил биты мантиссы, чтобы достичь этого, но я предполагаю, что это невозможно в python.
Приращение плавающей запятой python значение на минимально возможное количество
Ты не сумасшедший, и ты должен это сделать. Это, к сожалению, текущий недостаток математической библиотеки Python, как в Python 2.X, так и в Python3000. В Python должен быть math.nextafter(x,y), но его нет. Было бы тривиально добавить, поскольку большинство компиляторов C имеют свои функции.
Функции nextafter (x, y) возвращают следующее дискретно другое представляемое значение с плавающей запятой, следующее за x в направлении y. Функции nextafter() гарантированно работают на платформе или возвращают разумное значение, чтобы указать, что следующее значение невозможно.
Функции nextafter() являются частью POSIX и ISO C99 и _ nextafter() в Visual C. Стандартные математические библиотеки, совместимые с C99, Visual C, С++, Boost и Java реализуют IEEE, рекомендованные nextafter() функциями или методами. (Я честно не знаю, имеет ли .NET последующую(). Microsoft не очень заботится о C99 или POSIX.)
Так как Python, похоже, движется в направлении поддержки большинства математических функций и поведения C99 для математического модуля, любопытство исключает nextafter(). К счастью, есть легкие обходные пути.
Нет функций бит-скручивания здесь полностью или правильно обрабатывать случаи краев, например, значения, равные 0.0, отрицательные 0,0, субнормальные значения, бесконечности, отрицательные значения, превышение или недополнение и т.д. Вот эталонная реализация nextafter() в C, чтобы дать представление о том, как сделать правильное сверление бит, если это ваше направление.
В Python есть две сплошных работы, чтобы получить nextafter() или другие исключенные математические функции 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
И если вам действительно нужно чистое решение Python:
# 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)
Или воспользуйтесь отличным
от Марка Дикинсона.Очевидно, что решение 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
Insead приращения значения, просто используйте кортеж для встречного ключа. Если вам нужно держать их в порядке, каждый ключ должен быть кортежем, а не только дубликатами.
import sys
>>> sys.float_info.epsilon
2.220446049250313e-16
Я рекомендую не предполагать, что поплавки (или временные метки) будут уникальными, если это вообще возможно. Используйте счетный итератор, последовательность базы данных или другую службу для выдачи уникальных идентификаторов.
Забыв о том, почему мы хотели бы на мгновение увеличить значение с плавающей запятой, я должен сказать, что, по-моему, аутопульмированный собственный ответ правильный.
Но для проблемной области я разделяю опасения большинства респондентов относительно идеи использования float в качестве словарных ключей. Если возражение на использование Decimal (как предлагается в основных комментариях) заключается в том, что это "тяжеловесное" решение, я предлагаю сделать сам по себе компромисс: выяснить, какое практическое разрешение находится на отметках времени, выбрать несколько цифр для адекватного покрытия, затем умножить все временные метки на необходимую сумму, чтобы вы могли использовать целые числа в качестве ключей. Если вы можете позволить себе дополнительную цифру или две за пределами точности таймера, то вы можете быть еще увереннее, что не будет или меньше столкновений, и что если есть столкновения, вы можете просто добавить 1 (вместо некоторого rigamarole, чтобы найти следующее значение с плавающей запятой).
Лучший ответ (теперь я просто делаю это для удовольствия...), мотивированный разворачиванием бит. Обработка переноса и переполнения между частями числа отрицательных значений несколько сложна.
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 вы можете использовать:
В то время как 2.1 (случайный int из большого диапазона) отлично работает для ethernet, я бы использовал 2.2 (serializer) или 2.3 (UUID). Легкий, быстрый, пуленепробиваемый. Для 2.2 и 2.3 вам даже не требуется обнаружение столкновения (вы, возможно, захотите еще иметь его для 2.1, как это делает ethernet.)
Преимущество 2.2 заключается в том, что вы также можете определять и сортировать элементы данных, имеющие одну и ту же метку времени всплытия.
Затем просто извлеките x из кортежа для любых операций типа сортировки, а сам кортеж - это бесплатный ключ для хеша/словаря.
Edit
Я думаю, что пример кода поможет:
#!/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...
Интересная проблема. Количество, которое нужно добавить, очевидно, зависит от величины встречного значения, так что нормализованная добавка влияет только на младшие значащие биты.
Не нужно определять наименьшее значение, которое можно добавить. Все, что вам нужно сделать, это приблизительное. Формат FPU обеспечивает 52 бит мантиссы плюс скрытый бит для 53 бит точности. Ни одна физическая константа не известна нигде вблизи этого уровня точности. Никакой датчик не может измерить что-либо рядом с ним. Таким образом, у вас нет тяжелой проблемы.
В большинстве случаев для ключа k вы можете добавить k/2 53 из-за этой 52-битной дро + плюс скрытый бит.
Но не обязательно рисковать запуском ошибок библиотек или изучением проблем округления, снимая последний бит или что-нибудь рядом с ним.
1. Возможно, более одного раза, пока он не столкнется больше, по крайней мере, чтобы сорвать любые дьявольские авторы unit test.
Я думаю, вы имеете в виду "как можно меньше шансов избежать столкновения хэшей", поскольку, например, следующий-самый высокий поплавок уже может быть ключом! =)
while toInsert.key in myDict: # assumed to be positive
toInsert.key *= 1.000000000001
myDict[toInsert.key] = toInsert
Это говорит о том, что вы, вероятно, не хотите использовать временные метки в качестве ключей.
Вместо того, чтобы разрешать столкновения, изменяя ключ, как насчет сбора столкновений? IE:
bag = {}
bag[1234.] = 'something'
становится
bag = collections.defaultdict(list)
bag[1234.].append('something')
будет работать?
Вот его часть. Это грязно и медленно, но, возможно, так оно и есть. В нем отсутствует несколько угловых случаев, но, возможно, это закрывает кого-то другого.
Идея состоит в том, чтобы получить шестнадцатеричную строку числа с плавающей запятой. Это дает вам строку с мантиссой и битами экспоненты. Скручивание - это боль, потому что вы должны сделать все это вручную и продолжать конвертировать в/из строк. Во всяком случае, вы добавляете (вычитаете) 1 в (от) последнюю цифру для положительных (отрицательных) чисел. Убедитесь, что вы переносите экспонента, если вы переполняете. Отрицательные числа немного сложнее сделать, чтобы вы не теряли никаких бит.
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
После просмотра автопопуляционного ответа я придумал немного другой ответ:
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])
Отказ от ответственности: я действительно не так хорош в математике, как мне кажется.) Пожалуйста, убедитесь, что это правильно, прежде чем использовать его. Также я не уверен в производительности
некоторые примечания:
epsilonAtValue вычисляет, сколько бит используется для мантиссы (максимум минус, что используется для экспоненты).math.fsum(), но, похоже, это не повредит.Оказывается, это на самом деле довольно сложно (может быть, почему семь человек ответили, фактически не дав ответа...).
Я думаю, что это правильное решение, оно, по-видимому, верно обрабатывает 0 и положительные значения:
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)