可变分辨率Van der Corput Sequen

Question

我正在寻求对一个范围执行类似Van der Corput的采样，但是要有一个自定义的分辨率。你知道吗

例如，考虑对范围[0, 100]进行采样，分辨率为25。这需要在[0, 25, 50, 75, 100]进行采样，如果我们遵循vandercorput序列，比如：[0, 100, 50, 25, 75]。你知道吗

vandercorput算法的每个“过程”将范围迭代地划分为上一个过程大小的段1/2（2个点，然后是3，5，9，17，…）。因此，如果我的最小分辨率是24，那么我需要2^n + 1（在本例中是9）个样本，而不是ceil(100/24) = 5个样本来获得所需的分辨率。你知道吗

有没有什么方法可以产生我正在寻找的解决方案？你知道吗

Answer 1

首先，我认为您的序列有一个小缺陷，100从来不是该序列的一部分。范德科普特序列应该是0，50，25，75。。。。你知道吗

如果我们看一下这个数的二进制分数，vandercorput序列显示了一个有趣的模式。本质上可以归结为：

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

二进制反转镜像“二进制点”上的数字。所以这里我们看到这实际上只是一个二进制计数器。你知道吗

我们可以使用该逻辑为给定范围生成序列的第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]

通过替换以下内容，我们可以轻松使用浮点：

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-th元素的“分辨率”是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]