Алгоритм для петли над массивом из середины наружу?

Я работаю над алгоритмом "разделяй и властвуй" (на самом деле, тот, который наводит кривые на несколько входных точек). Для части "divide" мне нужно рассчитать коэффициент ошибки для каждой точки, и если ошибка превышает заданный порог, я хочу разбить кривую в этой точке и обработать левый и правый участки входа отдельно. Простая петля делает трюк; но мне было бы полезно начать в середине текущего раздела и работать наружу. (Чтобы уточнить: если я нахожу точку, чья ошибка слишком велика, я рекурсивно вызываю и генерирую отдельные кривые для левого и правого секций - если все точки находятся в пределах порога, тогда моя кривая подходит и я возвращаюсь).

После небольшого поцарапания головы я придумал это (точки находятся в массиве, а текущий раздел от startIndex до endIndex включительно):

int steps = (endIndex+1-startIndex);
int i = (startIndex+endIndex)>>1;
int stepdir = 1;
for(int q=0; q<steps; q++, i+=stepdir*q, stepdir=-stepdir)
{
   // test point i here and return early if error exceeds threshold
}

Другими словами, начиная с середины, пройдите один указатель вперед, два назад, три вперед, четыре назад... Это работает, и я уверен, что он эффективен, но мне кажется, что должен быть более чистый способ для этого, в частности, мне пришлось проверить спецификацию языка Java, чтобы убедиться, что операторы в выражении for update действительно оценивали последовательно (хотя это не оператор последовательности, как в C/С++).

Любые идеи с благодарностью оценили. Есть ли более чистый способ?

Ответы

Ответ 1

Это было бы более читаемым imho

for (int q=0; q < steps; q++) {

   int index = i + ( q% 2 == 0 ? q/2 : -(q/2+1)); //index lookup here
}

Изменить: реализована ошибка в поиске индекса

Ответ 2

Если ваш избыточный контролер ошибок прост (например, вызов функции), самая ясная вещь - написать:

int mid = npoints / 2;
for (int i = 0; i <= mid; i++) {
     if( excess_error(mid + i + 1) ) {
          // divide at mid + i + 1
     } else if excess_error(mid - i) {
          // divide at mid - i
     }
}

Снова код "divide at xyz" должен быть вызовом функции, или вы получаете вырезанный и вставленный код.

(Я не очень тщательно думал об угловых случаях и ошибках "один за другим", поэтому будьте осторожны, когда я == mid, но вы получите изображение.)

Ответ 3

Здесь более общее решение для тех, кому нужно искать наружу из произвольной точки (в этом примере ячейка [6] в массиве длиной 7).

int arraySize = 7;
int start = 6;

for (int i=0; i < arraySize; i++) {
   int index = (start+((i%2==0)?i/2:arraySize-(i+1)/2))%arraySize;
   print(index+",");
}
exit();

Печатает 6,5,0,4,1,3,2,