Thanks Gary, Leif, Alex! I suspected memoization might be the way to go—the leap I needed to make was: writing my own data constructors.
On Monday, May 5, 2014 9:10:40 AM UTC-4, Alex Miller wrote: > > To clarify slightly, the Java Language Specification section 5.1.7 > requires that the implementation cache *boxed* ints from -128 to 127, > boolean true/false, and characters from \u0000 and \u007f. Because Clojure > defaults to boxing in many cases you'll see the same effect. > > The persistent collections do go through factories and already cache one > special case: empty list/vector/set/map. This is also where the choice is > made as to the type of persistent map (array or hash impl) based on size ( > https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java#L1457 > ). > > I think in general, there is not enough commonality across programs for > the cost of the check to be more costly than the benefits to be saved in > memory so this is not something Clojure would ever do generically. But, if > this is tradeoff is important to you, then creating your own factory > function for collections and memoizing it would be a good way to achieve > that. > > > On Sunday, May 4, 2014 10:21:28 PM UTC-5, Leif wrote: >> >> >> The general technique in lisp is called hash consing (a.k.a. flyweight >> pattern, a.k.a. interning). Java strings, clojure symbols, and keywords >> are interned. And small integers, apparently. >> >> The basic idea is to create memoized versions of all the data >> constructors and only use them. This is basically what you did in your >> example and what Gary suggested. So, if you truly wanted something >> general, you'd probably have to reimplement a lot of clojure.core, or >> restrict yourself to a small number of constructor fns. >> >> If the vectors in your example are the only composite structure that >> needs sharing, and they represent points, say: >> >> (def mk-point (memoize (fn [x y] [x y]))) ; obviously lots of options >> here (caching strategy, weak refs) >> >> (def m1 {:a (mk-point 1 2)}) >> >> (def m2 (assoc m1 :b (mk-point 1 2))) >> >> (identical? (m2 :a) (m2 :b)) ; => true >> >> If the maps themselves need to be shared, you'll have to make your own >> version of assoc, dissoc, maybe conj & into, etc etc, and remember to >> always use them. It could get complicated. >> >> --Leif >> >> On Saturday, May 3, 2014 10:27:29 PM UTC-4, Mike Fikes wrote: >>> >>> Are there common techniques or idioms for achieving structural sharing >>> when composing data where equivalences exist? >>> >>> (My motivation is to reduce heap usage for a particular problem I'm >>> working on that involves a lot of repeated data.) >>> >>> As a specific example, consider sharing equivalent map values: >>> >>> (def m1 {:a [1 2]}) >>> >>> (def m2 (assoc m1 :b [1 2])) >>> >>> >>> (identical? (m2 :a) (m2 :b)) >>> >>> ;; => false >>> >>> >>> For this simple example, I can force sharing by introducing a variant of >>> assoc which looks at existing values: >>> >>> >>> (defn assoc-id [map key val] (assoc map key (get (apply hash-set (vals >>> map)) val val))) >>> >>> >>> And using it results in a map with two identical values: >>> >>> >>> (def m3 (assoc-id m1 :b [1 2])) >>> >>> >>> (identical? (m3 :a) (m3 :b)) >>> >>> ;; => true >>> >>> >>> But, of course, this approach could get to be expensive and/or unwieldy >>> if not done carefully. >>> >>> >>> So, I was wondering if there are general techniques in this area. I'm >>> sure I'm not the first to come across it. We already get this >>> automatically for boxing of small integers: >>> >>> >>> (identical? 5 5) >>> >>> ;; => true >>> >>> >>> (identical? 500 500) >>> >>> ;; => false >>> >>> >>> So I suppose I'm essentially looking for the same idea but for larger >>> non-primitive "values". >>> >>> >>> >>> -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
