2
votes

Conteneur le plus efficace pour la carte uint16_t à uint16_t

Je développe un programme pour une machine à très faible puissance de traitement où je veux mapper les clés uint16_t aux valeurs uint16_t .

J'utilise actuellement std: : map utilise une lecture non sécurisée:

std::map<uint16_t, uint16_t> m;
//fill m only once

while(true){
    auto x = m[y];
}

Les performances ne sont toujours pas acceptables pour les exigences. Existe-t-il une meilleure solution en terme de vitesse d'exécution?

Modifier: Quelques informations:

Le nombre total d'articles est inférieur à 500
L'insertion n'est effectuée qu'une seule fois
L'interrogation des valeurs est effectuée plus de 250 fois / s
Les clés et les valeurs sont uniques
La RAM est très limitée, la RAM globale est de 512 Ko, la RAM libre pour cette partie du code est inférieure à 50 Ko
Processeur monocœur 100 MHz

performance c++ dictionary

14 commentaires

Avez-vous essayé std :: unordered_map ?

Je pense que plus d'informations sur la tâche à accomplir et les restrictions aideraient.

Quelles contraintes sont requises pour le conteneur?

uint16_t peut contenir des valeurs 0..65535, alors pourquoi ne pas simplement utiliser un tableau fixe où les clés sont les index? uint16_t m [65535]; ... uint16_t y = ...; auto x = m [y]; Un tel tableau ne prendrait que 128 Ko de mémoire au maximum.

Combien d'articles? Une fois, j'ai fait un travail d'optimisation et j'ai trouvé que pour 10 éléments ou moins, avec de petites clés (comme des entiers), une simple recherche linéaire était plus rapide que les cartes, les cartes non ordonnées ou la recherche binaire. Commencez simplement par l'avant et recherchez jusqu'à la fin ou vous le trouvez. Ne gardez même pas une valeur de longueur, recherchez toujours les 10 éléments et remplissez les emplacements inutilisés avec des zéros ou -1 ou autre. Avec le tableau de taille fixe et le bon compilateur (et le processeur évidemment), vous pouvez même le dérouler et le vectoriser pour vous.

Vous devez fournir des informations sur la distribution et la taille des données.

Pour 500 éléments, je commencerais avec un tableau simple et ferais une recherche linéaire. L'efficacité du cache peut largement l'emporter sur la complexité algorithmique. Si cela s'avère lent, je regarderais vos données. Savez-vous quelles seront les quelque 500 valeurs? Si tel est le cas, vous pouvez leur proposer un hachage parfait et le stocker dans un tableau et y accéder via un index haché. Sinon, std :: unordered_map pourrait être plus rapide que votre solution std :: map .

Utilisez un tableau trié et effectuez une recherche binaire.

Pourquoi prenez-vous même la peine de mapper les données d'une valeur à une autre? Pourquoi ne pas simplement utiliser l'original et ne pas avoir à le traduire?

Merci pour toutes vos suggestions. std :: unordered_map entraîne des performances inférieures à std :: map

@NathanOliver Je vais essayer de trouver la fonction de hachage parfaite, cela semble la solution la plus faisable. Merci!

Les gens peuvent fournir la meilleure solution, ils sauront quel problème exact votre programme est censé résoudre.

Existe-t-il une loi de distribution des clés?

La machine à très faible puissance de traitement a-t-elle un nom?

3 Réponses :

3
votes

Sans plus de contexte sur votre carte,

si vous avez l'intention d'utiliser beaucoup de clés, un grand tableau comme suggéré précédemment serait assez facile à gérer car il n'y aurait pas de collisions, mais si vous n'allez pas utiliser toute la mémoire, cela pourrait être un gaspillage .

si vous avez l'intention d'utiliser une bonne quantité de données, mais pas assez pour qu'il y ait trop de collisions de hachage, std :: unordered_map a amorti les recherches O (1), et si vous ne vous souciez pas de l'ordre, elles sont stockés dans, cela pourrait être une bonne estimation.

si vous n'utilisez pas beaucoup de données et que vous avez besoin qu'elles soient flexibles, std :: vector est un bon choix

Comme tout ce que nous savons, c'est qu'il s'agit d'une carte uin16_t à uint16_t, il n'y a pas de meilleure réponse.

0 commentaires

3
votes

Le nombre total d'articles est inférieur à 500

L'insertion n'est effectuée qu'une seule fois

Conservez un tableau de taille fixe (500) de paires clé-valeur plus un "nombre d'éléments valides", si la taille réelle n'est connue qu'au moment de l'exécution; remplissez-le avec les données et triez-le; alors vous pouvez simplement faire une recherche binaire.

Étant donné que les éléments sont peu nombreux, en fonction du processeur spécifique, il peut même être plus pratique de simplement faire une recherche linéaire (peut-être en gardant les éléments les plus utilisés en premier si vous avez des indices sur les valeurs les plus fréquemment recherchées) .

0 commentaires

1
votes

Habituellement, un arbre binaire ( std :: map que vous utilisez actuellement) offre des performances adéquates. Votre budget CPU doit être vraiment petit.

Une approche de recherche binaire ne sera probablement pas beaucoup plus rapide. Une table de hachage ( std :: unordered_map ) pourrait être une solution.

Assurez-vous simplement de la dimensionner correctement afin d'éviter le ressassement et de rester juste en dessous de 1,0 facteur de charge. P >

std::unordered_map<uint16_t, uint16_t> m(503); // 503 is a prime
m.emplace(123, 234);
m.emplace(2345, 345);

std::cout << m.find(123)->second; // don't use operator[] to avoid creating entries
std::cout << m.find(2345)->second;

Pour vérifier la qualité de la fonction de hachage, parcourez tous les buckets en appelant bucket_size () et additionnez tout ce qui est supérieur à 1 (c'est-à-dire une collision).

0 commentaires