6

I am trying to split an array into n equal parts by calculating start and end indices. The address of the start and end elements will be passed into a function that will sort these arrays. For example, if arraySize = 1000, and n=2, the indices will be 0, 499, 999. So far I have the below code but for odd n, it is splitting it into more than n arrays. Another way I thought of doing this is by running through the loop n times, but I'm not sure where to start.

  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: Here's something else I came up with. It seems to be working, but I need to do some more thorough testing. I've drawn this out multiple times and traced it by hand. Hopefully, there aren't any edge cases that will fail. I am already restricting 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");
}
Improve this question
9
  • 3
    "arraySize = 2, and n=2, the indices will be 0, 499, 999" throw some more light on this pkease Commented Apr 10, 2016 at 5:41
  • You can add + 1 to end in each line in the loop body, and then subtract 1 from the end in the InsertionSort call. end = start + chunkSize; end > arraySize; end = arraySize; InsertionSort(&array[start], end). Thereby you lose a whole bunch of - 1 and + 1 noise. Commented Apr 10, 2016 at 5:42
  • Sorry fixed arraySize to be 1000. Commented Apr 10, 2016 at 5:43
  • Why you get more chunks is that division rounds down. For instance if we calculate 9 / 4 we get 2, just like 8 / 4. But then if we try to split 9 into chunks of 2, we get 5 chunks: 2 2 2 2 1. Commented Apr 10, 2016 at 5:44
  • If you split 9 into chunks of 3, you get 3 3 3. There is no way to get four chunks, unless you allow one of them to be of size 3: 2 2 2 3. Commented Apr 10, 2016 at 5:48

3 Answers 3

Reset to default
9

Calculate the minimum chunk size with the truncating division. Then calculate the remainder. Distribute this remainder by adding 1 to some chunks:

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

For instance if array_size is 11 and N == 4, 11/N yields 2. The remainder ("bonus") is 3: 11 - 2*3. Thus the first three iterations of the loop will add 1 to the size: 3 3 3. The bonus then hits zero and the last chunk size will just be 2.

What we are doing here is nothing more than distributing an error term in a discrete quantization, in a way that is satisfactory somehow. This is exactly what happens when a line segment is drawn on a raster display with the Bresenham algorithm, or when an image is reduced to a smaller number of colors using Floyd-Steinberg dithering, et cetera.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

You need to calculate your chunk size so that it is "rounded up", not down. You could do it using % operator and a more complex formula, but just using simple if is probably easier to understand:

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;
}
Improve this answer

6 Comments

Can you look at my edited solution please? Seems to be working.
@Shan Yeah, that works too. Then you end up with smaller other chunks and larger last chunk, which could be up to twice as large as other chunks. I think it's slightly better do it by having smaller last chunk, because then the work is divided more evenly between threads, for example for array size 8 and 3 threads: chunks 3,3,2 is better than of 2,2,4. However if your array size is bigger, the difference is irrelevant.
int chunkSize = round(float(arraySize) / numThreads); This seems to fix it also
@Shan If you use floats, use ceil to always round up, instead of round which rounds up or down from x.5.
But if arraySize = 10 and n = 3, I would want to have chunkSize = 3.
|
0

I hope this would help:

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);
Improve this answer

2 Comments

I came up with a similar solution in my edit. It seems to be working. Since your's is so similar to mine. I'll accept your answer if I can verify mine to be foolproof.
@Shan : seems identical in solution (Y)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.