# Better method to search array?

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.

13.10.2009 19:56:55
Is that homework assignment due today?
catfood 13.10.2009 20:01:21
This is a small project I'm doing finding the effective distances for an Ad-Hoc Wireless Network using a greedy geographical packet forwarding method. So...no? Granted this is a very simplified version of what I'm doing.
Nick Sinas 13.10.2009 20:05:31
If the distance of a node from itself is 1, how could there be a 0 in the matrix? Is this some sort of space-time manipulation ? :)
Zed 13.10.2009 20:23:24
So what you want is, for a given node (aka column), what other node is farthest away? A 2d array doesn't seem like the best way to store this information - unless distances aren't symmetric somehow. Also, your choice of 1 for the distance from a node to itself seems odd. Is that because you are using zero to represent no-path? Have you thought about using nodes and edges, as in a graph structure?
Mikeb 13.10.2009 20:24:10
@Zed a 0 exists by that it is out of range.
Nick Sinas 13.10.2009 22:41:53
4 ОТВЕТА
РЕШЕНИЕ

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;
}``````
13.10.2009 20:26:57
This is more what I was looking for. I appreciate the help!
Nick Sinas 14.10.2009 01:51:23

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.

13.10.2009 20:05:41
I can't do a sorted container because the array values correspond to the node locations, so when I want to know the distance from node 1 to 3 I can call node[1][3]. If this is sorted this will not work.
Nick Sinas 13.10.2009 20:15:37
My mistake, I thought it was obvious that changing the layout of the container means changing the way to read it, so i did not even mentioned it...
NewbiZ 13.10.2009 20:21:56
@thegreekness: Nothing prevents you from having both your array, and the sorted container.
Zed 13.10.2009 20:24:18
@Zed How could I have a sorted array while amaintaing the ability to call node[2][1] and get the distance from node 2 to node 1?
Nick Sinas 13.10.2009 22:44:31

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.

13.10.2009 20:30:27

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! :)

13.10.2009 20:36:29