更好的方法来搜索数组？

我有一个数组（nodes[][]）包含看起来像这样的有效距离值：更好的方法来搜索数组？

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

其中第一个值，node[0][0]是从节点0到节点0，是1
所以距离从节点2到节点1的距离为3.2（node[2][1]=3.2）
我需要，给定一个节点列，通过行搜索，找到最遥远的距离，而不是选择本身（node[1][1]）
的方法，我在想这样做像这样：

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

我想不出一个更好的方法来做到这一点。我可以使用函数来缩短它的长度，但这正是我想要使用的。在此之后，我必须将其循环到下一个最佳距离返回的列，并再次执行此例程。

来源

2009-10-13 Nick Sinas

是今天到期的作业吗？ – catfood 2009-10-13 20:01:21

这是一个我正在使用贪婪的地理数据包转发方法寻找Ad-Hoc无线网络的有效距离的小型项目。所以不行？当然，这是我正在做的一个非常简化的版本。 – 2009-10-13 20:05:31

如果节点距离自身的距离是1，矩阵中怎么会有0？这是否是某种时空操纵？ :) – Zed 2009-10-13 20:23:24

你可以简化它很多。很多你的检查和临时变量是多余的。这是一个执行搜索的小功能。我已经将大多数变量重命名为更精确一些他们的角色。

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

来源

2009-10-13 20:26:57

这是我所寻找的更多。我感谢帮助！ – 2009-10-14 01:51:23

试图优化时，与往常一样，你必须做出选择：

你想要的成本插入过程中或搜索过程中？

如果你有很少插入，并在容器中做很多搜索，那么你需要一个排序的容器。找到最大值将是O（1） - 即只是选择最后一个元素。

如果你有很多插入和一些搜索，那么你可以留在一个未分类的容器中，找到最大值是O（n） - 即你必须检查所有值至少一次以选择最大值。

来源

2009-10-13 20:05:41 NewbiZ

我不能做一个排序的容器，因为数组值对应于节点位置，所以当我想知道从节点1到3的距离时，我可以调用节点[1] [3]。如果这是排序，这将无法正常工作。 – 2009-10-13 20:15:37

我的错误，我认为很明显，更改容器的布局意味着改变阅读方式，所以我甚至没有提及它... – NewbiZ 2009-10-13 20:21:56

@thegreekness：没有什么能阻止你同时拥有数组和排序容器。 – Zed 2009-10-13 20:24:18

-1

如果你愿意牺牲一些空间，您可以添加额外的阵列来跟踪迄今所看到的特定列/行和该距离相当于节点的最大距离。

来源

2009-10-13 20:30:27 Ryan

-1

简介它。除非这是一个主要瓶颈，否则我会倾向于清晰度（可维护性）而不是聪明。

在阵列上线性循环是现代处理器做得相当好的事情，O（N）方法通常工作得很好。

有了成千上万的节点，我希望您的旧Pentium III能够以每秒几兆的速度运行！ :)

来源

2009-10-13 20:36:29 Will

更好的方法来搜索数组？

回答

相关问题