Geteiltes C-Array in n gleiche Teile

Question

Ich versuche, ein Array in n gleiche Teile durch Berechnung der Start- und Ende-Indizes zu teilen. Die Adresse der Start- und Endelemente wird an eine Funktion übergeben, die diese Arrays sortiert. Zum Beispiel, wenn ArraySize = 1000, und n = 2, sind die Indizes 0, 499, 999. Bis jetzt habe ich den folgenden Code, aber für ungerade n, es teilt es in mehr als n Arrays. Eine andere Möglichkeit, dies zu tun, ist, n mal durch die Schleife zu laufen, aber ich bin mir nicht sicher, wo ich anfangen soll.

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

EDIT: Hier ist etwas, das ich mit aufkommen. Es scheint zu funktionieren, aber ich muss etwas gründlicher testen. Ich habe es mehrmals herausgesucht und es von Hand verfolgt. Hoffentlich gibt es keine Randfälle, die scheitern werden. Ich beschränke bereits n> = arraySize.

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

Sie benötigen eine Blockgröße zu berechnen, so dass es „aufzurunden“ ist, nicht nach unten. Man könnte es % Operator und eine komplexere Formel, tut verwenden, aber nur mit einfachen if ist wahrscheinlich einfacher zu verstehen:

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

Ich hoffe, dass dies dazu beitragen würde:

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

die minimale Blockgröße berechnet mit die abgeschnittene Teilung. Dann berechne den Rest. Diesen Rest verteilt, indem 1 bis einige chunks Zugabe:

Pseudo-Code:

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

Zum Beispiel, wenn ARRAY_SIZE 11 und N == 4, 11/N ergibt 2. Der Rest ("Bonus") ist 3: 11 - 2*3. Also die ersten drei Iterationen der Schleife wird 1 zu der Größe hinzufügen: 3 3 3. Der Bonus trifft dann Null und die letzte Chunk-Größe wird nur 2.

Was wir hier tun, ist nichts mehr als die Verteilung eines Fehlers Begriff in einer diskreten Quantisierung, auf eine Weise, die irgendwie zufriedenstellend ist. Dies passiert genau dann, wenn ein Liniensegment auf einer Rasteranzeige mit dem Bresenham-Algorithmus gezeichnet wird oder wenn ein Bild mit Floyd-Steinberg-Dithering auf eine kleinere Anzahl von Farben reduziert wird, und so weiter.