python - 可变分辨率 Van der Corput 序列

Question

我正在寻求执行 Van der Corput - 类似于范围采样，但具有自定义分辨率。

例如，考虑对范围 [0, 100] 进行采样，分辨率为 25。这需要在 [0, 25, 50, 75, 100]，如果我们遵循类似 Van der Corput 的序列，则类似于:[0, 100, 50, 25, 75]。

Van der Corput 算法的每个“ channel ”迭代地将范围划分为前一 channel 大小的 1/2 段(2 点，然后是 3、5、9、17，.. .).因此，如果我的最小分辨率是 24，那么我将需要 2^n + 1(在本例中为 9)个样本，而不是 ceil(100/24 ) = 5 样本以达到所需的分辨率。

是否有任何方法可以产生我正在寻找的解决方案？

Answer 1

首先，我认为您的序列有一个小缺陷，100 从来都不是该序列的一部分。 Van der Corput 序列应该是0, 50, 25, 75, ...。

如果我们查看数字的二进制分数，Van der Corput 序列 会显示一个有趣的模式。本质上它归结为:

binary    decimal     binary reverse
0.0       0.0           0.0
0.1       0.5           1.0
0.01      0.25         10.0
0.11      0.75         11.0
0.001     0.125       100.0
0.101     0.625       101.0
0.011     0.375       110.0
0.111     0.875       111.0

二进制反转反射(reflect)了“二进制点”上的数字。所以在这里我们看到这实际上只是一个二进制计数器。

我们可以使用该逻辑为给定范围生成序列的第 i 个元素，l 和 u 的整数较低和上限分别为:

def vdc_seq(i, l, u):
    v = 0
    p = 0
    d = u - l
    while i:
        v <<= 1
        if i & 1:
            v += d
        i >>= 1
        p += 1
    if p:
        v += (1 << p-1)
    return l + v >> p

例如:

>>> list(map(partial(vdc_seq, l=0, u=100), range(9)))
[0, 50, 25, 75, 13, 63, 38, 88, 6]

我们可以很容易地在这里使用 float ，通过替换这个:

def vdc_seq(i, l, u):
    v = 0
    p = 1
    d = u - l
    while i:
        v <<= 1
        if i & 1:
            v += d
        i >>= 1
        p <<= 1
    return l + v / p

第 2^k+1-1 个元素的“分辨率”是 2^-k ，因此对于给定的最小分辨率 m，我们可以确定何时停止，并生成如下列表:

from functools import partial

def vdc_seq_list_min(l, u, m):
    n = 2 * (u - l + m - 1) // m - 1
    return map(partial(vdc_seq, l=l, u=u), range(n))

例如:

>>> list(vdc_seq_list_min(0, 100, 24))
[0, 50, 25, 75, 13, 63, 38, 88, 6]
>>> list(vdc_seq_list_min(0, 100, 10))
[0, 50, 25, 75, 13, 63, 38, 88, 6, 56, 31, 81, 19, 69, 44, 94, 3, 53, 28, 78]