J'essaie de créer une carte littérale avec les clés déterminées à partir d'une fonction aléatoire: tandis que le lecteur semble traiter la clé comme une liste non évaluée. Je ne trouve aucun détail à ce sujet dans la documentation. Y a-t-il quelqu'un qui peut m'aider à comprendre cela un peu plus?
4 Réponses :
Je ne connais pas la réponse à la question sur le lecteur, mais une manière plus sûre de construire cette carte de hachage serait de vous assurer que les clés sont différentes. Par exemple:
Non efficace pour la grande N, a o (n) complexité, devrait être O (1).
@Leongrapenthin où viennent votre exigence?
Efficacité. Si la génération de deux nombres aléatoires distincts dans une plage de 0-N a une complexité linéaire O (N), l'algorithme introduit des frais généraux inutiles au problème.
@Leon Cet exemple n'est pas optimisé pour les grands nombres, puisque le OP n'exigeait pas cela. Ce n'est pas incorrect. Cependant, quelle est la complexité de votre exemple pour n clés / valeurs? Comme il y a du hasard en jeu, je ne suis pas si sûr. Comment est-ce O (1) quand même?
L'exemple ci-dessus évite de générer des doublons et de les supprimer plus tard. On pourrait affirmer qu'il est plus efficace dans le cas où vous avez besoin de numéro proche ou égal à N Key / Vals pour N dans l'expression (plage n) .
@Leongrapenthin De toute façon, merci d'avoir soulevé la complexité. Cela m'a fait penser à la complexité de votre code. Je me demande comment vous pouvez réclamer O (1). Je suppose que la complexité doit être exprimée en deux ou trois variables (la quantité de clé / vals, le nombre 5 soulevé à une variable et la répartition du risque de duplicats, où, dans certains cas, votre exemple est plus efficace et dans certains cas, la mine si plus efficace. J'ai posé une question sur la complexité de votre exemple dans une autre question ici: Stackoverflow.com/questions/40692742/... Pas si merci pour le Downvote.
@Leongrapenthin let n est la quantité de touches à générer aléatoirement à partir d'un pool de 0 .. M-1 numéros. Le nombre attendu de tirage dans votre algorithme devient alors N × (HN-HN-J). Plus de détails ici: MATH.StaCKExchange.com/a/2022030/391129 . o (1) est clairement faux. Seulement pour les valeurs n << m approche O (n) .
@Leongrapenthin d'autre part, l'algorithme ci-dessus effectue toujours dans O (n) temps. Notez que collection.shuffle est o (m) , m étant la taille de la piscine et prenant le premier n Articles de Code est O (n) qui fait O (m + n) . Parce que n <= m nous avons au plus o (2m) qui est juste o (n) . Donc, l'algorithme ci-dessus est O (n) , où votre algorithme est au mieux O (n * journal (n)) .
Bien sûr, je parle de n comme la limite supérieure exclusive de l'intervalle aléatoire, pas le nombre de clés. Votre solution repose sur la génération de tous les entiers entre 0 <= i
Vous devez prendre en compte le nombre de clés
J'ai pris en compte le nombre de clés:
@Leongrapenthin Dans ce cas, la quantité attendue des nombres aléatoires générés est
Qu'est-ce que tu impliquas?
n et la limite supérieure de l'intervalle m . Lorsque n est proche de m , l'exemple ci-dessus fonctionne mieux (en général, pas dans ce cas concret). Il suffit de regarder le tableau ici: - Stackoverflow.com/questions/40692742/... Veuillez lire également: -
2 .
2.25 , légèrement plus que n = 2 .
tout produit par le lecteur est inévalué. C'est une idée principale derrière le lecteur: elle se lit comme des données avec une interprétation minimale à aucune. Le lecteur donne la carte inévaluée au compilateur.
Le lecteur fonctionne en construisant la carte progressivement via Assoc ou conjoint. Toutefois, dans le passé, cette approche aurait produit un résultat encore plus étranger pour votre code: Cet article décrit des lecteurs de style LISP dans un peu plus de détails: http://calculist.org/blog/2012/04/17/homoiconicité-isnt-the-point/ {(rand-int 5)) "adieu"} . C'est-à-dire que les règles d'association normales appliqueraient: la dernière paire de valeurs clés a ajouté des victoires ajoutées. Les gens ont couru dans ce problème, alors le lecteur effectue maintenant un contient un Vérifiez avant d'ajouter progressivement des valeurs.
Merci. Bonne explication.
Marcher à travers la source du compilateur de Clojure, j'ai trouvé ce qui suit:
Il est classe code LispReader code> qui contient classe imbriquée L'évaluation de toutes les formes Clojure est faite dans MapReader code> responsable de la lecture de la carte littéraux. C'est la méthode invoke code> lit les formulaires de clojure entre { code>, } code> symboles et renvoie une carte ( des formulaires de clojure em>) par em>) par appelant RT.map code> une méthode> p> li>
rt.map code> appelle persisterhashashmap.createwithCheck code> Où vérification réelle des touches dupliquées est effectuée . Depuis que nous construisons carte de formes Clojure em> le chèque déclencheront même s'il y a deux mêmes formes qui évaluent à différentes valeurs (comme dans votre exemple). P> li>
compilateur code> classe, en particulier les formulaires de carte sont évalués dans sa classe imbriquée MAPEXPR code> . Il méthode de eval code> évalue les clés et les valeurs de la carte et construit à nouveau une carte persistante à l'aide de rt.map code>. Donc, vérifier les clés dupliquées seront effectuées par rapport aux valeurs évaluées aussi bien, qui est la raison pour laquelle le code suivant également échouer: p> li>
OL> (let [x :foo y :foo]
{x :bar y :baz}) ;; throws duplicated key exception
Gagnant d'une réponse!
Je pense que vous avez répondu à votre propre question à la raison pour laquelle le chèque est dans les deux endroits - le lecteur crée une carte (qui pourrait avoir des touches en double) et la carte évaluée peut également avoir des touches en double.
Très bonne réponse. Merci @Olegthecat
Vous êtes correct en ce que le lecteur n'évalue pas la carte.
N'oubliez pas que cette évaluation se produit après la lecture. P>
de la Documentation de référence de lecteur de clojure : p>
Cela dit, la plupart des programmes de clojure commencent la vie en tant que fichiers texte, et c'est la tâche du lecteur d'analyser le texte et de produire la structure de données que le compilateur verra. Ce n'est pas simplement une phase du compilateur. Le lecteur et les représentations de données de clojure ont des utilités à proximité dans de nombreux contextes les mêmes que l'on pourrait utiliser XML ou JSON, etc. P>
On peut dire que le lecteur a une syntaxe définie en termes de caractères, et la syntaxe de la syntaxe définie en termes de symboles, de listes, de vecteurs, de cartes, etc. Le lecteur est représenté par la fonction Lecture, qui lit le formulaire suivant ( Pas de caractère) à partir d'un flux et retourne l'objet représenté par ce formulaire. P> BlockQuote>
L'évaluateur a besoin de la carte inévaluée pour la traverser et d'évaluer ses clés et ses valeurs. Si cette carte a le même formulaire plus d'une fois en tant que clé, il s'agit d'une carte de carte non valide. P>
Vous pouvez utiliser la fonction
hachage code> la fonction p>(zipmap (distinct (repeatedly #(rand-int 5))) ["hello" "goodbye"])
Merci. Grande réponse @ Leon-Grapenthin
@stuartrexking merci, veuillez reconsidérer l'accepter. La réponse que vous avez acceptée s'appuie sur des détails de mise en œuvre non documentés qui sont sujettes à modifier et ne touchent pas l'aspect de la conception linguistique qui est essentiel pour répondre à la question.
groups.google.com/d/msg/clojure/ylvelqu6gaqq/mzoeg0yg37qj/a >
Merci pour toutes les grandes réponses. Combinés ensemble, ils répondent à la question.