Discussion :

[boboss123]

Bonjour,

Ne connaissant pas trop les algo de trie, j'aurais besoin de vos lumières

Je dois développer sur un µControlleur 32bits un système qui me permette de créer une table d'adresse MAC.

Une entrée dans la table contient deux paramètres : "adresse MAC de 6 octets", "numéro de l'interface sur laquelle l'adresse MAC a été détectée"

Donc lorsque je reçois un paquet Ethernet sur mon µControlleur je dois :
1- récupérer l'adresse MAC et le numéro de l'interface (ça je sais faire)
2- regarder si l'adresse MAC est déjà enregistrée dans la table
3- si l'entrée existe déjà, vérifier que le numéro de l'interface est toujours le même => s'il n'est pas bon, écraser la valeur existante qui est dans la table par la nouvelle (ce cas ne devrait pas arriver souvent.. voir quasiment jamais).
4- si l'entrée n'existe pas, l'ajouter dans la table.
=> le nombre d'entrées sera inférieur a 4000
=> le temps d'affichage de la table n'est pa

Quel algo de trie me conseillez-vous d'utiliser pour que le remplissage se fasse le plus rapidement possible (faut-il que les entrées soient classées par ordre d'arrivée ou de valeur d'adresse MAC ou autre ?) ?

Merci d'avance,

[Obsidian]

Hello,

Tu vas donc te retrouver dans une situation où l'ajout d'une nouvelle entrée sera très rare (connexion d'un nouvel équipement au réseau) mais où la consultation de cette table sera fréquente. En outre, la recherche ne se fera qu'en fonction de l'adresse MAC et ta table, sans être ridicule, contient un nombre raisonnable d'entrées.

Moi, j'opterais pour un tri par insertion tout bête : tu conserves ta table triée et quand tu veux insérer une nouvelle entrée, tu fais une boucle qui décale d'une position la seconde moitié de la table. Sur 4000 entrées, un micro-contrôleur 32 bits ne devrait franchement pas avoir de mal. Pour le reste, c'est ce qu'il y aura de plus rapide en consultation et de plus économique en mémoire.

[boboss123]

bonjour,

Merci pour ta réponse,

Pour la consultation, il faut faire la recherche par dichotomie (ou il y a une meilleure méthode ?) ?


Je voudrais aussi tester avec une méthode qui me permette d'ajouter rapidement mes éléments car au démarrage je risque d'avoir plein de nouvelles entrées (et si je mets trop de temps, je risque de perdre des paquets). Quelle méthode me conseillez-vous d'utiliser ?
Il n'existe pas un tuto expliquant les différentes méthodes possibles pour ce genre de problème ?

[Obsidian]

Hello,

Oui, par dichotomie toute bête. Jusqu'à 4000 entrées, ça ne fera que douze comparaisons au maximum.

Pour le reste, ça dépend essentiellement de la quantité de mémoire dont dispose ton équipement. Si tu n'en manques pas, tu fais un index. Mais comme de toutes façons, il faudra consommer des ressources pour le maintenir à jour, le mieux et le plus facile, je pense consiste à maintenir une table triée et à consacrer toute la mémoire inutilisée à une longue file d'attente.

Donc, priorité aux paquets entrants, éventuellement en utilisant des interruptions, que tu stockes dans cette file et ensuite aux tâches de maintenance. Ton équipement risque d'être un peu lent au démarrage à tout digérer mais il ne devrait pas perdre d'information.

[boboss123]

ok, merci pour les informations.

Pour information : ça fonctionne comment le principe d'index ?

[Obsidian]

Comme ça :
http://fr.wikipedia.org/wiki/Index_%...onn%C3%A9es%29

L'idée est que pour chaque entrée, tu consacres un champ (dans l'entrée elle-même ou dans une structure distincte) formant une liste chaînée ou un arbre qui, lui, sera classé selon un autre critère.

De combien de mémoire disposes-tu sur ton micro-contrôleur ?