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

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

..但失败得很惨。

你肯定能看出实现中的问题，因为它可扩展性差、不完整、凌乱、写得不好等等等等......

因此，根据描述，我需要有关实现或更好方法的想法来实现我想要实现的目标的帮助。

附言我需要尽可能“内联”的解决方案(避免循环嵌套)——这就是我使用一堆标志和全局索引的原因。

当然，这可以通过额外的循环和不必要的迭代来完成。我邀请那些可以和欣赏的人 t̲h̲e̲ ̲a̲r̲t̲ ̲o̲f̲ ̲i̲n̲d̲e̲x̲i̲n̲g̲ 当涉及到数组时。

我确信某处有解决方案，但我无法进行适当的 Google 查询来找到它。

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

附言申请:described here

Answer 1

这是我用双端队列写的一个O(n)的解决方案(双端队列，不需要双端队列，可以使用简单的数组，但是由于popRight和popLeft，双端队列使代码变得干净)。代码是 Python，不是伪代码，但应该很容易理解(因为它是 Python)。:

def balancingSumProblem(seqStart = None, seqStop = None, numberOfArrays = None):
    from random import randint
    from collections import deque

    seq = deque(xrange(seqStart or randint(1, 10), 
                        seqStop and seqStop + 1 or randint(11,30)))
    arrays = [[] for _ in xrange(numberOfArrays or randint(1,6))]

    print "# of elements: {}".format(len(seq))
    print "# of arrays: {}".format(len(arrays))
    averageNumElements = float(len(seq)) / len(arrays)
    print "average number of elements per array: {}".format(averageNumElements)

    oddIteration = True
    try:
        while seq:
            for array in arrays:
                if len(array) < averageNumElements and oddIteration:
                    array.append(seq.pop()) # pop() is like popright()
                elif len(array) < averageNumElements:
                    array.append(seq.popleft())
            oddIteration = not oddIteration
    except IndexError:
        pass

    print arrays
    print [sum(array) for array in arrays]

balancingSumProblem(10,21,3) # Given Example
print "\n---------\n"
balancingSumProblem() # Randomized Test

基本上，从迭代到迭代，它在抓取大元素并将它们均匀分布在数组中和抓取小元素并将它们均匀分布在数组中之间交替。它从外到内(尽管您可以从内到外)并尝试使用应该是每个数组的平均元素数来进一步平衡它。

它并非在所有测试中都 100% 准确，但在大多数随机测试中表现良好。您可以尝试在此处运行代码:http://repl.it/cJg