Nouvelle souris sans fil à mémoire

[Tony04]

Bonsoir à tous,

je suis entrain de réaliser une souris sans fil dans laquelle je stocke entre 50 et 100 locos (avec adresse, nom, crans). Tout fonctionne mais quand je liste mes locos j'aimerais les trier au moins par adresse de machine (voir par nom, plus dur).
Quelqu'un a-t-il déjà eu ce problème à résoudre avec arduino ou éventuellement dans un autre domaine ?

Que ferais-je sans Locoduino ?    (l'ordi vient de me souligner en rouge Locoduino, je l'ai vite remis en place  )

A plus tard donc
Cordialement
Antoine

[Didier44]

Bonjour Antoine,

Tu ne nous donnes pas beaucoup de clés pour t'aider 
En C++ il existe une fonction appelé std::map qui pourrais t'aider (voir ce lien https://fr.cppreference.com/w/cpp/container/map)
Si à chaque loco tu as associé une classe ou une struct que tu puisses atteindre par un pointeur, alors map te permets d'associer à une clé (le nom de la loco ou son CV) le pointeur vers ta loco. Les clés sont triés par ordre alphabétique. Et il est très simple de retrouver une loco juste par son nom:

Code: [Sélectionner]

std::map<nom_loco, pointeur_vers_loco> liste_locos
pointeur_vers_loco = liste_locos[nom_loco]

Si tu as de la mémoire disponible dans ton Arduino tu peux faire la même chose en utilisant non pas le nom de la loco mais son adresse.

Code: [Sélectionner]

std::map<adresse_loco, pointeur_vers_loco> liste_locos
pointeur_vers_loco = liste_locos[adresse_loco]

Cette fonction n’existe pas en natif dans l'IDE d'Arduino mais sur un développement actuel, dont je parlerais bientôt, j'utilise un plugin (et non une library) qui le permet et qui fonctionne bien. Bien sur cela consomme un peu plus de mémoire sur l'Arduino.
Voir ici pour ce plugin http://andybrown.me.uk/2011/01/15/the-standard-template-library-stl-for-avr-with-c-streams/

Correction: une note dans l'un de mes projets m'a induit en erreur: les STL sont bien natifs à ce jour et la library  (ArduinoSTL par Mike Matera) est inspirée du lien ci dessus et c'est celle que j'ai utilisée récemment.

Bon développement
Didier

[Tony04]

Bonjour à tous,

merci à toi Didier pour ce renseignement qui est certainement la solution.
Hélas, je suis absolument nul en classe et en structure; de plus je suis à 98% de stockage programme et 76% de ram, il ne me reste donc pas beaucoup de place mais je vais quand même me pencher sur cette solution peut-être avec les derniers neurones qui me restent 

Actuellement j'ai en EEPROM les 50 locos sous ce format: 1 octet=ordre (besoin interne), 2 octets=adresse loco, 14 octets=nom loco. Comment pourrais-je utiliser ta solution ?

Bonne après-midi Locoduino
Antoine

[Thierry]

Un autre moyen est de créer une liste d'entiers ou d'octets (si on se limite à 255 machines maxi) qui représente la liste triée des locos présentes en EEPROM. Il "suffit" de créer cette liste au démarrage une fois pour toutes. L'autre solution si l'on veut éviter d'utiliser de la mémoire centrale ou de la mémoire programme est de créer cette liste directement en mémoire EEPROM grâce à un autre programme sur Arduino ou sur ordinateur, et de mettre ces 255 octets dès le début de l'EEPROM, avant les locos. Pour atteindre une loco, une simple indirection suffit : je veux la loco 3 dans l'ordre, je lis l'octet 3 de la liste qui me dit c'est l'enregistrement EEPROM 17, je lis la loco à l'emplacement 17 !

[Tony04]

Super idée et totalement dans mes cordes celle-là, un grand merci à toi Thierry.

Bonne soirée à tous
Antoine

[Thierry]

De rien.

Pour aller un peu plus loin et faire profiter tout le monde, voici un bout de code pour expliquer:

On commence par déclarer une liste, et la remplir avec un numéro croissant:

Code: [Sélectionner]

byte listeTriee[255];

for (int i = 0; i < 255; i++)
listeTriee[i] = i;

On a ainsi la liste des locos non triée, désignée par leur position dans l'EEPROM.
Puis on réalise le tri proprement dit par la méthode dite du tri à bulle: (https://fr.wikipedia.org/wiki/Tri_%C3%A0_bulles)

Code: [Sélectionner]

for (int i = 255 - 2; i >= 0; i--)
{
for (int j = 0; j <= i; j++)
{
if (loco[listeTriee[j+1]].adresse < loco[listeTriee[j]].adresse)
{
byte t = listeTriee[j + 1];
listeTriee[j + 1] = listeTriee[j];
listeTriee[j] = t;
}
}
}

Si l'ordre entre deux locos n'est pas le bon, on échange simplement les octets de la liste triée.
Pour tester sur le nom ou autre chose, il suffit de remplacer le '.adresse' par autre chose. Pour trier dans l'ordre inverse, changer le '<' par un '>' !
Je n'ai ni compilé ni testé ce code...

[bobyAndCo]

Trop top    Je ne connaissais pas le tri à bulle, ni même le tri shaker, la fonction tri étant disponible dans la plus part des langages !

Merci Thierry pour l'astuce.

[Dominique]

Super intéressant tout ça, merci Thierry 

Moi j’ai bien envie d’explorer le tri à peigne.

[Thierry]

Oui, ce type de tri va plus vite, mais il prend un peu plus de mémoire programme (on est déjà à 98%!) et la vitesse ne semble pas le critère déterminant.

[Jean-Luc]

Quicksort forever. 

Plus sérieusement, il faut prendre un algorithme efficace et peu gourmand en mémoire temporaire

https://fr.m.wikipedia.org/wiki/Algorithme_de_tri

Complexité spatiale de 1 (ne nécessite pas de mémoire additionnelle), cas moyen en n log n, pire cas en n log n si possible. Le gagnant serait le smoothsort : https://fr.m.wikipedia.org/wiki/Smoothsort de Dijkstra (un gars qui vaut le coup).

[Tony04]

Bonsoir Thierry,

Code: [Sélectionner]

byte listeTriee[255];

for (int i = 0; i < 255; i++)
listeTriee[i] = i;


Code: [Sélectionner]

for (int i = 255 - 2; i >= 0; i--)
{
for (int j = 0; j <= i; j++)
{
if (loco[listeTriee[j+1]].adresse < loco[listeTriee[j]].adresse)
{
byte t = listeTriee[j + 1];
listeTriee[j + 1] = listeTriee[j];
listeTriee[j] = t;
}
}
}


J'ai enfin eu le temps d'insérer ton code dans ma souris et contrairement à ce que je pensais je gagne de la mémoire et tout fonctionne au top.

Encore merci à toi

Cordialement
Antoine