Лучший способ поиска в массиве?

Question

У меня есть массив (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;
  } 

Я не могу придумать лучшего способа сделать это. Я мог бы использовать функции, чтобы сделать его короче, но это в общем то, что я думаю об использовании. После этого я должен повторить цикл, чтобы перейти к следующему столбцу, который возвращает наилучшее расстояние, и снова выполнить эту процедуру.

Answer 1

Как всегда, когда вы пытаетесь оптимизировать, вы должны сделать выбор:

Хотите ли вы стоимость во время вставки или во время поиска?

Если у вас мало вставок и много поиска в контейнере, вам нужен отсортированный контейнер. Нахождение максимума будет O (1) - т.е. просто выберите последний элемент.

Если у вас много вставок и несколько поисков, то вы можете остаться с несортированным контейнером, и найти максимум равно O (n) - т.е. вам нужно проверить все значения хотя бы один раз, чтобы выбрать максимум.

Answer 2

Профиль. Если это не является главным узким местом, я бы предпочел ясность (ремонтопригодность) перед умом.

Циклическая линейная передача по массивам - это то, что современные процессоры делают довольно хорошо, и подход O (N) часто работает просто отлично.

С тысячами узлов я бы ожидал, что ваш старый Pentium III сможет работать с несколькими миллиардами секунд в секунду! :)

Answer 3

Если вы готовы пожертвовать некоторым пространством, вы можете добавить дополнительные массивы, чтобы отслеживать максимальное расстояние, видимое на данный момент для определенного столбца / строки и узла, которому это расстояние соответствует.

Answer 4

Вы можете немного упростить это. Многие ваши проверки и временные переменные являются избыточными. Вот небольшая функция, которая выполняет ваш поиск. Я переименовал большинство переменных, чтобы быть более точным, каковы их роли.

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