# balance

**Repository Path**: thickas/balance

## Basic Information

- **Project Name**: balance
- **Description**: 平均分配问题
- **Primary Language**: Python
- **License**: GPL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 8
- **Forks**: 0
- **Created**: 2020-09-14
- **Last Updated**: 2024-04-22

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## balance(平均分配问题算法探讨)
<hr>


#### 问题描述
&emsp;&emsp;对于$N$个数据，将其分成$m$组（其中$N>3$，$m\geq2$），要求每组的数据个数尽量相等（至多差1），同时每组数据之和也尽量相等。

&emsp;&emsp;显然每组的元素个数至多为$n=\lceil N/m \rceil$。如果N刚好能被m整除，则每组元素均为$n$个；如果N不能被m整除，则有一部分组的元素为$n$个，一部分组的元素个数为$n-1$个。

&emsp;&emsp;于是我们可以将N个数据随机初始化到下面的有凹陷的矩阵$data$中，其行数$m$，列数$n$；矩阵$data$从第$k$行开始凹陷，其最后一个元素无效，这里用0表示；其中$0<k\leq m$，如果k=m，则表示没有凹陷，也就是每组元素个数都是$n$。

$$
data=
     \left(\begin{matrix} 
        a_{0,0} & a_{0,1} & …& a_{0,n-2} & a_{0,n-1}\\
        a_{1,0} & a_{1,1} & …& a_{1,n-2} & a_{1,n-1}\\
        \vdots & \vdots & …& \vdots & \vdots\\     
        a_{k-1,0} & a_{k-1,1} & …& a_{k-1,n-2} & a_{k-1,n-1}\\       
        a_{k,0} & a_{k,1} & …& a_{k,n-2} & 0\\     
        a_{k+1,0} & a_{k+1,1} & …& a_{k+1,n-2} & 0\\    
        \vdots & \vdots & …& \vdots & \vdots\\    
        a_{m-1,0} & a_{m-1,1} & …& a_{m-1,n-2} & 0\\
    \end{matrix}\right)
$$

&emsp;&emsp;对应于矩阵$data$每一行的数据之和为：

$$
total=(S_0, S_1, ..., S_{k-1}, S_k, S_{k+1}, ..., S_{m-1})
$$

&emsp;&emsp;于是问题转化为通过重组$data$中的有效元素，使$total$中的数据尽量相等，其等价于$total$之间的极差（最大和最小值之差）最小化，也就是要实现下面的优化器：

$$Optimizer：Minimize(max(total)-min(total)) $$

&emsp;&emsp;我们下面主要解决矩阵$data$的优化问题。


#### 问题的难度分析
&emsp;&emsp;为分析简单，不妨设矩阵中所有数据都是有效的，也就是$mn$个数据分成$m$组的情况，其存在的组合数为：
$$
\frac {\prod\limits_{i=0}^{m-1}C_{(m-i)n}^{n}}{m!}\geq\frac {\prod\limits_{i=0}^{m-1}(m-i)^n}{m!}=(m!)^{n-1}
$$   
&emsp;&emsp;$m\geq2$，问题的规模至少是一个$O(2^n)$，这实际上应该是一个NP-hard问题。所以除非数据规模很小，否则使用穷举的方式是不可取的。    

#### 算法思路
&emsp;&emsp;通过上面的分析，穷举不可取，如果要将其转化为多重背包问题或装载问题，好像也是很难实现的。在这里，我们只有另辟蹊径，采取一种近似的策略，其思想是通过在最大和最小行之间交换任务，使其差距减少，然后重复进行，直到达到预设极差目标或最大允许交换次数为止。具体如下：

```
data←要优化的矩阵
shape←(rows,cols,concav) /*描述矩阵形状的参数*,其中rows=m,cols=n,concav=k*/
diff_expected←极差目标  /*期望达到的极差范围，小于此值才算达到目标。对于矩阵元素是整数的问题，可以设置为2）*/
max_exchange←最大允许交换次数

初始化total    
while 极差 >= diff_expected：
    p1←total最大的行,p2←total最小的行  /*如有多个相同的最大行，任取一个；最小行亦如些*/
    备份p1,p2
    for i←0 to max_exchange:
        随机交换p1,p2中的一个元素
        if p1、p2的差距绝对值缩小：
            更新total
            break    /*继续while*/
        else:
            contiue  /*继续for*/        
    else /*达到最大交换次数，缩小差距失败*/
        恢复p1,p2
        输出未达到目标的优化结果
        结束
else:  /*极差达标，成功*/
    输出达到目标的优化结果
    结束
```

#### 算法的python实现
&emsp;&emsp;使用python实现上述算法，代码见[balance.py](/balance.py)。

&emsp;&emsp;通过对python实现的测试，可以得出描述程序性能的基本指标，每毫秒交换次数。在我的笔记本上只能达到150次左右，这个速度是不能满意的。

&emsp;&emsp;于是我用C++重写了balance函数，并通过dll的方式由python调用。详细代码见[balance.cpp](/balance.cpp)（注意此文件请用gbk格式打开）。此代码是最终代码，需要说明几点对代码的改进要点：

&emsp;&emsp;1、在mingw下加了O3选项编译，以提升速度这个性能。编译时要注意选择32位还是64位编译器。
```
g++ balance.cpp -fPIC -shared -o balance.dll -O3 -static
```
&emsp;&emsp;2、随机数的生成，最开始使用的是系统的rand函数，但发现性能太低，占据了内循环中75%左右的运行时间。于是改成xorshift算法，并将每次生成的64位随机数高32位和低32位分别用于两个组的交换序号，改进后的速度能提高3-5倍左右（与计算机硬件配置有关）。

&emsp;&emsp;3、对total的存储、最大和最小查找、更新采用了STL中的multimap结构。它是使用平衡二叉树来储存数据，在分组数$m$较大时，能使更新和查找的性能均能在$O(logN)$，比向量（不论是否排序）或链表的性能有所提高。当然在分组数较少时，性能可能会比使用向量或链表略低，但基本可以忽略。

&emsp;&emsp;对C++编写的代码进行测试，在我的笔记本上每毫秒交换次数能达到15万次左右，比python提高了1000倍。

#### 注意事项
&emsp;&emsp;不论是使用python还是C++的实现，在测试代码调用balance平衡之后，优化后的最终结果已更新到矩阵data中，故可以使用np.save或np.savetxt保存结果矩阵。

&emsp;&emsp;对于整数问题，没有精度问题，优化结果是“精确”的；对于浮点数据，由于精度问题，在累计求和后，因为精度损失，最终优化的极差结果可能会有细微的差错，所以是一个“近似”的结果。

&emsp;&emsp;不论对于整数问题，浮点数问题，都可能存在求和后数据溢出的问题，所以对于超大规模的数据或离散度极高的数据测试，要当心这类问题。

&emsp;&emsp;[balance.cpp](/balance.cpp)代码是用gbk格式保存的，所以请用gbk格式打开，否则会出现乱码。

#### 后记
&emsp;&emsp;研究这个算法问题，源起于一个银行催货款分配任务的题目，其实际意义并不在于问题的本身，而在于研究算法的思想和如何去优化，提升速度。

&emsp;&emsp;如还想在C++层面的进一步优化，一是可以考虑重新设计随机数算法，二是考虑GPU并行计算（优化耗时长的时候一般在后面相对平衡的情况下，对于整数问题，那时候最大和最小行都可能分别是多行）

&emsp;&emsp;通过一些测试，可以观察得到以下一些情况：

&emsp;&emsp;1、增加rows和cols，需要进行的优化的轮次会大幅增加，耗时也会增加。

&emsp;&emsp;2、对于同样的rows和cols，如果将low和high之间的范围增大，每epoch需要交换的次数会大大增加，耗时会显著地增加。表明数据离散程度越高，越难达到平衡。

&emsp;&emsp;3、平均每毫秒交换次数是相对稳定的，主要与计算机硬件配置有关。

&emsp;&emsp;可以将算法应用于另一类问题，对N个正数，同样分组，要求每组数据的乘积尽量相等，这可通过将每个数据取对数，转换为分组求和尽量相等的问题。