Discussion :

[greenzephyr]

Salut à tous,
J'ai besoin d'un conseil concernant le choix de ma structure de donnée.
Je vous donne le contexte:
Je travaille sur un fichier de diagramme d'antenne associant à un angle d'élévation donné (degré), une valeur de gain (dB).
Genre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
Elevation (deg);Gain (dB)
0;5 
3;45 
6;3.1 
10;6.5 
16;18.1 
20;33.1 
24;31.2 
30;3.5

Dans mon application, j'aurai besoin d'accéder au gain qui correspond à un angle donné. On prendra l'angle le plus proche.
Par exemple;

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Pour un angle de 5 deg, je devrai retourner 3.1 dB

.

Je devrai faire cette opération un nombre de fois assez important (peut-être plusieurs centaines de fois).

Comment me conseillerez-vous de modéliser ces données et la recherche dans ces données ?

J'ai pensé aux arbres binaires de recherche. Qu'en pensez-vous ? Existe-t-il une implémentation Java des ABR ?

J'ai aussi pensé à faire un hashet dont le hash serait calculé intelligemment pour accéder rapidemment à la donnée de l'angle le plus proche de celui demandé mais je bloque sur intelligemment ;-)

SVP, aidez-moi . Donnez moi votre opinion et conseils.
Merci

[zorm]

Bonjour,

Personnellement, j'aurai utilisé une HashMap<Integer,Double>.
Pour la recherche, j'aurai fait une méthode qui utilise containsKey().

Ca donnerait un truc du genre.

Si containsKey alors
Afficher la valeur qui lui correspond
sinon
Rechercher sur valeur ++
Rechercher sur valeur --

Après, si tu cherches sur une valeur qui se trouve au milieu de 2 clés de la map, il faudra faire un choix si tu préfères celle du dessus ou celle du dessous...

Voila la méthode brut de pomme que je mettrai en place dans un premier temps. Après, il faut voir comment elle pourrait etre optimisée

[dinobogan]

Tu peux aussi construire un arbre AVL. c'est un arbre binaire équilibré. Seules les fonctions d'ajout et de suppressions sont spécifiques. La valeur d'un noeud sera son gain. La complexité de recherche dans ce type d'arbre est O(log n).
Il y a plein de littérature sur les arbre AVL, je te laisse le soin de chercher par toi même

[greenzephyr]

Merci,
cela me parait de bonnes bases pour commencer mes recherches.
Je vous tiens au courant
A+

[greenzephyr]

Bon en fait j'ai fait une classe de donnée contenant mon élévation et mon gain:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
public class ElGainPatternElement
{
  private double elevation;
  private double gain;
...
+getters/setters
}

J'utilise alors un ArrayList que je trie à l'aide d'un Comparator adapté à ma donnée pour comparer sur l'élévation.

J'utilise alors la méthode Collections.binarySearch pour rechercher un élément d'élévation donné dans ma liste.
J'ai quelque peu spécialiser cette méthode afin de retourner l'élement juste au-dessus ou au-dessous si l'angle n'existe pas dans ma liste (voir mon premier post pour l'exemple)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
public static <T> T binarySearch(List<? extends T> list, T key,
      Comparator<? super T> c, boolean isMinStrategy)
  {
    int index = Collections.binarySearch(list, key, c);
 
    // si objet non trouvé
    if (index < 0)
    {
      // récupérer l'index le plus proche de celui recherché
      index = isMinStrategy ? (-index - 2) : (-index - 1);
 
      // si plus grand que tous les élts, retourner le dernier de la liste
      if (index >= list.size())
        index = list.size() - 1;
 
      // si plus grand que tous les élts, retourner le premier de la liste
      else if (index < 0)
        index = 0;
    }
    // retourner l'objet le plus proche (au regard de la stratégie min ou max)
    return list.get(index);
  }

Ca marche très bien et très rapide.
Par contre, je viens d'apprendre que la stratégie à adopter n'est pas de retourner l'élément supérieur ou inférieur mais de faire une interpolation du gain.

L'interpolation à priviligier doit être celle des moindres carrés .
J'y connais absolument rien à ca... Quelqu'un a une idée pour faire cela ?

Merci