PureBasic

Bonsoir, une petite question sur les fondamentaux de la programmation,

Liste, map ou tableau ?
Je me pose souvent cette question, je présume que chaque structure à son avantage, et si je pose cette question c'est pour essayer de mieux comprendre et d'optimiser au maximum mes programmes (je penses notamment au programme serveur de 3Arks).

Pour ce faire, je vais déjà expliquer que j'ai globalement compris comment fonctionne les tableaux et les listes ;
Un tableau récupère un espace mémoire qui correspond à ; 1ère dimension { * 2nd dimension ... }* taille de l'élément stocké. Dans la mémoire. Ainsi sa longueur est fixé, et pour accéder à un élément c'est instantanée (pour un tableau de dimension 5 sur 5 ) :
pointeur_sur_element[3,3] = *pointeur_du_tableau + 3*5 + 3

Pour une liste, chaque donnée stocké l’élément + un pointeur vers l'élément suivant. On a donc des choses de ce genre ;
[chose_a stocker][pointeur vers la seconde chose à stocker...]

Les maps, déjà, j'ai pas compris comment ça fonctionne mais vue le gros avantage qu'il existe sur les listes (pointer vers un élément avec sa clé), je présume que c'est plus lent qu'une liste. De même, une liste est plus lente qu'un tableau.

Je suis partie donc du principe qu'il valait mieux utiliser un tableau si on avait la taille de ce qu'on allait stocker (et que la taille était fixe). Une liste si la taille varie au cours du temps, et une map dans quel cas ? Pour ma part, dans mes programmes, j'ai tendance à abuser des maps, et je me demandais si il valait mieux faire ça :

Pour une structure qui comporte une ID, un pseudo, des coordonnées, pour récupérer rapidement un élément de la structure, en fonction d'un ID, mieux vaut il faire ça ; Ou ça : De même, une question du même genre, mon joueur se balade sur une carte. A chaque coordonnées de la carte, il est probable qu'il rencontre un évènement, l'évènement est traité dans une structure, je stocke donc des pointeurs. Ces évènements sont rare. J'ai pensé à 3 méthodes pour stocker ce genre de chose.

Via un tableau :
Chaque coordonnée est représenté dans le tableau, si une coordonné vaut 0, c'est qu'il n'y a pas d'évènement, sinon sa pointe vers l'évènements à executer. Le gros défaut d'une telle technique, c'est qu'on risque d'utiliser beaucoup plus de mémoire que nécessaire.

Via une map :
La map contiendrait uniquement les évènements, pour vérifier qu'un joueur a marché sur un évènement, j'utiliserais la clé de la map en faisant ; Map_Evenement(str(positionX)+":"+str(positionY))
Si la clé n'existe pas, il n'y a pas d'évènement, si la clé existe, on a directement le pointeur vers l'évènement.

Via une liste :
La liste contiendrait uniquement les évènements, pour vérifier qu'un joueur a marché sur un évènement, je ferais un : Je suis arrivé donc au problème suivant ;
Avec une map, j'ai pas l'impression que ce soit propre, avec une liste ça me parait lourd de parcourir tout la liste pour chaque déplacement, avec un tableau ça me parait lourd d'utiliser autant de mémoire alors qu'il risque d'avoir peu d'évènement pour de grande carte.

Donc voilà, j'aimerais un petit éclaircissement, si quelqu'un sait, les différences de vitesse entre map/liste/tableau et les différences d'occupation mémoire (un ordre d'idée) ?
Je me doute que la réponse du problème dépends uniquement de la quantités de données à stocker.

Merci d'avance !

Bonjour Stombretrrooper

Pour ma part je n'utilise que rarement les listes et les Maps. Mais j'abuse souvent des tableaux. Tu semble indiquer qu'il te faut a l'avance savoir la taille du tableau. Ceci est faux. Tu oublie la focntion Redim.


Voici un bout de code qui modifi la longueur du tableau a chaque tour de boucle en fonction de ce que je recherche dans un fichier pour l'inclure dans un tableau.
J'espère avoir un petit peu éclairé ta lanterne
Michel

Salut Stombretrooper,

Pour la dernière partie, je n'ai pas d'info pour répondre à tes questions mais je ne stockerais pas les évènements dans une map. Les tests de collisions en X,Y ça prend rien en temps de calcul et c'est très précis.
D'autant s'il est possible que tes évènements se déplacent...

Après, si vraiment tu as beaucoup d'évènements, tu peux essayer de les activer/desactiver uniquement quand ils sont dans le périmètre de ton joueur. A voir pour combiner avec la gestion du MapEditor.

Inutile de tester des évènements ou des contacts avec des éléments qui ne sont pas à l'écran...

Bon courage pour optimiser

Les "map" en PB sont plus connues sous le nom de Table de hachage.

Cala permet de stocker de grande quantité de données sans passer par une base de données. Les données ne pourront pas être triées, elles sont "en vrac" et on y accède à l'aide d'une clé créée par un algorithme.

En gros, on peut imaginer un annuaire téléphonique en vrac (qui ne serait pas trié par ordre alphabétique ou autre), ce qui fait beaucoup d'entrés, dont la clé serait calculée sur le nom et prénom et les données associées seraient l'adresse et le n° de tel. Qu'est ce qui ce passe quand 2 clés sont identiques : la collision.
L'accès aux données en mémoire est plus rapide qu'avec une base de données qui utilise beaucoup le disque dur.

Pour plus de précision :
http://fr.wikipedia.org/wiki/Table_de_hachage
http://www.siteduzero.com/tutoriel-3-32 ... chage.html

Donc, il n'est pas besoin d'utiliser les map avec un petit volume de données.

Mesa.

Ta question n'est pas assez précise. Si les trois systèmes existent, c'est bien parce que chacun a ses avantages et ses inconvénients.

En gros :

• les tableaux permettent de stocker TOUS les éléments correspondant à n dimensions. Exemples : toutes les cases d'un échiquier, tous les points d'une image...
• les listes permettent de stocker les éléments utiles et de supprimer/ajouter (donc allocation mémoire dynamique), de trier et de chercher rapidement. Exemple : les pièces de l'échiquier...
• les maps permettent de stocker les éléments utiles, de supprimer/ajouter, de trouver rapidement et facilement par le programmeur grâce à un index nominatif. Elles sont normalement triées automatiquement. Exemple : où est la reine ?

les réponses précédentes ont déjà dus te donner pas mal de réponse, moi je vais y ajouter que tu peux mélanger les méthodes :

par exemple : tu fais un tableau avec tout tes évènements que ce soient des structures ou non,
et tu accèdes au éléments que tu veux par l'intermédiaire d'une map. Le tableau ne sera pas d'une taille folle, puisqu'il n'utiliseras que la mémoire du nombre d'évènement,
et avec la map dont chaque élément est un pointeur vers les données du tableau sera utile pour les trouver.

Tu peux aussi utiliser la map de pointeur avec une liste chainée, il faut être plus prudent, mais un tri de la liste chainée ne modifieras pas l'accès aux éléments que tu pourras avoir avec la map.

Il me semble qu'une map est très rapide, (@mesa en parle plus haut avec les tables de hachage), perso le truc qui me gène c'est de devoir créer une chaine pour accéder à l'élément.
Après avoir lu ton post, la méthode que je choisirais pour gérer les évènements aux coordonnées de la carte est une map, comme toi.
Car cela permet de ne pas se poser la question de savoir si l'évènement est dans le champ de vision. (au pire fait des tests de vitesse

Merci de vos réponses !

Je vais m'adapter, je vais rester sur le système de map pour les collisions avec les évènements, je verrais bien si ça convient ou non.

Après pour répondre à Cool Dji, je pense que c'est déjà assez compliquer de gérer les évènements sans devoir calculer quel évènement est sur l'écran de qui (car on parle bien de l'appli serveur, qui accueil tout les joueurs, il est ainsi fort probable qu'il y est plusieurs joueurs sur une seule map).

Pour répondre à MLD, je connais la fonction redim, mais c'est vraiment une des fonctions que j'essayent d’éviter au maximum, par peur de faire une erreur de redimensionner mon tableau d'une mauvaise manière.

Il faut bien comprendre comment marche le classement des données en table de hachage pour profiter de toute cette puissance.

Dans un tableau à une dimension de 512 et un octet stocké, tu as en gros une zone mémoire qui va aller de l'adresse M à l'adresse M+511.
ton tableau est donc:
dim carte.b(512), il occupe 512 octets en mémoire.
Quand tu veux accéder à un octet en fonction de son index tu fais ça:
octet=carte(index) (cad que le programme va calculer l'adresse de départ M+l'index pour trouver l'adresse de ton octet)
L'accès à l'octet pointé par l'index est quasiment instantané.

Voyons la table de hachage:
Newmap carte.b(512)
512 correspond au nombre de slots (ou alvéoles) que pb affecte par défaut à une table de hachage, mais c'est un paramètre très important (au point que je pense que ce paramètre ne devrait pas être facultatif)
512 emplacement mémoires sont créés, comme pour le tableau du dessus.
Comment y accéder ? Comme ci-dessus on a besoin de fournir au programme un index.
Au lieu de donner directement un index entre 0 et 511, cet index va être calculé à partir d'une chaine de caractère. Ce calcul s'appelle la fonction de hachage.
A partir de n'importe quelle chaine de caractère on doit avoir un chiffre compris entre 0 et 511. (donc si la chaine fait 512 cela devient 0, 513=>1 etc. C'est un modulo)
Donc à partir de deux chaines de caractères différentes on peut tomber sur le même index. Problème en vu...
En fait, pour chaque index (slot) il y a une liste chainée qui correspond.
Si on a deux éléments dont la clé correspond au slot 511, la liste chainée du slot 511 contiendra 2 éléments.
ainsi quand vous accédez à un de ces 2 éléments, le programme calcul l'index à partir de la clé, puis recherche dans une liste chainée l’élément correspondant. Cette recherche peut être plus ou moins longue en fonction du nombre d’éléments stocké dans ce slot.
Conclusion, il faut ajuster le nombre de slot au nombre d’éléments qui seront stockés dans la table de hachage, pour que la recherche reste rapide. Quoiqu'il en soit, si une case n'est pas utilisée, on économise avec la table de hachage, de la mémoire,(au moins à partir d'une certaine dimension qui correspond aux octets occupés par la structure de la map) contrairement au tableau où toutes les cases sont stockées en mémoire.

Je ne suis pas sûr d'avoir été clair ...

t'es certain de ton truc de la liste chainée, je me souviens d'autre chose pour pb moi.
Fred, ton mot (si possible ??

Non je ne suis pas certain pour Pb, j'en ai aucune idée...
Je ne fais pas dans le reverse ingeenering moa..
En théorie, dans le pire cas, dans une map d'un seul slot, la recherche est de l'ordre de O(n) comme dans une liste chainée alors qu'elle est de O(1) si il y a suffisamment de slots. (comme dans un tableau)

Dis nous de quoi tu te rappelle, ça m'interesse bien sûr !

Ps: perso je me sers d'une table de hashing pour remplacer un tableau de pathfinding sur une grande carte, en utilisant la clé "X/Y".
J'économise beaucoup de mémoire ainsi.

en pb, une map peut te restituer la clé des éléments qui la compose.
Donc l'utilisation en mémoire est plus grande (puisqu'il faut stocker la clé),
mais du coup, il ne peux pas y avoir plusieurs slot sur un élément de map ??

Ah, sur cet aspect là, je ne connais pas toute les infos stockée en plus que l'élement, j'ai simplifié volontairement, en prenant un stockage d'un octet fixe, sans structure ou autres élements.
Mais concernant la gestion des collisions, je pense que c'est la méthode que Fred a adopté. (listes chainés, c'est la plus simple)
D'après wiki on peut stocker en arbre équilibré (pas terrible si il a peu de collision) les éléments en collision ou avec un adressage ouverts.(pas très efficace si on veut une table de hachage généraliste comme c'est le cas de la fonction de pb)

ouaip, mais le truc, c'est que si tu mets la même clef, le prog te dis que l'élément existe déjà.
Donc, dans l'hypothèse que tu trouves une clé qui donne le même résultat (dur à trouver en le voulant >< ) bah normalement, le prog devrais dire que l'élément existe déjà. (je me pers en conjecture là )

Non je crois que tu confonds la clé et l'index qui ressort de la fonction de hachage.
Si tu as la même clé, le programme te dis que cet élément existe déjà.
L'index qui est calculé, on n'y a pas accès, c'est transparent pour l'utilisateur de pb.

ce qui voudrais dire qu'il compare les clés une à une ?
ou bien lorsqu'il tombe sur un index identique, il compare ta clé à toutes celle de la liste jusqu'à la bonne (ça serais super lent ;'( )

edit : c'est presque un chat ;'(