在等效数组之间分配元素以实现平衡和

Question

我给了一组元素,比如10到21(总是顺序的),我生成相同大小的数组,其中大小是运行时确定的.

3个生成数组的示例(数组#是动态的,以及所有数组中的元素数,其中一些元素可以是0 - 未使用):

A1 = [10,11,12,13]

A2 = [14,15,16,17]

A3 = [18,19,20,21]

这些生成的数组将被赋予不同的进程,以对元素进行一些计算.我的目标是平衡每个获得阵列的进程的负载.我的意思是:

举个例子,有

A1 = 46

A2 = 62

A3 = 78

对每个线程给出的元素的潜在迭代.

我想重新排列初始数组,为每个进程提供相同数量的工作,例如:

A1 = [21,11,12,13] = 57

A2 = [14,15,16,17] = 62

A3 = [18,19,20,10] = 67

(不是平等分配,但比初始更公平).分布可以是不同的,只要它们接近某个最佳分布并且优于第一个和最后一个数组的最差(初始)情况.在我看来,使用不同的索引可以实现不同的分布[在这里进行数组的拆分{可以是不均匀的}]

这适用于给定的例子,但可能有奇怪的情况..

所以,我认为这是一个反射问题(由于缺乏正确定义的知识),其中应该通过对角线看到数组,例如:

10 | 111213

1415 | 1617

181920 | 21

然后可以做一个明显的替代..

我尝试实现如下:

  if(rest == 0)
    payload_size = (upper-lower)/(processes-1);
  else
    payload_size = (upper-lower)/(processes-1) + 1;
  //printf("payload size: %d\n", payload_size);
  long payload[payload_size];
  int m = 0;
  int k = payload_size/2;
  int added = 0;  //track what been added so far (to skip over already added elements)
  int added2 = 0;  // same as 'added'
  int p = 0;
  for (i = lower; i <= upper; i=i+payload_size){
    for(j = i; j<(i+payload_size); j++){
       if(j <= upper){
         if((j-i) > k){
           if(added2 > j){
             added = j;
             payload[(j-i)] = j;
             printf("1 adding data: %d at location: %d\n", payload[(j-i)], (j-i));
           }else{
             printf("else..\n");
           }
         }else{
           if(added < upper - (m+1)){
             payload[(j-i)] = upper - (p*payload_size) - (m++);
             added2 = payload[(j-i)];
             printf("2 adding data: %d at location: %d\n", payload[(j-i)], (j-i));
           }else{
             payload[(j-i)] = j;
             printf("2.5 adding data: %d at location: %d\n", payload[(j-i)], (j-i));
           }
         }
       }else{ payload[(j-i)] = '\0'; }
    }
    p++;
    k=k/2;

    //printf("send to proc: %d\n", ((i)/payload_size)%(processes-1)+1);
  }

但是失败了.

你肯定可以在实现中看到问题,因为它的可扩展性很差,不完整,杂乱,写得很糟糕等等等等等等......

因此,在给出描述的情况下,我需要帮助实现或者想要更好的方法来实现我想要实现的目标.

PS我需要解决方案尽可能' in-liney '(避免循环嵌套) - 这就是我使用一堆标志和全局索引的原因.

当然,这可以通过额外的循环和不必要的迭代来完成.我邀请那些能够并且在数组方面欣赏索引艺术的人.

我确信那里有一个解决方案,但我无法通过合适的Google查询来查找它.

暗示？我想到使用索引%size_of_my_data来完成这个任务..

PS应用:这里描述

Answer 1

通过简单的分配序列，您只需迭代地将最小和最大元素依次添加到每个列表中即可。有一些终止细节需要修复，但这是总体思路。应用于您的示例，输出将如下所示：

john-schultzs-macbook-pro:~ jschultz$ ./a.out
10 21 13 18  = 62
11 20 14 17  = 62
12 19 15 16  = 62

当 num_procs 均匀划分 num_elems 时，像这样的简单反射分配将是最佳的。当它不满足以下条件时，这将是次优的，但仍然不错：

#include <stdio.h>

int compute_dist(int lower, int upper, int num_procs)
{
  if (lower > upper || num_procs <= 0)
    return -1;

  int num_elems                = upper - lower + 1;
  int num_elems_per_proc_floor = num_elems / num_procs;
  int num_elems_per_proc_ceil  = num_elems_per_proc_floor + (num_elems % num_procs != 0);
  int procs[num_procs][num_elems_per_proc_ceil];
  int i, j, sum;

  // assign pairs of (lower, upper) to each process until we can't anymore

  for (i = 0; i + 2 <= num_elems_per_proc_floor; i += 2)
    for (j = 0; j < num_procs; ++j)
    {
      procs[j][i]   = lower++;
      procs[j][i+1] = upper--;
    }          

  // handle left overs similarly to the above
  // NOTE: actually you could use just this loop alone if you set i = 0 here, but the above loop is more understandable

  for (; i < num_elems_per_proc_ceil; ++i)
    for (j = 0; j < num_procs; ++j)
      if (lower <= upper)
        procs[j][i] = ((0 == i % 2) ? lower++ : upper--);
      else
        procs[j][i] = 0;

  // print assignment results

  for (j = 0; j < num_procs; ++j)
  {
    for (i = 0, sum = 0; i < num_elems_per_proc_ceil; ++i)
    {
      printf("%d ", procs[j][i]);
      sum += procs[j][i];
    }
    printf(" = %d\n", sum);
  }

  return 0;
}

int main()
{
  compute_dist(10, 21, 3);

  return 0;
}