前言
近似计算的效率之争
正文
问题来源
最近工作上遇到这么一个问题。老司机讲了一下公司实现的方式，然后个人觉得有效率更优的解法。讨论一下感觉有这样的可能，于是便安排我来验证一下是否是更优。
问题描述
问题是这样的，我们计算结束后会有很多个group组的记录，每个group中含有的记录条数是不确定的，然后我们这里有很多个partition分区。每一个组不能拆分多个部分放在partition中（每个组只能放在一个partition中），让所有partition上的记录数保持相对平均。由于以前都是有确切解，都会给出示例。由于该问题（应该是NP问题）只需要求工程上可行解（近似解）即可，所以不展示示例。
分析：
算法课中有个装载问题，譬如一堆人按体重分为两组拔河，如何获得最平均的分配。而我们这个实际工程场景有多个分区。如何获得最平均的分区，思想如下：
将分组依次分配到每一个分区，若分区当前大小+当前分配的分组大小< 分区设定的最大数量，则分配成功，否组则试图将该分组分配到下一个分区，若所有的分区都分配不成功，则将分区的默认最大数量调大；
所有的分区分配完一轮后，重新按照包含的计费对象数量从小到大进行排序，然后将剩下未分配的分组按照上面的流程重新进行分配；
上述算法有两个缺陷：初始分区大小和增长分配分区大小这两个值如何确定。这两个值的取值影响整个算法的效率，需要在工程上进行测试来估计。并且这样分配本身效率和实现都不太好。所以公司在实现上放弃该算法。
记录平均值法：
将所有分区的容量看成是无上限的（重要思想）。
记录加入partition的平均值（非实时更新）average，初始状态为0。将partition组成循环队列，每个partition初始化值为0。每次将group加入partition时，寻找当前partition中已装入的记录数小于average的分区，若在一圈内找到该分区，将group的值加入寻找到的分区；若在一圈内未能找到当前partition中已装入的记录数小于average的分区，则更新average值。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<malloc.h>
#include<sys/time.h>
//分区数
#define NUM 89
//测试次数
#define TIMES 10000
//数字范围
#define RANK 100
int main()
{
int i;
int num;
int a[NUM];
int average=0;
int j=0;
int total=0;
int index;//记录结束一圈的index
struct timeval st;
struct timeval end;
unsigned long timer;
memset(a,0,sizeof(a));
srand((unsigned int)time(NULL));
gettimeofday(&st, NULL);
for(i=0;i<TIMES;i++)
{
num = rand()%RANK+1;
index = (j-1+NUM)%NUM;//坑死了
for(;;)
{
if(a[j] <= average)
{
total += num;
a[j] += num;
break;//退出内循环
}
if(index==j)//转一圈了
{
average = total / NUM + 1;
//continue;
}
j=(++j)%NUM;
}
}
gettimeofday(&end, NULL);
timer = 1000000 * (end.tv_sec - st.tv_sec) + end.tv_usec - st.tv_usec;
printf("timer = %ld us\n", timer);
//for(i=0;i<NUM;i++)
// printf("%d\n",a[i]);
printf("%d %d\n",average,total);
return 0;
}
小顶堆化法： 贪心思想，每次获取最小的分区，然后更新，堆整理。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<malloc.h>
#include<sys/time.h>
//分区数
#define NUM 89
//测试次数
#define TIMES 10000
//数字范围
#define RANK 100
#define lchild(i) ((i<<1)+1)
int main()
{
int i;
int num;
int a[NUM];
int average=0;
int j=0;
int temp=0;
int start;
struct timeval st;
struct timeval end;
unsigned long timer;
memset(a,0,sizeof(a));
srand((unsigned int)time(NULL));
gettimeofday(&st, NULL);
for(i=0;i<TIMES;i++)
{
num = rand()%RANK+1;
a[0] += num;
temp = a[0];
start = 0;
for(j = lchild(start); j < NUM; j=lchild(j)){
if(j<NUM && a[j]>a[j+1]){
j++;
}
if(temp < a[j]){
break;
}
a[start] = a[j];
start = j;
}
a[start] = temp;
}
gettimeofday(&end, NULL);
timer = 1000000 * (end.tv_sec - st.tv_sec) + end.tv_usec - st.tv_usec;
printf("timer = %ld us\n", timer);
//for(i=0;i<NUM;i++)
// printf("%d\n",a[i]);
//printf("%d %d\n",average,total);
return 0;
}
总结：
对比两种算法的效率，小顶堆化的算法并没有在效率上优于记录平均值法，相反小顶堆化的运行时间大致上是记录平均值法的两倍。
在其他参数不变的情况下，更改group的记录数的取值范围（RANK），对算法效率无任何影响。
在其他参数不变的情况下，增加group数（TIMES）不影响两种算法的时间运行的时间比率。而减少group数到一定情况下，记录平均值法效率得到显著提高，而小顶堆化算法效率无影响（计算量减少，运行时间会减少）。
在其他情况不变的情况下，增加分区数（NUM）到一定的情况下，记录平均值法效率得到显著提高，而小顶堆化算法效率降低。当分区数为23时两者算法时间近似。
结语
坚持不懈。
