Последовательность Ван дер Корпута с переменным разрешением - PullRequest
Новая
       24

Последовательность Ван дер Корпута с переменным разрешением

1 голос
/ 28 мая 2019

Я хочу выполнить Van der Corput -подобную выборку диапазона, но с пользовательским разрешением.

В качестве примера рассмотрим выборку диапазона [0, 100],с разрешением 25. Это повлечет за собой выборку в [0, 25, 50, 75, 100], и если мы будем следовать последовательности, подобной Ван-дер-Корпуту, что-то вроде: [0, 100, 50, 25, 75].

Каждый «проход» алгоритма Ван-дер-Корпутаитеративно делит диапазон на отрезки 1/2 размера предыдущего прохода (2 балла, затем 3, 5, 9, 17, ...).Поэтому, если мое минимальное разрешение составляет 24, то для достижения желаемого разрешения мне потребуется 2^n + 1 (в данном случае 9) выборок, а не ceil(100/24) = 5.

Существуют ли какие-либо подходы?что даст решение, которое я ищу?

1 Ответ

2 голосов
/ 29 мая 2019

Прежде всего, я думаю, что ваша последовательность имеет незначительный недостаток, 100 никогда не является частью этой последовательности. Последовательность Ван дер Корпута должна быть 0, 50, 25, 75, ... .

A Последовательность Ван дер Корпута показывает интересную картину, если мы посмотрим на двоичные дроби числа. По сути это сводится к: 

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 -го элемента равно 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]
...