将Python浮点值增加最小可能量

Question

如何在Python中以最小可能的增量递增浮点数?

---

背景：我将浮点数用作字典键。

偶尔会出现碰撞，我希望通过以尽可能小的量递增浮点数来解决这些碰撞。如何实现？

在C语言中，我会操作曼特尼斯位来实现这一点，但我认为在Python中不可能这样做。

- James

---

由于这个问题上的活动量非常大，当将其他“Python中下一个浮点数值”问题链接/关闭时，它似乎是规范的“重复”的问题。然而，它存在至少两个不同的方面：（1）如何递增浮点值，以及（2）如何在使用浮点数作为字典键时避免冲突。可以在这里找到标题问题的明确陈述和更确定的答案。 - John Y

Answer 1

自Python 3.9起，标准库中有math.nextafter。阅读以下内容以了解旧版本Python的替代方法。 nextafter(x,y)函数返回在方向y上接近x的下一个离散不同的可表示浮点值。 nextafter()函数保证在该平台上正常工作或者返回合理值以指示下一个值不可能存在。 nextafter()函数是POSIX和ISO C99标准的一部分，并且在Visual C中为_nextafter()。符合C99标准的数学库，Visual C，C ++，Boost和Java都实现了IEEE推荐的nextafter()函数或方法。（老实说，我不知道.NET是否有nextafter()。 Microsoft并不太关注C99或POSIX。）

这里的位操作函数都无法完全或正确地处理边缘情况，例如数值经过0.0、负0.0、次标准数、无穷大、负数、溢出或下溢等。如果您需要正确的位操作，这里有一个C语言中nextafter()的参考实现可以为您提供思路。

在Python < 3.9中，有两个可靠的解决方案来获取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

直接链接到系统数学动态链接库：

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的解决方案是最简单的。

- user648852

---

谢谢你作为第一个真正回答这个问题的人。 - A. Rex

Pythonжњ‰Decimal.next_plus()е‡Ңж•°пәЊз”Ёжі•з±»дәәдғҺJavaзљ„Math.nextUp()е‡Ңж•°гЂ‚иҮ¦жѓ…иҮ·еЏ‚иЂѓиү™дёҒstackoverflowй“ңжҺӨпәљhttps://dev59.com/questions/5lbTa4cB1Zd3GeqP-3V2#5756149 - jfs

一个未讨论的边界情况是：如何想出比 x 更大的一些数来提供给 nextafter 函数。假设您总是提供 x + 1 作为 y 参数；如果 x 非常接近最大可能值，这将给您带来错误的答案。也许更方便的方法是考虑 nextafter 的 y 参数的符号，以指示所需的是增量还是减量。 - wberry

@wberry 对于 y，使用 +inf 或 -inf 怎么样？ - user1220978

你可能会发现这很有用。from _testcapi import DBL_MAX，DBL_MIN，FLT_MAX，FLT_MIN - JohnMudd

Answer 2

Python 3.9及以上版本

从Python 3.9开始，发布于2020年10月5日，您可以使用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()。

与math.copysign(math.inf, x)相比，更简单的替代方法是直接使用2*x。

- gerrit

---

更简单地移开零点，可以使用 math.nextafter(x, 2*x)。 - Simply Beautiful Art

@SimplyBeautifulArt 确实。即使在 2*x == inf 的情况下也适用。 - gerrit

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

- S.Lott

---

我知道各种花式多阶段哈希技术，但在这种情况下，我想做一些快速且简单的事情，我知道这将足够。 - James

@Autopulated，如果已经发生冲突，可能会有大于当前时间的键！ - Mark Ransom

是的，所以我的计时器需要返回相同的值三次。我不知道你的电脑有多快，但我关心的那些电脑远远没有那么快。 - James

@Autopulated，你还没有告诉我们你要插入的事件的性质，所以我不知道每个时刻获得超过两个事件的可能性有多大。此外，请注意，有些计时器并不像它们的精度所建议的那样经常计数。三次连续不是唯一触发此问题的方法，你也可能在下一个时刻有两个事件，然后再跟着两个事件。 - Mark Ransom

抱歉，对于除0以外的所有值，[0.5,1)都适用。但这仍意味着将epsilon除以2（[0,0.5)则意味着将其除以4）。 - James

Answer 4

暂且不考虑为什么我们想要增加浮点数值，我认为Autopulated的回答可能是正确的。

但对于问题领域而言，我和大多数回答者一样对将浮点数用作字典键的想法表示疑虑。如果使用Decimal（正如主要评论中所提出的）存在“重量级”解决方案的反对意见，我建议您自己妥协：找出时间戳的实际分辨率，选择足够覆盖它的数字位数，然后将所有时间戳乘以必要的倍数，以便您可以使用整数作为键。如果您负担得起超出计时器精度的额外一两个数字，则可以更有信心地确保没有或减少碰撞，并且如果存在碰撞，则只需添加1（而不是一些繁琐的操作来查找下一个浮点值）。

- John Y

Answer 5

不要对值进行递增，而是对冲突的键使用元组。如果您需要保持它们的顺序，则每个键都应该是一个元组，而不仅仅是重复项。

- Mark Ransom

---

任何一个浮点数都比任何一个元组小。4.0 < () --> True - kindall

@kindall，谢谢！我喜欢这个网站的一件事情是你自己的答案能够教给你一些新东西。 - Mark Ransom

@Adam，好像有些人发现了我的错误并撤回了他们的投票。我在坏的例子中加了<strike>标签，但只在IE上显示，所以我的编辑使答案变得非常混乱。现在应该解决了。 - Mark Ransom

在Python 2中，不兼容的类型可以进行排序，但在Python 3中则无法。如果你在一个浮点数和一个元组之间使用 < 运算符，会得到一个 TypeError 错误。 - bignose

@kindall，在Python 3中，浮点数和元组不能直接进行比较。TypeError: unorderable types: float() < tuple() - Brian Minton

是的，这是真的。正如在你上面发表2.5年前的评论中指出的那样。 - kindall

Answer 6

如果可能的话，我建议不要假定浮点数（或时间戳）是唯一的。使用计数迭代器、数据库序列或其他服务来发行唯一标识符。

- wberry

---

我并不假设它们会是唯一的，这就是为什么我提出了这个问题！不过，我假设碰撞非常罕见。 - James

“我假设碰撞很少发生”和假设它们从不发生一样糟糕。找一个更好的关键词。 - S.Lott

不会发生碰撞的情况非常少。我知道我的计时器的行为方式，也知道何时向我的字典中添加了东西：很少的哈希碰撞是完全可以接受的。 - James

Answer 7

更好的答案（现在我只是为了好玩而这样做...），灵感来自于对位操作的调整。处理负值数字各部分之间的进位和溢出有些棘手。

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!')

- James

---

我喜欢这个，尽管一开始我并不理解它。（我阅读了http://docs.python.org/library/struct.html现在更好地理解它了。）唯一让我不太满意的是函数命名。;) - James Khoury

这就是我来这里发布的内容。这是最简单、最健壮和可证明正确的答案。当然，如果在Inf处发生碰撞，你会绕回来... - Gabe

这实际上也是Mark Dickinson在这里的答案。 - John Y

这里有一个支持负浮点数的解决方案版本：https://dev59.com/p2kv5IYBdhLWcg3wsCzi#10426033 - jfs

Answer 8

不要通过更改键来解决冲突，那么如何收集冲突呢？例如：

bag = {}
bag[1234.] = 'something'

变成

bag = collections.defaultdict(list)
bag[1234.].append('something')

这个可以吗？

- SingleNegationElimination

Answer 9

对于冲突键k，添加：k / 2 ⁵⁰

---

有趣的问题。您需要添加的数量显然取决于冲突值的大小，以便规范化添加仅影响最不重要的位。

没有必要确定可以添加的最小值。所有你需要做的就是近似它。FPU格式提供52个尾数位加上一个隐藏位，共53位精度。没有任何物理常数达到这种精度水平。没有传感器能够测量到任何接近它的东西。因此，您没有遇到困难的问题。

在大多数情况下，对于键k，您将能够添加k/2⁵³,由于52位小数加上隐藏位。

但是，没有必要为了追求最后一位或靠近它的任何内容而冒险触发库错误或探索舍入问题。

因此，我会说，对于冲突键k，只需添加k / 2 ⁵⁰并完成。

¹

---

^{1.可能需要多次添加，直到不再发生冲突，至少为了破坏任何恶毒的单元测试作者。}

- DigitalRoss

---

哦，对于零，你可以做些不同的事情，因为可以基于double值的范围（而不是精度）使用数量大大更小的值。添加类似于1 / 2 ** 1020.的内容。 - DigitalRoss

Answer 10

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

- Adam Byrtek

---

如果你将这个数字加到4.0上，你会得到一个完全相同的值！ - James

我认为适当的用法应该是 x+=x*sys.float_info.epsilon。 - Mark Ransom

sys.float_info.epsilon被定义为“1.0和下一个可表示的最大值之间的最小差”，因此相对于其他值来说不安全。 - martineau

没问题，最小差异取决于指数大小。 - Adam Byrtek

@Mark是正确的，这看起来对大/小浮点数很健壮。另外，在版本<2.6中没有任何float_info的情况下，您可以定义epsilon = 2 * pow(2，-53)。 - Mike T