以尽可能小的量增加python浮点值

Question

我正在使用浮点值作为字典键.

偶尔,很偶尔(也许永远,但不能肯定从来没有),就会出现冲突.我想通过将浮点值递增尽可能小的数量来解决这些问题.我怎样才能做到这一点？

在C中,我会旋转尾数的位来实现这一点,但我认为在python中是不可能的.

Answer 1

以尽可能小的量增加python浮点值

你并不疯狂,你应该能够做到这一点.遗憾的是,Python数学库目前的缺点是Python 2.X和Python3000.math.nextafter(x,y)Python中应该有一个,但没有.由于大多数C编译器都具有这些功能,因此添加它将是微不足道的.

的函数nextafter(X,Y)的功能在y方向上的返回下一个离散地不同的可表示的浮点值下面的X-.nextafter()函数保证在平台上工作或返回合理的值以指示下一个值是不可能的.

这些nextafter()函数是POSIX和ISO C99标准的一部分,在Visual C中是_nextafter().符合C99标准的数学库,Visual C,C++,Boost和Java都实现了IEEE推荐的nextafter()函数或方法.(我真的不知道.NET是否有nextafter().微软并不关心C99或POSIX.)

由于Python似乎正朝着支持数学模块的大多数C99数学函数和行为的方向发展,因此排除它nextafter()是好奇的.幸运的是,有一些简单的解决方法.

无的比特摆弄功能这里完全或正确处理的边缘的情况下,如值去虽然0.0,负0.0,次归,无穷大,负值,过或者下溢等在这里是在C语言函数nextafter()的参考实施如果那是你的方向,想一想如何做正确的比特.

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

如果你真的想要一个纯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)

或者,使用Mark Dickinson的出色解决方案

显然Numpy解决方案是最简单的.

Answer 2

Python 3.9 及以上

从2020-10-05 发布的Python 3.9 开始，您可以使用该math.nextafter函数：

math.nextafter(x, y)

返回 x 之后朝向 y 的下一个浮点值。

如果 x 等于 y，则返回 y。

例子：

• math.nextafter(x, math.inf) 上升：朝向正无穷大。

• math.nextafter(x, -math.inf) 下降：朝向负无穷大。

• math.nextafter(x, 0.0) 走向零。

• math.nextafter(x, math.copysign(math.inf, x)) 从零开始。

另见math.ulp()。

Answer 3

首先,这种"应对碰撞"是一个非常糟糕的主意.

如果它们发生碰撞,字典中的值应该是具有公共密钥的项目列表,而不是单个项目.

您的"哈希探测"算法将不得不循环通过多个"微小增量"来解决冲突.

并且已知顺序散列探测是低效的.

阅读: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

Answer 4

增加值的内部,只需使用元组作为碰撞键.如果你需要保持它们的顺序,每个键应该是一个元组,而不仅仅是重复.

Answer 5

import sys
>>> sys.float_info.epsilon
2.220446049250313e-16

Answer 6

我建议不要假设浮动(或时间戳)在任何可能的情况下都是唯一的.使用计数迭代器,数据库序列或其他服务来发出唯一标识符.

Answer 7

暂时忘记为什么我们要增加浮点值，我不得不说我认为 Autopulated 自己的答案可能是正确的。

但对于问题域，我和大多数响应者一样对使用浮点数作为字典键的想法抱有疑虑。如果反对使用 Decimal （如主要评论中提出的）是因为它是一个“重量级”解决方案，我建议您自己做妥协：找出时间戳上的实际解决方案，选择一些数字为了充分覆盖它，然后将所有时间戳乘以必要的数量，以便您可以使用整数作为键。如果你能承受超出计时器精度的额外一两位数字，那么你可以更加确信不会有或更少的碰撞，并且如果有碰撞，你可以只加 1（而不是用一些冗长的公式来找到碰撞）下一个浮点值）。