Re: Algorithmic vs design complexity

Hi Ralph,

On Mar 29, 3:20 am, ralph <nt_consultin...@yahoo.net> wrote:


:-)

Thank you for your reply; it is very kind of you to take the time,
despite my failure to clearly put across the problem. I was concious
of making my post too long-winded and complex, so in my attempt to
simplify, I probably made it unclear and too abstract.


Actually, the bus-stop example is just theoretical. My field involves
similar things though; such as calculating road centre-lines on the
map, longitudinal sections (peaks and troughs), cross-sections,
earthwork and that kind of stuff. So it involves a lot of work with
geometrical objects and queries on these objects; such as the height
of a point on a profile given the horizontal distance along it. To do
various calculations I write code that combine these queries, and a
lot of the time the functions combine in the way described in my
original post.


The thing is that I have very nicely encapsulated object-oriented
structures with simple implementations of key queries; such as the
height of a profile. The problem is one of efficiency, and it occurs
when one function runs in a loop (n) where each iteration makes a
query that itself needs to loop (m) to calculate the result. The
result is a quadratic number of iterations (n*m).

But, sometimes there is an opportunity for the loops to progress in
parallel (along distance in my example), thus reducing the number of
iterations drastically (n+m). The problem is: my nice encapsulated
design doesn't support that, and it is unclear what the cleanest
solution to the problem is. In my bus-stop example, the brute-force
solution would be to re-implement the height function within the bus-
stop loop, keeping track of where we are on the profile along the way.
This totally breaks the encapsulation of the profile height
calculation.

To make things more concrete, I've included a complete code example
below based on a simpler scenario. Note the messy implementation of
the optimized parallel traversal. The aim is to somehow structure the
code so that the query remains encapsulated and usage remains simple
and clean; while running just as fast.


In spirit, that has been my location throughout. :-)

My aim is to rewrite and improve a lot of my code, so thanks again for
your reply. It has forced me to more clearly formulate the problem,
and it has helped me better characterize it and recognize when it
applies. In fact, a better subject title might be "Optimizing ordered
queries" or something like that.

Here is an attempt at a more concise characterization of the problem:

* Function A makes a series of calls (queries) to function B.
* The queries are ordered in terms of a query argument x.
* B iterates in the same domain and order as x.

The above characteristics indicate that the code can be optimized by
using a single traversal over the domain of the query argument and
keeping parallel track of the state of A and B.

Here's the code example:

<code>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

struct Floor
{
  int height;
};

struct Building
{
  typedef vector <Floor> Floors;
  Floors floors;

  int floor (int height)
  {
    int hf = 0;
    const int nf = floors.size ();
    for (int i = 0; i != nf; ++i)
    {
      hf += floors [i].height;
      if (height < hf) return i;
    }
    return nf;
  }
};

struct Object
{
  int height;
};

bool less_height (const Object& a, const Object& b)
{
  return a.height < b.height;
}

void output (int height, int floor)
{
  cout << "object height: " << height
    << ", floor: " << floor << "\n";
}

int main ()
{
  Building building;
  const int nf = 6;
  Floor floors [nf] = {5, 4, 4, 4, 3, 3};
  building.floors.assign (floors, floors + nf);

  const int no = 5;
  Object objects [no] = {21, 7, 14, 11, 8};

  cout << "Unordered traversal:\n\n";
  for (int i = 0; i != no; ++i)
  {
    int h = objects [i].height;
    output (h, building.floor (h));
  }

  // Now let's sort the objects on height.

  sort (objects, objects + no, &less_height);
  cout << "\nOrdered traversal:\n\n";
  for (int i = 0; i != no; ++i)
  {
    int h = objects [i].height;
    output (h, building.floor (h));
  }

  // Keeping the objects sorted opens an opportunity
  // to optimize algorithms that traverse them.

  cout << "\nParallel traversal:\n\n";
  {
    int hf = 0; // absolute height of floor
    int io = 0; // object index
    for (int i = 0; i != nf; ++i)
    {
      hf += floors [i].height;
      for (; io != no; ++io)
      {
        int h = objects [io].height;
        if (h > hf) break;
        output (h, i);
      }
    }
  }

  cin.get (); // pause
  return 0;
}
</code>

Regards,
Vidar Hasfjord