C dizisini n eşit parçalara ayırma

Question

Bir diziyi, başlangıç ​​ve bitiş indislerini hesaplayarak n eşit parçalarına ayırmaya çalışıyorum. Başlangıç ​​ve bitiş öğelerinin adresi, bu dizileri sıralayacak bir işleve geçirilecektir. Örneğin, eğer arraySize = 1000 ve n = 2 ise, endeksler 0, 499, 999 olacaktır. Şimdiye kadar aşağıdaki kodlarım var ama tek n için, n dizisinden daha fazlasına bölüyor. Bunu yapmayı düşündüğüm başka bir yol da döngüde n kere koşmaktır, ama nereden başlayacağımı bilmiyorum.

int chunkSize = arraySize/numThreads; 
    for (int start = 0; start < arraySize; start += chunkSize) { 
     int end = start + chunkSize - 1; 
     if (end > arraySize - 1) { 
      end = arraySize - 1; 
     } 

     InsertionSort(&array[start], end - start + 1); 
    } 

DÜZENLEME: Burada ile geldi başka bir şey. Çalışıyor gibi görünüyor, ama daha kapsamlı bir test yapmam gerekiyor. Bunu çok kez çizdim ve el ile takip ettim. Umarım, başarısız olacak herhangi bir kenar durumu yoktur. Zaten n> = arraySize'yi kısıtlıyorum.

int chunkSize = arraySize/numThreads; 
for (int i = 0; i < numThreads; i++) { 
    int start = i * chunkSize; 
    int end = start + chunkSize - 1; 
    if (i == numThreads - 1) { 
     end = arraySize - 1; 
    } 

    for (int i = start; i <= end; i++) { 
     printf("%d ", array[i]); 
    } 
     printf("\n"); 
} 

Answer 1

Öğe büyüklüğünü, aşağı doğru değil "yuvarlatılmış" olacak şekilde hesaplamanız gerekir.

int chunkSize = arraySize/numThreads; 
if (chunkSize * numThreads < arraySize) { 
    // In case arraySize is not exactly divisible by numThreads, 
    // we now end up with one extra smaller chunk at the end. 
    // Fix this by increseing chunkSize by one byte, 
    // so we'll end up with numThread chunks and smaller last chunk. 
    ++chunkSize; 
} 

Answer 2

ben bu yardımcı olacağını umut:

int chunkSize = arraySize/numThreads; 
    for (int i = 0; i < numThreads-1; i++) { 
     start = i* chunkSize; 
     end = start + chunkSize - 1; 
     InsertionSort(&array[start], end + 1); 
    } 
    //Last chunk with all the remaining content 
    start = end + 1; 
    end = arraySize - 1; 
    InsertionSort(&array[start], end + 1); 

Answer 3

ile asgari yığın boyutunu hesaplayın Bunu % operatör ve daha karmaşık bir formül kullanılarak, ama sadece if anlamak muhtemelen daha kolay basit kullanarak yapabileceği kısaltma bölümü. Sonra kalanını hesaplayın. Bazı parçalar 1 eklenerek bu kalan dağıtma:

Sözde kodu:

Örneğin

chunk_size = array_size/N 
bonus = array_size - chunk_size * N // i.e. remainder 

for (start = 0, end = chunk_size; 
    start < array_size; 
    start = end, end = start + chunk_size) 
{ 
    if (bonus) { 
    end++; 
    bonus--; 
    } 

    /* do something with array slice over [start, end) interval */ 
} 

ARRAY_SIZE 11 ve N == 4 ise, 11/K elde edilir 2. kalan ("prim") 3: 11 - 2*3. Bu nedenle, döngünün ilk üç yinelemesi 1'e eklenecektir: 3 3 3. Bonus sıfırdır ve son yığın boyutu sadece 2 olacaktır.

Burada yaptığımız şey, bir hatayı dağıtmaktan başka bir şey değildir. Bir şekilde nicel bir şekilde, bir şekilde tatmin edici bir şekilde terim. Bu, tam olarak bir satır segmenti Bresenham algoritması ile raster ekrana çizildiğinde veya bir görüntü Floyd-Steinberg dithering ve etet kullanılarak daha az sayıda renge indirildiğinde gerçekleşir.