以尽可能最小的量增加一个python浮点值
我使用浮点值作为字典键。
有时偶尔（也许永远也不会永远）会有碰撞。 我想通过尽可能less地增加浮点值来解决这些问题。 我该怎么做？
在C中，我会旋转尾数来实现这一点，但我认为这是不可能在Python中。
以尽可能最小的量增加一个python浮点值
你不疯狂，你应该能够做到这一点。 这是Pythonmath库的一个缺点，不幸的是，在Python 2.X和Python3000中。 Python中应该有一个math.nextafter(x,y) ，但是没有。 由于大多数C编译器都具有这些function，所以添加起来并不重要。
nextafter（x，y）函数以y的方向返回下一个离散的不同的可表示的浮点值。 nextafter（）函数保证在平台上工作，或者返回一个合理的值来表示下一个值是不可能的。
nextafter()函数是POSIX和ISO C99标准的一部分， 在Visual C中是_nextafter（） 。 C99标准math库，Visual C，C ++，Boost和Java都实现了IEEE推荐的nextafter（）函数或方法。 （我并不真正知道.NET是否有nextafter（），微软并不太在乎C99或POSIX。）
由于Python似乎正朝着支持math模块的大部分C99math函数和行为的方向前进， nextafter()的排除是令人好奇的。 幸运的是有简单的解决方法。
这里没有任何一点点处理函数完全或正确地处理边界情况，例如经过0.0，负0.0，低于正常值，无穷大，负值，溢出或下溢等的值。 这里是C中nextafter（）的参考实现如果这是你的方向，那么怎么做正确的位置呢？
在Python中获得nextafter()或其他排除的POSIXmath函数有两个实际的工作：
使用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
直接链接到系统mathDLL：
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解决scheme：
# 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)
或者，使用马克·迪金森的出色解决scheme
显然Numpy解决scheme是最简单的。
首先，这个“应对碰撞”是一个非常糟糕的主意。
如果碰撞，字典中的值应该是具有公共密钥的项目列表，而不是单个项目。
您的“散列探测”algorithm将不得不循环多个“微小增量”来解决冲突。
并且顺序散列探测器被认为是低效的。
阅读： 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
我build议不要假设浮动（或时间戳）将是唯一的，如果可能的话。 使用计数迭代器，数据库序列或其他服务来发出唯一标识符。
增加值的缺省值，只需使用一个元组作为碰撞键。 如果你需要保持它们的顺序，每个键都应该是一个元组，而不仅仅是副本。
忘了为什么我们想暂时增加一个浮点值，我不得不说我认为Autopulated自己的答案可能是正确的。
但对于问题领域，我分享了大多数响应者对使用浮点数作为字典键的想法的疑虑。 如果反对使用十进制（正如主要评论中提出的），那就是它是一个“重量级”的解决scheme，我build议做一个自己动手的折衷scheme：找出时间戳上的实际分辨率，挑选一些数字充分覆盖它，然后将所有时间戳乘以必要的数量，以便您可以使用整数作为键。 如果你能够承受超过定时器精度的一两位数，那么你可以更加确信碰撞没有或者更less，而且如果碰撞，你可以加1（而不是一些rigamarole来find下一个浮点值）。
一个更好的答案（现在我只是为了好玩而做这个…），这是为了扭转局面。 处理多个负值部分之间的进位和溢出有点棘手。
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 Ransombuild议元组(x,y)由x=your_unmodified_time_stamp和y=(extremely unlikely to be a same value twice)组成，而不是修改浮点时间戳。
所以：
-
x就是未修改的时间戳，可以是多次相同的值; - 你可以使用：
- 一个大范围的随机整数，
- 串行整数（0,1,2等），
- UUID 。
虽然2.1（从大范围的随机int）那里工作伟大的以太网，我会使用2.2（串行器）或2.3（UUID）。 简单，快速，防弹。 对于2.2和2.3，你甚至不需要碰撞检测（你可能想要像以太网一样使用2.1）。
2.2的好处是你也可以告诉并sorting具有相同浮点时间戳的数据元素。
然后，从元组中为任何sortingtypes操作提取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
有趣的问题。 您需要添加的数量显然取决于碰撞值的大小，因此标准化的添加只会影响最低有效位。
没有必要确定可以添加的最小值。 所有你需要做的是近似的。 FPU格式提供了52个尾数位加上一个53位精度的隐藏位。 在这个精度水平附近没有任何物理常数是已知的。 没有传感器可以测量任何附近的东西。 所以你没有一个难题。
在大多数情况下，对于关键字k ，由于52位分数加上隐藏位，您可以添加k / 2 53 。
但是没有必要冒着触发图书馆漏洞或者通过拍摄最后一点或任何附近的东西来探索四舍五入问题的风险。
所以我想说，为了碰撞关键字k ，只需加上k / 2 50就可以了。 1
1.可能不止一次，直到它不再相互碰撞，至less为任何恶魔的unit testing作者。
我认为你的意思是“尽可能less地避免哈希碰撞”，因为例如下一个最高的浮点可能已经是一个关键！ =）
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')
那会工作吗？
这是它的一部分。 这是肮脏和缓慢，但也许这就是你喜欢它。 这是缺less几个angular落的情况下，但也许这让别人closures。
这个想法是得到一个浮点数的hexstring。 这给你一个string尾数和指数位twiddle。 由于您必须手动完成所有操作，并不断转换为string，所以这种混乱是件痛苦的事情。 无论如何，你加（减）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
看着Autopopulated的答案后，我想出了一个稍微不同的答案：
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])
免责声明：我的math真的不像我想象的那样伟大;）请在使用之前确认这是正确的。 另外我不确定performance
一些说明：
-
epsilonAtValue计算尾数使用的位数（最大减去指数所用的位数）。 - 我不确定是否需要
math.fsum()，但嘿它似乎并没有受到伤害。
事实certificate，这实际上是相当复杂的（也许为什么七个人已经回答，却没有真正提供答案呢…）。
我认为这是正确的解决scheme，它似乎正确地处理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)
