將C數組拆分爲n等分

我想通過計算開始和結束索引將數組拆分成n個相等部分。開始和結束元素的地址將被傳遞給一個將對這些數組進行排序的函數。例如，如果arraySize = 1000，並且n = 2，則索引將爲0,499,999。到目前爲止，我有下面的代碼，但對於奇數n，它將它分割成多於n個數組。我認爲這樣做的另一種方式是循環運行n次，但我不知道從哪裏開始。將C數組拆分爲n等分

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

編輯：這裏是別的東西，我想出了。它似乎在工作，但我需要做一些更徹底的測試。我已經多次繪製並手工追蹤。希望沒有任何邊緣案例會失敗。我已經限制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"); 
}

來源

2016-04-10 Shan

「arraySize = 2，並且n = 2，索引將爲0,499,999」在這個pkease上拋出更多的光 – nullpointer

您可以在循環體的每一行中向結尾添加+ 1，然後在InsertionSort調用中從'end'減1。 'end = start + chunkSize'; 'end> arraySize'; 'end = arraySize'; 'InsertionSort（＆數組[開始]，結束）'。因此你會失去一大堆 - 1和+ 1的噪音。 – Kaz

對不起，固定arraySize爲1000. – Shan

您需要計算您的塊大小，以便「四捨五入」而不是減小。

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

來源

2016-04-10 06:05:36 hyde

你能看看我編輯過的解決方案嗎？似乎工作。 – Shan

@Shan Yeah，那也可以。然後你最終得到更小的其他塊和更大的最後塊，這可能是其他塊的兩倍。我認爲通過減小最後一個塊的做法會稍微好一點，因爲這樣工作就會在線程之間更均勻地分配，例如數組大小爲8和3的線程：塊3,3,2優於2,2,4。但是，如果您的數組大小更大，則差異無關緊要。 – hyde

'int chunkSize = round（float（arraySize）/ numThreads）;' 這似乎也解決了它也 – Shan

我希望這將有助於：

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

來源

2016-04-10 06:09:24 nullpointer

我在編輯中提出了類似的解決方案。它似乎在工作。因爲你的和我的很相似。如果我能驗證我的安全性，我會接受你的答案。 – Shan

@Shan：在解決方案（Y）中似乎完全相同 – nullpointer

計算與最小的塊大小，你可以用它%運營商和更復雜的公式，但只是用簡單的if可能更容易理解做截斷分裂。然後計算餘數。通過加入1至一些組塊分發此其餘：

僞代碼：

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和N == 4，11/N得到2.餘數（「獎金」）是3：11 - 2*3。因此，循環的前三個迭代將在大小上加1：3 3 3.獎金然後爲零，最後一個塊大小將爲2.

我們在這裏做的只不過是分配一個錯誤以一種令人滿意的方式在某種程度上離散量化。當使用Bresenham算法在線柵顯示器上繪製線段時，或者使用Floyd-Steinberg抖動等將圖像縮小爲較少數量的顏色時，就會發生這種情況。

來源

2016-04-10 06:12:45 Kaz

將C數組拆分爲n等分

回答

相關問題