La documentation de MATH.COMBINATORICS STATS que toutes les fonctions renvoient des séquences paresseuses.
Toutefois, si j'essaie de courir Sous-ensets avec beaucoup de données, P>
% lein repl nREPL server started on port 61774 REPL-y 0.1.10 Clojure 1.5.1 => (require 'clojure.math.combinatorics) nil => (last (clojure.math.combinatorics/subsets (range 20))) OutOfMemoryError Java heap space clojure.lang.RT.cons (RT.java:570) or OutOfMemoryError Java heap space clojure.math.combinatorics/index-combinations/fn--1148/step--1164 (combinatorics.clj:64)
5 Réponses :
Le problème est que sous-ensembles code> utilise MAPCAT code> et MAPCAT code> n'est pas assez paresseux car il utilise Apply qui réalise et contient certains éléments être concaténé. Voir une très belle explication ici . Utilisation de la version Lazier MapCat de ce lien dans les sous-ensembles doit résoudre le problème: (defn my-mapcat
[f coll]
(lazy-seq
(if (not-empty coll)
(concat
(f (first coll))
(my-mapcat f (rest coll))))))
(defn subsets
"All the subsets of items"
[items]
(my-mapcat (fn [n] (clojure.math.combinatorics/combinations items n))
(range (inc (count items)))))
(last (subsets (range 50))) ;; this will take hours to compute, good luck with it!
Je m'attendais à ce que la bibliothèque ait une utilisation constante de la mémoire. Je peux augmenter xmx à 4 Go, mais cela peut à peine gérer 50 éléments de la gamme. Je souhaite créer des sous-ensembles d'ensembles avec 1000 éléments+.
Quelle version de Java utilisez-vous?
J'exécute Java version "1.6.0_45" sur un Mac OS X en 64 bits
En l'absence d'arguments de ligne de commande, les paramètres de taille du tas de démarrage d'une JVM sont déterminés par divers ergonomie Les valeurs par défaut (JDK 6) sont Mais vous pouvez forcer une valeur absolue à l'aide du -xmx et -xms args
Vous pouvez trouver plus de détails ici
La définition de XMX n'est pas le problème. J'essaie de comprendre pourquoi cette fonction prend plus de mémoire qu'elle ne devrait.
Vous souhaitez calculer l'ensemble de puissance d'un ensemble avec 1000 éléments? Vous savez que cela va avoir 2 ^ 1000 éléments, non? C'est si grand que je ne peux même pas trouver un bon moyen de décrire à quel point c'est énorme. Si vous essayez de travailler avec un tel ensemble, vous pouvez le faire de manière paresseuse, votre problème ne sera pas de la mémoire: ce sera le temps de calcul. Disons que vous ayez un supercalculateur avec une mémoire infinie, capable de traiter un billion de dollars par nanoseconde: il s'agit de 10 ^ 21 articles traités par seconde, soit environ 10 ^ 29 articles par an. Même ce supercalculateur prendra beaucoup plus de temps que la durée de vie de l'univers pour travailler à travers les articles de Je dirais donc, arrêtez de vous inquiéter de l'utilisation de la mémoire de cette collection et de travailler sur un algorithme qui n'implique pas de marcher à travers des séquences avec plus d'éléments que des atomes dans l'univers. (sous-ensembles (plage 1000)) . .
Vous avez absolument raison. Le calcul d'une grande solution définie avec des sous-ensembles prendra des âges et n'est pas une option viable dans une application réelle. Toutefois, avoir une version de sous-ensembles non sujette à une utilisation constante de la mémoire serait importante pour les applications avec un cas d'utilisation plus réaliste.
Ce problème a été soulevé sur le ticket du projet suivant: Clojure Jira: OutofMemoryError avec Combinatoriques / sous-ensembles . Là, vous pouvez trouver un patch par Andygerhut. Cela a fonctionné pour moi. Notez que le patch est différent du Variation MAPCAT suggérées par une autre réponse .
Le problème n'est ni avec RéponseDani's Réponse , où il réinstalle Si vous examinez de près, Dani et l'auteur de cet article implémentent pour démontrer que le problème n'est pas lié à La paresse complète dans le code ci-dessus est réalisé en réimpliquant la fonction code> mappe code>. En fait, Le problème réel est que appliquer code>, ni avec concat code>, ni avec mapcat code>. MAPCAT code> entraîne accidentellement la répartition du problème, mais le raisonnement derrière celui-ci n'est pas correct. En outre, sa réponse pointe sur un article, où l'auteur dit "Je crois que le problème réside dans l'application" em>. Ceci est clairement faux, comme je suis sur le point d'expliquer ci-dessous fort>. Enfin, le problème à la main n'est pas lié à Cet autre a >, où l'évaluation non paresseuse appliquer code>. p> MAPCAT CODE> SANS L'UTILISATION DE LA FONCTION CODE> MAP CODE>. Je montrerai dans l'exemple suivant que la question est liée à la manière dont la fonction mappe code> est implémentée. P> appliquer ou CONCAT CODE> Voir la mise en œuvre suivante de MAPCAT code>. Il utilise à la fois concat code> et appliquer code>, il réalise toujours la paresse complète: p> MapCat code> est implémenté exactement la même chose comme dans clojure.core code>, mais cela fonctionne complètement paresseux. La mise en oeuvre de la carte code> ci-dessus est un peu simplifiée pour l'exemple de l'exemple, car elle ne prend en charge qu'un seul paramètre, mais même la mise en œuvre avec toute la signature variadique fonctionnera de la même manière: appliquer code> ni avec concat code>. En outre, nous avons montré que le vrai problème doit être associé à la manière dont la fonction mapper code> est implémentée dans clojure.core code>. Jetons un coup d'œil à celui-ci: P> (defn map
([f coll]
(lazy-seq
(when-let [s (seq coll)]
(if (chunked-seq? s)
(let [c (chunk-first s)
size (int (count c))
b (chunk-buffer size)]
(dotimes [i size]
(chunk-append b (f (.nth c i))))
(chunk-cons (chunk b) (map f (chunk-rest s))))
(cons (f (first s)) (map f (rest s))))))))
plage code> renvoie une SEQ chunked et est utilisé en interne par sous-ensembles code>. Le correctif recommandé par David James patchs sous-ensembles code> à nonchunk em> la séquence créé par gamme code> interne. p> p>
Fonctionne bien sans erreur OOM .. Quelle version de clojure que vous utilisez?
Fonctionne pour moi en utilisant Clojure 1.5.1 sur Linux avec des paramètres JVM par défaut.
Clojure 1.5.1 sur un Mac (installé avec homebrew). J'ai mis à jour la description du problème avec plus de détails.
@Agnur user100464 Que se passe-t-il lorsque vous exécutez (dernier (clojure.math.combinatorics / sous-ensembles (gamme 1000)))? Quels paramètres de -xmx avez-vous?