[Résolu] Map ou liste chaînée ?

[TimProd]

Bonjour à tous,

Dans mon projet "CHOC" présenté dans la rubrique jeux, j'utilise des listes chaînées quand le besoin s'en fait sentir, par exemple pour la gestion d'une liste pour savoir si des cases sont occupées par des pions alliés ou adverses (modification aisée, interrogation rapide et surtout, contrairement à un tableau, pas besoin de lister toutes les cases, juste celles occupées).

Ma question est de savoir quels est la différence fondamentale entre maps et listes, et quels sont les types de situation où il convient d'utiliser l'une plutôt que l'autre ?
J'avoue que sur ce point, la doc PureBasic ne m'a pas permis de trancher.

Cordialement,

TimProd

[Lord Nelson]

Salut TimProd

Avec une liste tu va mettre dedans des éléments que ta pas besoin de rechercher (Si yen à des tonnes)
Sa peut être par exemple des nombres ou des chaînes.

Mais des que tu va devoir recherche un élément et si tu répète sa très fréquemment, alors tu ne dois pas utiliser une liste chaînée !
Exemple:

Tu veux lister toutes les couleurs utiliser dans une image et leur nombre d'utilisation, alors
Tu va mettre toutes les couleurs dans une liste ?, tu va rechercher pour chaque pixel pour voir si la couleur est dans ta liste ?
Alors ça va prendre plusieurs jours !!!

Par contre si je met les couleurs dans une map, je peux dès l'or les retrouver instantanément ou qu'elles soit grâce à une clef !

J'entre la clef pour savoir si la couleur existe déjà (C'est instantané), si oui, alors j’incrémente de 1 le nombre (De fois que la couleur à été trouvé jusqu'à présent)
que stocke la Map (Elle stocke une clef et une valeur par élément), de cette manière c'est ultra rapide !

Donc en résumer, une liste pour stocker des éléments donc ta pas besoin de faire de recherche
Une map pour faire des recherches et retrouver un élément instantanément ou qu'il soit dans la map grâce à ça clef et sa valeur.

Dans ton cas à toi, si tu dois stocker toutes les cases de ton jeu, utilise une map ou même un tableau (voir plus bas) !
La clef pourra être sa numérotation en X et Y par exemple, sa valeur, si elle est occupé ou pas et par qui !

Sache également qu'une map ne peut être trier alors qu'une liste et un tableau oui !
Sache aussi que tu peux utiliser un tableau dans ton cas, deux dimension, X et Y pour sa position et la valeur de l'élément, par exemple, si elle est occupé ou pas et par qui !

Voilà, j’espère pas m'avoir trop planté

[Ar-S]

Si tu n'as qu'une cellule à gérer, tu peux utiliser une list() mais si tu en as plusieurs comme un tableau de cellule, les MAP sont pratiques. Voilà un exemple de map ou je crée un tableau de 2x2 :

A1.A2
B1.B2

Dans cet exemple tu peux retrouver les données d'une cellule ciblée par son nom.

Code : Tout sélectionner

Structure Cellule
	ID.b
	Couleur.i 
	Etat.b
EndStructure

NewMap Cellule.Cellule() ; 
 
  Cellule("A1")\ID = 0
  Cellule()\Couleur = $00FF00
  Cellule()\Etat = 0
  
 Cellule("A2")\ID = 1
  Cellule()\Couleur = $F11FFF
  Cellule()\Etat = 0
  
  Cellule("B1")\ID = 2
  Cellule()\Couleur = $FF22FF
  Cellule()\Etat = 1
  
  Cellule("B2")\ID = 3
  Cellule()\Couleur = $33FFFF
  Cellule()\Etat = 0
  

;;; VERIF

Cellule ("A1")
Resultat$ = MapKey(Cellule())

Debug "Cellule : " + Resultat$
Debug "ID : " + Cellule()\ID
Debug "Etat : " + Cellule()\Etat
Debug "Couleur : " + Cellule()\Couleur

Debug ""
Debug "----------"
Debug ""

Cellule ("B2")
Resultat$ = MapKey(Cellule())

Debug "Cellule : " + Resultat$
Debug "ID : " + Cellule()\ID
Debug "Etat : " + Cellule()\Etat
Debug "Couleur : " + Cellule()\Couleur

[TimProd]

Merci à tous les deux.

Cela me permet de changer mon fusil d'épaule tant qu'il n'y a que quelques lignes de codes.

Pour résumer :
Les maps = rapidité de traitement, indispensable donc quand le code a besoin d'être optimisé.
Les listes chaînées = facilité de traitement avec, par exemple, une fonction de tri.

Encore merci,

A +

[Micoute]

Bonjour TimProd, tu as tout compris, c'est tout à fait ça ! Mais il faut savoir qu'avec une map, on ne peut pas avoir 2 clés identiques, donc la deuxième efface la première !

[Fig]

Il y a un point à prendre en compte quand tu utilise une map, c'est le nombre de slot que tu lui affecte.

Si tu affecte un slot seulement (par défaut c'est 512 je crois, mais pour illustrer l'exemple je prends ce cas extrême), ta map ne sera pas plus efficace en terme de vitesse qu'une liste chainée.

Il faut savoir que chaque slot d'une map contient (contiendra) une liste chainée lors du remplissage.
Le but est d'équilibrer le nombre de slot en fonction du nombre d'éléments estimées afin d’éviter les ralentissements.

Bon là c'est faire mal aux mouches mais il est bon de savoir comment une map est gérée.

Ainsi, la clé permet d'arriver sur le slot qui contient la liste chainée où l’élément est stockée. Ensuite la liste chainée est parcourue bêtement jusqu'à trouver l'élément en question.
D'où l'importance du bon choix du nombre de slot si tu stock un très grand nombre d'élements.
Personnellement je choisis généralement le ratio 1:3 (cad qu'en moyenne j'aurai 3 elements dans les listes de chacun des slots) mais comme la mémoire n'est plus un problème aujourd'hui, ne pas hésiter à prendre plus large.

Si j'estime que je vais stocker 300 000 éléments, je prends 100 000 de slots minimum par exemple...

Si ce n'est pas clair pour toi, rassure toi, ce n'est pas grave, tout ce mécanisme est transparent pour l'utilisateur, fais abstraction de ce que je raconte et garde juste le ratio 1:3 en mémoire si tu stocks plus de 1536 (512x3) éléments.