一维世界中到达极点的平均距离

Question

我的世界

想象一个有极点的一维离散世界。让我们用一个一维网格来表示这个世界，其中每个插槽要么包含极I，要么不包含极-

--------I-I---------I----II-------I-------------I--

在这个世界上有n插槽和m极。我们可以用一个长度为m的向量表示这个世界，它列出了极点的位置。

std::vector<unsigned int> polePositions;

或具有长度为n的布尔向量。

std::vector<bool> isThereAPole;

兴趣的统计与实例

每个插槽与所有极点的平均距离(averageDistance)。例如，在槽索引2下面(基于零的计数)

---I-I

与两极的平均距离

averageDistance = (1 + 3) /2=2

然后，我们可以计算每个时隙的平均距离，并将它们平均起来，以得到平均距离(averageAverageDistance)。对于上面的例子，

averageAverageDistance =(3+ 5) /2+ (2 + 4)/2 + (1+3)/2 + (0+2)/2 + (1 + 1)/2 + (2+0)/2)/6 = 12/6 =2

问题

如何计算高性能的averageAverageDistance？

通常，在函数的每个调用中，我都有关于n=1e6插槽和m=1e5极点的信息。n将在函数的每个调用中保持不变，但m (以及polePositions或isThereAPole)将因函数调用而有所不同。

坏实现

下面是一个简单的实现，使用上面的小数据作为示例

#include <iostream>
#include <vector>
#include <math.h>

double getAverageAverageDistance(std::vector<unsigned int> polePositions, int n)
{
    double averageAverageDistance = 0.0;
    for (int slot = 0 ; slot < n ; slot++)
    {
        double averageDistance = 0.0;
        for (auto& polePosition : polePositions)
        {
               averageDistance += fabs(slot - polePosition);
        }
        averageDistance /= polePositions.size();
        averageAverageDistance += averageDistance;
    }
    averageAverageDistance /= n;
    return averageAverageDistance;
}

int main()
{
  std::vector<unsigned int> polePositions;
  polePositions.push_back(3);
  polePositions.push_back(5);
  int n = 6;

  std::cout << "averageAverageDistance = " << getAverageAverageDistance(polePositions, n) << "\n";
}

正确地输出

averageAverageDistance = 2

该程序具有时间复杂度O(n )。有没有更好的解决办法？

Answer 1

这是一个从地面到地面的6个插槽的问题。

假设所有的空位都被填满了。然后，从每个插槽到每一个其他插槽的距离可以用一个6x6矩阵表示为：

| 0 1 2 3 4 5 |
| 1 0 1 2 3 4 |
| 2 1 0 1 2 3 |
| 3 2 1 0 1 2 |
| 4 3 2 1 0 1 |
| 5 4 3 2 1 0 |

通过把所有的数字相加，再除以36，就可以计算出总距离。

当一个插槽没有填充一个杆子时，整个柱子可以被移除。比如说，第二个插槽不见了。您可以删除整个第二列，以获得总数。当然，现在的数额需要除以30，而不是36。

让我们来表示列中所有数字的和。将其称为SUM(i)，其中i是列的索引。

当第二行丢失时，您可以将总数表示为：

SUM(0) + SUM(2) + ... + SUM(5)

幸运的是，有一个很好的和模式，您可以将SUM(i)表示为插槽总数和i的函数。

让我们看一下N = 6列的和。

SUM(0) = 5*6/2

让我们调用基数和，CSUM。

SUM(1)是通过从CSUM中删除5，然后添加1来获得的。

SUM(1) = CSUM - (5-1)

SUM(2)是通过从CSUM中去除5和4，然后添加2和1来得到的。

SUM(2) = CSUM - (5-2) - (4-1)
=> SUM(2) = CSUM - (5-2) - (5-2)
=> SUM(2) = CSUM - 2*(5-2)

SUM(3)是通过从CSUM中删除5、4和3，然后添加3、2和1来获得的。

SUM(3) = CSUM - (5-3) - (4-2) - (3-1)
=> SUM(3) = CSUM - (5-3) - (5-3) - (5-3)
=> SUM(3) = CSUM - 3*(5-3)

其模式是：

SUM(i) = CSUM - i*((N-1) - i)

在一般情况下，

CSUM = (N-1)*N/2

有了这些知识，如果你知道有极点的槽的指数，你就可以很容易地计算出总和。如果有O(M)极点，这是一个M操作。

演示程序：

#include <iostream>
#include <vector>

int SUM(int N, int p)
{
   return (N-1)*N/2 - p*((N-1) - p);
}

int main()
{
   int N = 0;
   int M = 0;

   std::cin >> N;
   std::cin >> M;

   std::vector<int> polePositions;
   for ( int i = 0; i < M; ++i )
   {
      int p;
      std::cin >> p;
      polePositions.push_back(p);
   }

   int s = 0;
   for ( int p : polePositions )
   {
      s += SUM(N, p);
   }

   double average = 1.0*s/(N*polePositions.size());

   std::cout << "Average: " << average << std::endl;
}

给定输入

6
2
3 5

输出是

Average: 2

Answer 2

我认为在O(m)中可以做到这一点。

polePositions矢量有每个极点的位置，也就是从第一个插槽到每个极点的距离。取这个向量的和，得到从第一个时隙到所有极点的总距离(稍后我们将计算平均值)。

当你通过每个插槽移动时，这个总距离将被m缩小，直到你到达一个带有极的槽，位于p1位置。当我们到达那里时，您已经添加了(sum - m) + (sum - 2 * m) + ... + (sum - p1 * m)。我们可以轻松地跳过这个距离，并通过添加(p1 * (sum - m) +( sum - p1 *m)/ 2)将其累加到和中。

一旦我们通过了第一个极点，向右的每一步都会增加1的项(当我们离p1越远)，同时减小它的m-1，因为我们离其他极点越近。因此，您可以重复前面的步骤，为每个插槽添加(sum -(m-2))。

继续，直到你为每一个杆添加了术语。最终，你会达到中间，这个学期将增加而不是减少。

在最后一项中，在最后一极的右边加上所有插槽的和。然后用n除以整和。

(这是未调试的算法。)