c++ - 一维世界中到极点的平均距离

我的世界

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

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

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

std::vector<unsigned int> polePositions;

或带有长度为n的 bool(boolean) vector

std::vector<bool> isThereAPole;

兴趣统计和示例

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

---I-I

与两极的平均距离



然后，我们可以计算每个插槽的平均距离，并将它们平均化，以获得平均平均距离(averageAverageDistance)。对于以上示例，



问题

如何以高性能计算此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 m)。有更好的解决方案吗？

最佳答案

这是从头开始研究6个插槽的问题。

假设所有插槽都已满。然后，从每个插槽到
每隔一个插槽可以以6 x 6矩阵表示为:

| 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)中删除5和4，然后向其添加2和1，可以获得CSUM。

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