Better method to search array?

Question

I have an array (nodes[][]) that contains values of effective distances that looks something like this:

__                 __
|1    0.4  3         |
|0.4  1    0         |
|3    3.2  1   ...   |
|0.8  4    5         |
|0    0    1         |
--                  --

Where the first value, node[0][0] is the distance from node 0 to node 0 which is 1.
So the distance from node 2 to node 1 is 3.2 (node[2][1]=3.2)
I need, given a node column, to search through the rows to find the farthest distance, while not picking itself (node[1][1])
The method I was thinking to do something like this:

int n=0;
currentnode=0;  //this is the column I am searching now
if(currentnode==n)
   n++;
best=node[n][currentnode];
nextbest=node[n++][currentnode];
if(nextbest>best)
   best=nextbest;
else
  for(int x=n;x<max;x++)    //max is the last column
  {
   if(currentnode==n)
      continue;
   nextbest=node[x][currentnode];
   if(nextbest>best)
      best=nextbest;
  }

I can't think of a better method to do this. I could use functions to make it shorter but this is GENERALLY what I am thinking about using. After this I have to loops this to go to the next column that the best distance returns and do this routine again.

Answer 1

As always when trying to optimize, you have to make a choice:

Do you want the cost during insertion, or during search ?

If you have few insertions, and a lot of search to do in the container, then you need a sorted container. Finding the maximum will be O(1) - i.e. just pick the last element.

If you have a lot of insertions and a few search, then you can stay with an unsorted container, and finding a maximum is O(n) - i.e. you have to check all values at least once to pick the the maximum.

Answer 2

You can simplify it quite a bit. A lot of your checks and temporary variables are redundant. Here's a small function that performs your search. I've renamed most of the variables to be a little more precise what their roles are.

int maxDistance(int fromNode) {
    int max = -1;

    for (int toNode = 0; toNode < nodeCount; ++toNode)
    {
        if (fromNode != toNode && nodes[toNode][fromNode] > max) {
            max = node[toNode][fromNode];
        }
    }

    return max;
}

Answer 3

If you are willing to sacrifice some space, you could add additional arrays to keep track of the maximum distance seen so far for a particular column/row and the node that that distance corresponds to.

Answer 4

Profile it. Unless this is a major bottleneck, I'd favour clarity (maintainability) over cleverness.

Looping linearly over arrays is something that modern processors do rather well, and the O(N) approach often works just fine.

With thousands of nodes, I'd expect your old Pentium III to be able to a few gazillion a second! :)