python 浮点精度：这个增量能可靠地工作吗？

Question

我使用以下代码动态生成与给定项目列表关联的增量概率的每个组合的字典列表，这样概率总和为 1。例如，如果 increment_divisor 是2（导致 1/2 或 0.5 递增），并且列表包含 3 个项目 ['a', 'b', 'c']，那么函数应该 return

[{'a': 0.5, 'b': 0.5, 'c': 0.0},
 {'a': 0.5, 'b': 0.0, 'c': 0.5},
 {'a': 0.0, 'b': 0.5, 'c': 0.5},
 {'a': 1.0, 'b': 0.0, 'c': 0.0},
 {'a': 0.0, 'b': 1.0, 'c': 0.0},
 {'a': 0.0, 'b': 0.0, 'c': 1.0}]

代码如下。该脚本通过计算 1/x 生成增量器，然后迭代地将增量器添加到 increments 直到值为 >= 1.0。我已经知道 python float 不精确，但我想确保 increments 中的最后一个值非常接近 1.0。

from collections import OrderedDict
from itertools import permutations

def generate_hyp_space(list_of_items, increment_divisor):
    """Generate list of OrderedDicts filling the hypothesis space.

    Each OrderedDict is of the form ...
    { i1: 0.0, i2: 0.1, i3: 0.0, ...}
    ... where .values() sums to 1.

    Arguments:
    list_of_items     -- items that receive prior weights
    increment_divisor -- Increment by 1/increment_divisor. For example,
                         4 yields (0.0, 0.25, 0.5, 0.75, 1.0).
    """
    _LEN = len(list_of_items)
    if increment_divisor < _LEN:  # permutations() returns None if this is True
        print('WARN: increment_divisor too small, so was reset to '
              'len(list_of_items).', file=sys.stderr)
        increment_divisor = _LEN
    increment_size = 1/increment_divisor
    h_space = []
    increments = []
    incremental = 0.0
    while incremental <= 1.0:
        increments.append(incremental)
        incremental += increment_size
    for p in permutations(increments, _LEN):
        if sum(p) == 1.0:
            h_space.append(OrderedDict([(list_of_items[i], p[i])
                                        for i in range(_LEN)]))
    return h_space

在 float 的不精确性破坏脚本的可靠性之前，increment_divisor 可以有多大？（具体来说，while incremental <= 1.0 和 if sum(p) == 1.0）

这是一个小示例，但实际使用将涉及更大的排列 space。有没有更efficient/effective的方法可以实现这个目标？（我已经计划实施缓存。）numpy 数据类型在这里对速度或精度有用吗？

Answer 1

The script generates the incrementer by calculating 1/x and then iteratively adds the incrementer to increments until the value is >= 1.0.

不，不，不。只需将 0 到 x 中的每个整数除以 x:

即可得到 [0/x, 1/x, ..., (x-1)/x, x/x] 的列表

increments = [i/increment_divisor for i in range(increment_divisor+1)]
# or for Python 2
increments = [1.0*i/increment_divisor for i in xrange(increment_divisor+1)]

无论发生什么舍入错误，列表的元素数量总是正确的。

对于 NumPy，这将是 numpy.linspace:

increments = numpy.linspace(start=0, stop=1, num=increment_divisor+1)

至于你的整体问题，在浮动中工作可能是个坏主意。你应该能够用整数完成整个事情并且最后只除以 increment_divisor，所以你不必处理 sum(p) == 1.0 中的浮点精度问题。此外，itertools.permutations 不会执行您想要的操作，因为它不允许相同排列中的重复项。

您应该使用基于 stars and bars 想法的算法来生成所有可能的方法，以在 increment_divisor 结果之间放置 len(list_of_items) - 1 分隔符，而不是完全过滤排列概率指令的位置。

Answer 2

感谢@user2357112...

...指出使用 ints 直到最后一步的方法。
...指引我前往星星和酒吧的方法。

我将 stars_and_bars 作为生成器实现如下：

def stars_and_bars(n, k, the_list=[]):
    """Distribute n probability tokens among k endings.

    Generator implementation of the stars-and-bars algorithm.

    Arguments:
    n   --  number of probability tokens (stars)
    k   --  number of endings/bins       (bars+1)
    """
    if n == 0:
        yield the_list + [0]*k
    elif k == 1:
        yield the_list + [n]
    else:
        for i in range(n+1):
            yield from stars_and_bars(n-i, k-1, the_list+[i])

python 浮点精度：这个增量能可靠地工作吗？

python float precision: will this increment work reliably?

python

precision

numpy