performance - 使两个直方图成比例的算法，最小化了删除的单位

Question

假设您有两个具有相等数量容器的直方图。n个观测值分布在各个垃圾箱中。现在每个箱子都有0到N个观测值。
为了使两个直方图成比例，哪种算法适合于确定要从两个直方图中删除的最小观测数它们不需要在绝对数上相等，只需要彼此成比例也就是说，必须有一个共同的因素，一个直方图中的所有箱子都可以乘以这个因素，才能使它等于另一个直方图。
例如，假设下面两个直方图，其中每个直方图中的项i指的是各个直方图在bin i中的观察数。
直方图1:4、7、4、9
直方图2:2，0，2，1
对于这些直方图，解决方法是从直方图1中删除第2个行中的所有7个观察值，然后从第4个行中删除另外7个观察值，这样（直方图1）*2=直方图2。
但是，一般的算法可以用来找到两个直方图的子集，最大化它们之间的总观测数，同时使它们成比例？您可以从两个直方图中删除观察结果，也可以仅从一个直方图中删除观察结果。
谢谢！

Answer 1

在我看来，这个问题相当于最小化曼哈顿长度| R |，其中R=x a-B，a和B是你的“向量”，x是你的比例标度。
| r有一个最小值（不一定是整数），因此可以使用简单的对分算法（或类似于牛顿法的方法）快速找到它。
然后，假设您想要一个比例为整数的解决方案，测试两种情况ceil（x）和floor（x），以找到曼哈顿长度最小的情况（这是需要删除的观察数）。
证明问题不是np难的：
考虑一个低效的“解决方案”，即从所有容器中删除所有n个观察结果。现在A和B都等于“0”直方图0=（0,0,0，…）这两个直方图是相等的，因此对于所有的比例值S是0＝S＊0的比例，因此要去除的观测值的最大值是N.。
现在假设有一个更有效的解决方案，其中有一个比例/偏移量n和一个比例尺度S＞2×N（即在去除一些观测值A= N*B或B= N*A）之后。如果a=0和b=0，我们得到了n个清除的前一个解（这与小于n个清除的假设相矛盾）。如果a=0且b≠0，则不存在s<>0以致于0=s*b且不存在s以致于s*0=b（b=0且s≠0的参数类似）。所以一定是a≠0和b≠0的情况。假设a是要缩放的直方图（因此a*s=B），a必须至少有一个非零分录a[i]，最小值为1（在去除额外的观察值之后），因此当缩放时，它将具有最小值≥因此，等效条目b[i]也必须至少有2*n个观测值。但是，最初观测的总数是n，因此我们需要在b[i]中添加至少n个观测，这与改进后的解决方案具有少于n个添加/删除的假设相矛盾。所以没有一个“有效”的解需要大于N的比例尺度。
因此，要找到一个有效的解决方案，最坏的情况下，需要测试缩放因子在0-n范围内的“最佳拟合”解决方案。
A=S*B中比例因子S的“最佳匹配”解决方案，其中A和B各有M个箱子
添加/删除{a b s（a[i]-s*b[i]）mod s+abs（a[i]-s*b[i]）div s}的和（i=1到m）。
这是一个m阶运算，因此测试0-n范围内的每个比例因子将是o阶（m*n）的算法。
我相当肯定（但还没有正式的证据），比例因子不能超过最满的容器中的观察数实际上，它通常要小得多。对于具有200个箱子的两个直方图，随机选择每个箱子30-300个观察值：如果在A和B的所有箱子中分别有Na>Nb的总观察值，则标度因子要么几乎总是在Na/Nb-4>Nb）。