Average distance to a pole in a 1D world

user_2051137 0
Viewed 111

My world

Imagine a 1 dimensional discrete world where there are poles. Let's represent this world by a 1D grid where each slot either contains a pole I or does not contains a pole -

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

In this world there are n slots and m poles. We can represent this world either with a vector of length m listing the positions of the poles

std::vector<unsigned int> polePositions;

or with a boolean vector of the length n

std::vector<bool> isThereAPole;

Statistic of interest and example

Each slot has an average distance (averageDistance) to all poles. For example, below the slot index 2 (zero based counting) 

---I-I

has an average distance to the poles of

averageDistance = (1 + 3) / 2 = 2

We can then compute this average distance for each slot and average them out to get the average average distance (averageAverageDistance). For the above example,

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

Question

How to compute this averageAverageDistance with high performance?

Typically, I'll have about n=1e6 slots and about m=1e5 poles at each call of the function. n will remain the same at every call of the function but m (and polePositions or isThereAPole) will vary among function calls.

Bad implementation

Here is a simple implementation using the above small data as example

#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";
}

which correctly outputs

averageAverageDistance = 2

This program has time complexity O(n m). Is there a better solution?

time-complexity algorithm c++ performance
2 Answers

Here's a look at the problem from the ground up for 6 slots.

Let's say all the slots are filled. Then, the distances from each slot to every other slot can be represented in a 6 x 6 matrix as:

| 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 |

The total distance can be computed by adding all the numbers and dividing the total by 36.

When a slot is not filled with a pole, that entire column can be removed. Say, the 2-nd slot is missing. You can remove the entire second column to get the total sum. Of course, the sum now needs to be divide by 30 and not 36.

Let's you can represent the sum of all numbers in a column. Call it SUM(i) where i is the index of the column.

When the second row is missing, you can represent the total sum as:

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

Fortunately, there is a good pattern for the sums and you can represent SUM(i) as function of the total number of slots and i.

Let's look at the sums of the columns for N = 6.

SUM(0) = 5*6/2

Let's call the cardinal sum, CSUM.

SUM(1) is obtained by removing 5 from CSUM and then adding 1 to it.

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

SUM(2) is obtained by removing 5 and 4 from CSUM and then adding 2 and 1 to it.

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

SUM(3) is obtained by removing 5, 4, and 3 from CSUM and then adding 3, 2, and 1 to it.

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

The pattern is that:

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

In the general case,

CSUM = (N-1)*N/2

With that knowledge, you can easilty compute the total sum if you know the indices of the slots where there are poles. It's a O(M) operation if there are M poles.

A demonstrative program:

#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;
}

Given the input

6
2
3 5

the output is

Average: 2
user_4345510

I think this can be done in O(m).

The polePositions vector has the position of each pole, which is also the distance from the first slot to each pole. Take the sum of this vector to get the total distance from the first slot to all poles (we'll compute the average later).

As you move thru each slot, this total distance will be reduced by m, until you reach a slot with a pole, located at position p1. When we get there, you've added in (sum - m) + (sum - 2 * m) + ... + (sum - p1 * m). We can easily skip over this distance, and accumulate this into the sum by adding (p1 * ((sum - m) + (sum - p1 * m)) / 2).

Once we pass that first pole, each step to the right will increase the term to add by 1 (as we get farther from p1) while reducing it by m-1, as we get closer to all the other poles. So you'd repeat the previous step, adding (sum - (m - 2)) for each slot.

Continue until you've added in terms for each pole. Eventually you'll reach the middle, and the term will increase instead of decrease.

For the last term, add in the sum for all the slots to the right of the last pole. Then divide the whole sum by n.

(That's the undebugged algorithm.)

user_52316070
Related