Meilleure méthode pour rechercher un tableau?

J'ai un tableau (nodes[][]) qui contient des valeurs de distances efficaces qui ressemble à quelque chose comme ceci:Meilleure méthode pour rechercher un tableau?

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

Lorsque la première valeur, node[0][0] est la distance du nœud 0 à 0 noeud qui est 1.
donc la distance du noeud 2 au noeud 1 est de 3,2 (node[2][1]=3.2)
j'ai besoin, donné une colonne de noeud, pour rechercher à travers les lignes pour trouver la plus grande distance, sans se ramasser (node[1][1])
la méthode que je pensais faire quelque chose comme ça:

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

Je ne peux pas penser à une meilleure méthode pour le faire. Je pourrais utiliser des fonctions pour le rendre plus court mais c'est GÉNÉRALEMENT ce que je pense utiliser. Après cela, je dois faire une boucle pour aller à la colonne suivante que la meilleure distance revient et refaire cette routine.

Source

2009-10-13 Nick Sinas

Ce devoir est-il dû aujourd'hui? – catfood

C'est un petit projet que je fais en trouvant les distances efficaces pour un réseau sans fil Ad-Hoc en utilisant une méthode d'acheminement de paquets géographique glouton. Donc non? Certes, c'est une version très simplifiée de ce que je fais. –

Si la distance d'un nœud par rapport à lui-même est 1, comment pourrait-il y avoir un 0 dans la matrice? Est-ce une sorte de manipulation spatio-temporelle? :) – Zed

Vous pouvez le simplifier un peu. Un grand nombre de vos contrôles et variables temporaires sont redondants. Voici une petite fonction qui effectue votre recherche. J'ai renommé la plupart des variables pour être un peu plus précis sur leurs rôles.

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

Source

2009-10-13 20:26:57

C'est plus ce que je cherchais. J'apprécie l'aide! –

Comme toujours en essayant d'optimiser, vous devez faire un choix:

Voulez-vous le coût lors de l'insertion, ou pendant la recherche?

Si vous avez peu d'insertions et beaucoup de recherche à effectuer dans le conteneur, vous avez besoin d'un conteneur trié. Trouver le maximum sera O (1) - c'est-à-dire choisir le dernier élément. Si vous avez beaucoup d'insertions et quelques recherches, alors vous pouvez rester avec un conteneur non trié, et trouver un maximum est O (n) - c.-à-d. Vous devez vérifier toutes les valeurs au moins une fois pour choisir le maximum .

Source

2009-10-13 20:05:41 NewbiZ

Je ne peux pas faire un conteneur trié parce que les valeurs du tableau correspondent aux emplacements des nœuds, donc quand je veux connaître la distance du nœud 1 à 3, je peux appeler le nœud [1] [3]. Si cela est trié cela ne fonctionnera pas. –

Mon erreur, je pensais qu'il était évident que changer la disposition du conteneur signifie changer la façon de le lire, donc je ne l'ai même pas mentionné ... – NewbiZ

@thegreekness: Rien ne vous empêche d'avoir à la fois votre tableau, et le trié récipient. – Zed

-1

Si vous êtes prêt à sacrifier un peu d'espace, vous pouvez ajouter des tableaux supplémentaires pour garder une trace de la distance maximale vu jusqu'à présent pour une colonne particulière/ligne et le nœud que cette distance correspond à.

Source

2009-10-13 20:30:27 Ryan

-1

Profil. À moins que ce soit un goulot d'étranglement majeur, je serais favorable à la clarté (maintenabilité) sur l'intelligence.

La mise en boucle linéaire sur des tableaux est quelque chose que les processeurs modernes font plutôt bien, et l'approche O (N) fonctionne souvent très bien.

Avec des milliers de nœuds, je m'attendais à ce que votre vieux Pentium III puisse atteindre quelques milliards de seconde! :)

Source

2009-10-13 20:36:29 Will

Meilleure méthode pour rechercher un tableau?

Répondre

Questions connexes