Равномерно расставить n элементов в течение m итераций

Question

Для контекста это означает одновременное управление несколькими шаговыми двигателями в высокоточном приложении.

Постановка задачи
Скажем, у меня есть цикл, который будет запускать i итераций. В течение этих итераций выражение E_x должно оцениваться до true x раз (x <= i гарантировано).

Требования
- E_x должен оценить true точно x раз
- E_x должно оцениваться до true с более или менее равномерно распределенными интервалами *

* «равномерно распределенные интервалы» означает, что максимальный размер интервала сведен к минимуму

Примеры
Для: i = 10, x = 7
E_x будет верно для итераций, помеченных 1: 1101101101

Для: i = 10, x = 3
E_x будет верно для итераций, помеченных 1: 0010010010

Для: i = 10, x = 2
E_x будет верно для итераций, помеченных 1: 0001000100

Каков наилучший (или даже "хороший") способ E_x оценить до true с равномерно распределенными интервалами, гарантируя, что это верно ровно x раз?

Этот вопрос близок к моему, однако предполагается, что E_x всегда будет оценивать до true на 1-й и последней итерациях, что не соответствует моим требованиям (см. 2-й пример выше).

Answer 1

Если вы хотите сделать x шаг за n итераций, вы можете сделать это следующим образом:

int incCount = 0;
int iterCount = 0;

boolean step() {
    ++iterCount;
    int nextCount = (iterCount*x + n/2) / n; // this is rounding division
    if (nextCount > incCount) {
        ++incCount;
        return true;
    }
    else {
        return false;
    }
}

Это простой для понимания способ. Если у вас встроенный процессор, где деление дороже, вы можете выполнить ровно так же, как это:

int accum = n/2;

boolean step() {
    accum+=x;
    if (accum >= n) {
        accum-=n;
        return true;
    }
    else {
        return false;
    }
}

Общая сумма, добавленная к accum здесь, равна iterCount*x + n/2, как и в первом примере, но деление заменяется пошаговым повторным вычитанием. Именно так работает алгоритм рисования линий Брезенхэма.

Answer 2

Я буду использовать немного другое соглашение об именах: давайте сгенерируем T интервалы [1..T] и N событий. Также давайте решим проблему как циклическую. Для этого давайте добавим один поддельный шаг в конце, в котором мы гарантированно инициируем событие (и это также будет событие в момент времени 0, т.е. перед циклом). Так что мой T - это ваш i+1, а мой N - ваш x+1.

Если вы поделите T на N с напоминанием, вы получите T = w*N + r. Если r=0, случай тривиален. Если r != 0 лучшее, что вы можете достичь, это r интервалы размера w+1 и (N-r) интервалы размера w. Быстрое и простое, но достаточно хорошее решение будет примерно таким (псевдокод):

events = []
w = T / N
r = T % N
current = 0
for(i = 1; i<=N; i++) {
   current += w;
   if (i <= r)
      current += 1;
   events[i] = current;
}

Вы можете видеть, что последнее значение в массиве будет T, как было обещано нашим повторным утверждением как циклическая проблема. Это будет T, потому что в течение цикла мы добавим w к current N раз и добавим r раз 1, поэтому сумма будет w*N+r, что составляет T.

Основным недостатком этого решения является то, что все «длинные» интервалы будут в начале, а все «короткие» интервалы будут в конце.

Вы можете распределять интервалы более равномерно, если вы немного умнее. И результирующая логика будет по существу такой же, как и за алгоритмом линии Брезенхема , на который есть ссылки в комментариях. Представьте, что вы рисуете линию на плоскости, где X -ось представляет время, а Y -ось представляет события, от (0,0) (то есть 0 -ое событие до вашего таймфрейма) до (i+1, x+1) (это x+1 -ое событие, сразу после вашего таймфрейма). Момент для инициирования события - это когда вы переключаетесь на следующий Y, то есть рисуете первый пиксель в данном Y.