背光空间发生器

Question

我希望有一个生成器函数，它返回一条线，给定一个最小距离k。这很简单，可以用numpy完成，如下所示：

points = np.linspace(start, end, k)

但是，我想将这些点生成为一种“增加分辨率”，因此在从0到1的行上，生成器将产生：

1/2, 1/4, 3/4, 1/8, 3/8, 5/8, ...

同样，这很容易递归（只接受端点并在每一半上调用self），但我想要一个可以实现同样的事情的生成器，而不必从一开始就用所有内容填充数组，并且没有重复点。

最好的方法是什么？

Answer 1

实现此目的的一种方法是使用：

def infinite_linspace():
    den = 2
    while True:
        for i in range(1,den,2):
            yield i/den
        den <<= 1

因此，我们使用从1到den-1（包括）的分子迭代，然后将分母加倍。

然后是前15个数字：

>>> list(islice(infinite_linspace(), 15))
[0.5, 0.25, 0.75, 0.125, 0.375, 0.625, 0.875, 0.0625, 0.1875, 0.3125, 0.4375, 0.5625, 0.6875, 0.8125, 0.9375]
>>> [1/2,1/4,3/4,1/8,3/8,5/8,7/8,1/16,3/16,5/16,7/16,9/16,11/16,13/16,15/16]
[0.5, 0.25, 0.75, 0.125, 0.375, 0.625, 0.875, 0.0625, 0.1875, 0.3125, 0.4375, 0.5625, 0.6875, 0.8125, 0.9375]

我们甚至可以将更多智能放入其中以获得相对较快的第i个元素：

class Linspace:

    def __iter__(self):
        den = 2
        while True:
            for i in range(1,den,2):
                yield i/den
            den <<= 1

    def __getitem__(self, idx):
        if not isinstance(idx, int):
            raise TypeError('idx should be an integer')
        if idx < 0:
            raise ValueError('idx should be positive')
        den = denn = idx+1
        denn |= den >> 1
        while den != denn:
            den = denn
            denn |= denn >> 1
        denn += 1
        return (2*idx+3-denn)/denn

所以现在我们可以在对数时间访问例如第10,15和123'456元素：

>>> l = Linspace()
>>> l[9]
0.3125
>>> l[14]
0.9375
>>> l[123455]
0.8837966918945312

Answer 2

这是一种直接计算第i个元素的较短的伪O（1）方法：

def jumpy(i):
    i = (i<<1) + 3
    return i / (1<<i.bit_length()-1) - 1

list(map(jumpy, range(15)))
# [0.5, 0.25, 0.75, 0.125, 0.375, 0.625, 0.875, 0.0625, 0.1875, 0.3125, 0.4375, 0.5625, 0.6875, 0.8125, 0.9375]