J'essaie de dériver un fichier graphviz décrivant une valeur structurée. Ceci est à des fins diagnostiques afin que je souhaite que mon graphique reflète la structure réelle en mémoire aussi étroite que possible. J'utilise ci-dessous pour mapper les valeurs des sommets de graphviz afin de pouvoir réutiliser un sommet lorsqu'une valeur comporte deux références entrantes ou plus: la documentation pour Je sais que Ocaml déplace les références autour, mais existe-t-il un proxy O (1) pour une identité de référence disponible dans OCAML? La réponse à Hashtable de variable mutable dans OCAML suggère non. Je suis déteste d'attacher des numéros de série aux états, car c'est le code de diagnostic Donc, toutes les erreurs que je fais faire, avoir le potentiel de masquer d'autres bugs. hashtbl.hash < / code> suggère qu'il convient à une utilisation à la fois lorsque stinidentity.equal = (=) et quand sincietitity.equal = (==) mais je voudrais assurer Cet accès à la table de hachage est aussi proche que possible de O (1) afin de ne pas avoir hashtbl.hash Marcher un graphique d'objet (potentiellement grand dans ce cas) à chaque recherche.
4 Réponses :
Si vous utilisez le mot "objet" dans le sens des types d'objet Vous pouvez également jouer avec <...> <...> , vous pouvez utiliser oo.id pour obtenir un unique Identité entière pour chaque instance. Sinon, la réponse à "existe-t-il une proxy générale pour l'identité de la valeur" est "non". Dans ce cas, mon conseil serait de commencer avec hashtbl.hash , évaluez s'il convient de votre nécessité, et de concevoir votre propre fonction de hachage.
hashtbl.hash_param (voir
Merci pour le pointeur. Par objet, je veux dire une valeur structurée, pas une instance d'un classe .
Je l'ai trouvé très délicat d'utiliser l'égalité physique pour faire hacher. Vous ne pouvez certainement pas utiliser quelque chose comme l'adresse de la valeur que votre clé de hachage, car (comme vous le dites) les choses sont déplacées par GC. Une fois que vous avez une clé de hachage, il semble que vous puissiez utiliser une égalité physique pour faire des comparaisons tant que vos valeurs sont mutables. Si vos valeurs ne sont pas mutables, OCAML ne garantit pas beaucoup de sens de (==). En termes pratiques, des objets immuables égaux (=) peuvent être théoriquement fusionnés dans un seul objet physique si le compilateur OCAML ou le temps d'exécution souhaite (ou inversement).
Lorsque je travaille à travers les différentes possibilités, je finis généralement à mettre un numéro de séquence dans mes valeurs lorsque j'ai besoin d'un identifiant unique. Comme le dit Gasche, vous pouvez utiliser oo.id si vos valeurs sont des objets de style OO réels.
Comme les autres, je pense que les identifiants uniques sont la voie à suivre.
Les identifiants uniques ne sont pas difficiles à générer en toute sécurité. Une solution consiste à utiliser un dossier privé comme suit. Il empêche les utilisateurs du module de copier le champ ID:
Je pense que votre SIG est manquant VAL Cree_T: ~ FOO: chaîne -> T
Désolé pour le piratage laid, mais j'ai fait quelque chose comme ça il y a quelque temps.
Le truc sur cela est de s'assurer que les valeurs ne seront pas déplacées en mémoire après l'insertion de la table. Il y a deux situations qui peuvent déplacer des valeurs en mémoire: copier du mineur au dernier tas de tas et de grandes compactage du tas. Cela signifie que lorsque vous insérez une valeur dans la table, il doit être dans le tas majeur et entre deux opérations sur la table, vous devez vous assurer qu'aucune compactage ne s'est produite.
Vérification de la valeur dans le tas mineur peut être fait à l'aide de la fonction C IS_YOUNG, si tel est le cas, vous pouvez forcer la valeur à migrer vers le tas majeur à l'aide de gc.minor ().
pour le deuxième problème, vous pouvez soit complètement désactiver compactions ou reconstruire la table sur les compacts. La désactivation de celle-ci peut être faite à l'aide de détecter qu'une compaction est produite peut être effectuée en comparant à chaque accès à la table renvoyée par Notez que vous devez désactiver le compactage avant d'accéder à la table.
Si vous désactivez le compactage, vous devez également envisager de modifier la politique d'allocation afin d'éviter la fragmentation non liée du tas. Si vous voulez quelque chose de vraiment laid dans les anciennes versions de OCAML (avant 4.00) Le compactage a maintenu la valeur dans le même ordre en mémoire, de sorte que vous puissiez implémenter un ensemble ou une carte basée sur une adresse physique sans vous inquiéter.
Je pense que je vais épuiser toutes les autres avenues avant d'essayer quelque chose qui dépend de nombreux détails de la mise en œuvre, mais merci d'avoir expliqué les détails pertinents du stock GC.
"La documentation de hashtbl.hash suggère qu'il convient à une utilisation à la fois lorsque ShistIdentity.equal = (=) et lorsque Stinidentity.equal = (==)" Ce n'est pas cependant.
hashtbl.hash a de nombreuses collisions lorsqu'il est associé à une égalité physique, ce qui vous permettait de l'utiliser, votre hashtable pourrait dégénérer dans une courte gamme de longues listes de clés physicymères structurellement égales.@Pascalcuoq, tout à fait juste. Par "approprié", je voulais dire "gérer remplacer et trouver invariant", et ne faisait pas référence à la conservation du nombre de comparaisons clés sur la constante de recherche.