Алгоритм обхода массива от середины кнаружи?

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

Немного почесав голову, я пришел к следующему (точки находятся в массиве, а текущий раздел - от 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
}

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

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

10
задан Chris Nash 27 July 2011 в 00:39
поделиться