Je sais que je peux utiliser diverses classes de conteneurs dans STL, mais c'est une overkilleuse et coûteuse à cette fin.
Nous avons plus de 1 M + utilisateurs en ligne et par utilisateur, nous devons maintenir 8 éléments de données 32 bits non liés. L'objectif est de
L'approche de la force brute serait de maintenir un dernier pointeur d'écriture et itérer (depuis seulement 8 articles), mais je recherche des intrants pour mieux analyser et mettre en œuvre.
Attendez-vous à des suggestions intéressantes en termes de modèle de conception et d'algorithme.
6 Réponses :
Vous voulez utiliser ici une combinaison de la table hachage et une liste donné nouvel élément doublement liée .
Chaque élément est accessible via la table de hachage qui contient la touche dont vous avez besoin plus un pointeur sur l'élément de la liste.
x , faire:
1. Ajouter x à la tête de la liste, sauvegardez le pointeur sous PTR .
2. Ajouter x à la table de hachage où les données sont stockées et ajouter PTR .
3. Si la liste est plus grande que celle autorisée, prenez le dernier élément (à partir de la queue de la liste) et supprimez-le. Utilisez la clé de cet élément pour le retirer également de la table de hachage.
Je ne sais pas que cela sera plus rapide qu'une recherche linéaire de force brute et une décalage, car il s'agit seulement de 8 articles 32 bits.
Merci, cependant, comme je l'ai mentionné, une liste ou une carte serait surchargée pendant 8 entrées et ne sera pas optimisée.
Si vous voulez une implémentation C du cache LRU, essayez cette lien
L'idée est que nous utilisons deux structures de données pour mettre en œuvre un cache LRU.
la file d'attente qui est implémentée à l'aide d'une liste doublement liée. La taille maximale de la file d'attente sera égale au nombre total de trames disponibles (taille du cache) .Les pages les plus récemment utilisées seront près de l'extrémité avant et les pages au moins seront proches de l'arrière. de
Un hachage avec numéro de page en tant que clé et adresse du nœud de la file d'attente correspondant en tant que valeur. de
Lorsqu'une page est référencée, la page requise peut être dans la mémoire. Si c'est dans la mémoire, nous devons détacher le nœud de la liste et l'amener à l'avant de la file d'attente. de
Si la page requise n'est pas dans la mémoire, nous apportons cela en mémoire. En mots simples, nous ajoutons un nouveau nœud à l'avant de la file d'attente et mettons à jour l'adresse du nœud correspondante dans le hachage. Si la file d'attente est pleine, c'est-à-dire que toutes les cadres sont pleines, nous retirons un nœud de l'arrière de la file d'attente et ajoutons le nouveau nœud à l'avant de la file d'attente.
Don Knuth donne plusieurs approximations intéressantes et très efficaces dans l'art de l'ordinateur de prorammer.
Liste d'auto-organisation II: Lorsque vous trouvez une entrée, déplacez-la d'une place; Supprimer de la fin.
[Les deux ci-dessus dans vol. 3 §6.1 (a).]
Un autre schéma implique de maintenir la liste circulaire avec 1 bit supplémentaire par entrée, qui est défini lorsque vous trouvez cette entrée et effacé lorsque vous passez le passé pour trouver autre chose. Vous commencez toujours à rechercher lors de la dernière place que vous avez arrêtée et si vous ne trouvez pas l'entrée, vous remplacez celui-ci avec le bit Effacement suivant avec celui-ci, c'est-à-dire qu'il n'a pas été utilisé depuis un voyage entier autour de la liste.
[vol. 1 §2.5 (g).]
Vous devez utiliser filtre de coucou qui est un Structure de données probabilistes qui prend en charge Fast Ensemble Test d'adhésion. C'est un Structure de données Based . Complexité du temps du filtre de Cuckoo: pour référence ici est comment fonctionne le filtre Cuckoo. pour LRU Vous pouvez utiliser l'horodatage dans votre fonction de hachage en gardant juste un Variable locale. C'est la meilleure approche pour les très grands ensembles de données à ce jour.
Étant donné qu'il n'y a que des entrées O (8) par utilisateur, toutes les opérations sont de toute façon O (1). Ce n'est pas un très grand ensemble de données, pas du tout.
@Msalters par utilisateur dispose de 8 entrées et la question indiquait qu'il y a plusieurs utilisateurs de 1 m, il y a donc 8 entrées de 8 x 1 m. C'est pourquoi c'est pourquoi je pense qu'il a un ensemble de données volumineux
Alors votre réponse n'est pas claire. Vous proposez de stocker 8 millions d'entrées dans un seul filtre de coucou? C'est certainement possible, vous venez de donner à l'utilisateur XYZ les entrées XYZ-0 à XYZ-7. Et vous pouvez gérer chacun d'eux pour déterminer lequel des 8 entrées est la plus ancienne et devra être remplacée. Cependant, c'est loin d'être efficace. Les frais de vue de la mémoire sont énormes et la localité de référence est entièrement absente.
Merci sahib. Il y a 1M utilisateurs et ils sont déjà dans la carte de hachage, donc une fois que nous avons reçu une entrée utilisateur, nous n'avons besoin que de gérer ces 8 entrées.
I Personnellement, je vais soit avec les listes d'auto-organisation telles que proposées par EJP ou, comme nous n'avons que huit éléments, il suffit de les stocker avec un horodatage séquentiellement.
Lors de l'accès à un élément, il suffit de mettre à jour l'horodatage, lors du remplacement. , remplacez celui avec l'horodatage ancien (une recherche linéaire). Ceci est moins efficace sur les remplaçants, mais plus efficacement sur l'accès (pas besoin de déplacer des éléments autour). Et ce pourrait être le plus facile à mettre en œuvre ... p>
Modification des listes d'auto-organisation, si elle est basée sur une structure de données de tableau: Bien sûr, sur la mise à jour, vous devez modifier plusieurs éléments (variante I) ou au moins Échangez deux d'entre eux (variante II) - mais si vous organisez les données comme tampon de bague, lors du remplacement, nous remplacons simplement le dernier élément avec le nouveau et déplacez le pointeur de la mémoire tampon sur ce nouvel élément: P>
d, e, a, c ^
Je suis d'accord avec les commentaires de la goutte et de Geza. La mise en œuvre directe prendra une lecture de la ligne de cache et provoquera une écriture de ligne de cache.
La seule question de performance ne reste que la recherche et la mise à jour de cette valeur 32 bits dans 256 bits. En supposant que le X86 moderne, la recherche elle-même peut être deux instructions: _mm256_cmp_epi32_mask trouve toutes les valeurs égales en parallèle, _mm256_lzcnt_epi32 Nombre de zéros de tête = nombre d'éléments non assortis plus anciens * 32. Mais même avec des opérations SIMD plus anciennes, les opérations de lecture / écriture de la ligne de cache domineront l'heure d'exécution. Et cela est à son tour dominé en trouvant le bon utilisateur. Qui à son tour est dominé par les E / S du réseau impliqué.
C ouc ++ ? La réponse peut varier de manière significative ...Ne vous inquiétez pas. 1M utilisateurs * 8 champ / utilisateur * 4 octets / champ = 32 Mo. Sur un processeur de serveur décent, des données pertinentes seront dans le cache L3 tout le temps. Tout algorithme est un overkill. Écrivez un code propre, simple, maintenable et passez à autre chose. Mieux vaut passer du temps (que vous perdrez sur des optimisations prématurées) sur la mise en œuvre d'une autre fonctionnalité pour vos utilisateurs.
Je recommande un tableau simple avec une recherche linéaire pour les éléments (et aligner les éléments à la limite de 32 octets, de sorte qu'il ne traverse jamais une ligne de cache). Stockez les éléments à l'ordre d'arrivée, s'il est plein, supprimez le premier et le décalage. Je ne pense pas que tout algorithme complexe sera nettement plus rapide.
Vous voudrez peut-être clarifier quelques détails. Je suppose que vous voulez dire "l'élément de données le plus ancien sur les 8 pour l'utilisateur donné". Et je ne sais pas si vous voulez l'âge de l'insertion, ou l'âge de la dernière recherche. LR U suggère ce dernier, mais votre mise en œuvre suggérée est la première.
@Drop merci, je suis d'accord. Notre mise en œuvre actuelle utilise une matrice linéaire mais explorait s'il existe de meilleures possibilités.