Algoritma, ortadan dışa doğru bir dizi üzerinden mi geçecek?

Question

Ben bir böl ve yönet algoritması üzerinde çalışıyorum (aslında, bir dizi giriş noktasına eğri uydurma yapan). 'Böl' kısmı için, her nokta için bir hata teriminin hesaplanması gerekiyor ve eğer hata belirli bir eşiği aşarsa, eğriyi o noktada bölmek ve girişin sol ve sağ bölümlerini ayrı ayrı işlemek istiyorum. Basit bir döngü hile yapar; ama şu anki bölümün ortasında başlamam ve dışarıdan çalışmak benim için avantajlı olurdu. (Netleştirmek gerekirse: hatası çok büyük olan bir noktayı bulursam, yinelemeli olarak sol ve sağ bölümler için ayrı eğriler ararım ve üretirim - eğer tüm noktalar eşiğin içindeyse, benim eğrime uyuyor ve dönüyorum). yakın başlayarak diğer bir deyişle

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 
} 

: Baş-çizilmemesi biraz sonra

, ben (noktalar bir dizi vardır ve mevcut bölüm startIndex gelen kapsayıcı endIndex etmektir) bu geldi Orta, bir endeks ileri, iki geri, üç ileri, dört geri ... Çalışır, ve eminim ki bu verimli, ama bunu yapmak için daha temiz bir yol olmalı, özellikle, ben sona erdi güncelleme dilindeki ifadelerin sırayla değerlendirildiğinden emin olmak için Java dil özelliklerini kontrol etmek zorunda kalmadan (C/C++'da olduğu gibi bir sıra operatörü olmasa bile).

Herhangi bir fikir için minnetle teşekkür ederiz. Daha temiz bir yolu var mı?

Answer 1

Bu

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

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

Düzenleme imho daha okunabilir olacaktır: senin aşırı yanılma denetleyicisi (örneğin bir işlev çağrısı) basitse indeks araması bir hata fark

Answer 2

, en net şey etmektir yazma:

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

Yine "bölmek xyz de" kod bir işlev çağrısı olmalıdır, yoksa & yapıştırılan kod kesilmiş olsun.

(ı köşe durumlarda dikkatle düşünce değil ve ben == orta, ama resmi olsun off-by-tek hataları, bu yüzden dikkatli olun.)

Answer 3

İşte herkes için daha genel bir çözüm Bu, rastgele bir noktadan dışarı doğru arama yapmak zorundadır (bu örnekte, uzunluk 7 dizisinde [6] hücresinde).

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(); 

Baskılar 6,5,0,4,1,3,2,