Algorytm pętli nad tablicą od środka na zewnątrz?

Question

Pracuję nad algorytmem dziel i rządź (w rzeczywistości taki, który dopasowuje krzywą do wielu punktów wejściowych). W przypadku części "dziel", muszę obliczyć termin błędu dla każdego punktu, a jeśli błąd przekracza dany próg, chcę podzielić krzywą w tym punkcie i oddzielnie przetwarzać lewą i prawą sekcję wejścia. Prosta pętla wykonuje lewę; ale byłoby dla mnie korzystne zacząć od środka obecnej sekcji i pracować na zewnątrz. (Aby wyjaśnić: jeśli znajdę punkt, którego błąd jest zbyt duży, rekurencyjnie wywołuję i generuję oddzielne krzywe dla lewej i prawej sekcji - jeśli wszystkie punkty znajdują się w obrębie progu, to moja krzywa pasuje i wracam).

Po nieco głowy drapania, wymyśliłem ten (punkty są w tablicy, a obecna sekcja jest od startIndex do endIndex włącznie):

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 
} 

Innymi słowy, zaczynając w pobliżu w środku, idź jeden indeks do przodu, dwa do tyłu, trzy do przodu, cztery do tyłu ... Działa, i jestem pewien, że jest skuteczny, ale wydaje mi się, że powinien istnieć lepszy sposób na zrobienie tego, w szczególności zakończyłem do sprawdzenia specyfikacji języka Java, aby upewnić się, że instrukcje w wyrażeniu dla aktualizacji dokonały oceny w sekwencji (mimo, że nie jest operatorem sekwencji, jak to jest w C/C++).

Wszelkie pomysły wdzięcznie doceniane. Czy istnieje czystszy sposób?

Answer 1

To byłoby bardziej czytelne imho

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

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

EDIT: zrozumiał błąd w odnośnika indeksu

Answer 2

Jeśli kontroler nadmiar błędów jest prosty (np wywołania funkcji), najczystsze rzeczą jest napisać:

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 
    } 
} 

Znowu „podzielić na xyz” kod powinien być wywołanie funkcji, lub Ci wyciąć & wklejony kod.

(nie myślałem dokładnie o przypadkach narożnych i off-by-one błędów, więc należy być ostrożnym kiedy == połowy, ale pojawi się obraz.)

Answer 3

Oto bardziej ogólne rozwiązanie dla każdego, który musi szukać na zewnątrz z dowolnego punktu (w tym przykładzie komórka [6] w tablicy o długości 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(); 

Drukuje 6,5,0,4,1,3,2,