order of returned values from keys and vals

[Kent]

Hi,

Is it safe to assume that the values returned from (keys mp) and (vals
mp) will be in the same order? In other words, will (zipmap (keys mp)
(vals mp)) always return mp?

My experience has been that this does work, and it seems very
reasonable that it should work, but I don't see it documented anywhere
and I don't want to write a bunch of code that assumes it will work
and then have that code break in the future.

Thanks.
Kent

[Chouser]

keys, vals, and seq all do walk the map in the same order.

I believe this is promised, though I agree having it in the
docstring of keys and vals would be nice.

--Chouser
http://joyofclojure.com/

[Matching Socks]

Actually, http://dev.clojure.org/jira/browse/CLJ-1302 "keys and vals consistency not mentioned in docstring" was declined, with the comment "The absence of this property in the docs is correct. You should not rely on this."

[Sam Ritchie]

Looks like Rich just chimed in with:

"keys order == vals order == seq order "

Matching Socks

January 31, 2014 7:31 PM

Actually, http://dev.clojure.org/jira/browse/CLJ-1302 "keys and vals consistency not mentioned in docstring" was declined, with the comment "The absence of this property in the docs is correct. You should not rely on this."



On Wednesday, August 11, 2010 6:03:39 PM UTC-4, Chouser wrote:

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@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+u...@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+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--
Sam Ritchie (@sritchie)

Paddleguru Co-Founder
703.863.8561
www.paddleguru.com
Twitter // Facebook

[Justin Smith]

Realistically, how many situations are there where running keys and vals independently is preferable to running seq once and using the two element vectors that returns?

Usually this way one can avoid walking the whole thing twice.

(into {} (map (fn [[k v]] [k (inc v)]) {:a 0 :b 1})) is representative of the idiom I usually use. As a bonus, into uses transients, which can create the resulting structure in fewer cycles / less time.

[Ambrose Bonnaire-Sergeant]

zipmap could also potentially use transients (which would be a nice addition).

keys/vals are also lazy, so I would be surprised if there was any performance

difference with walking the seq "twice".

Thanks,

Ambrose

[Michał Marczyk]

On 2 February 2014 04:54, Ambrose Bonnaire-Sergeant <abonnair...@gmail.com> wrote:

zipmap could also potentially use transients (which would be a nice addition).

My patch for this has been waiting in JIRA since end of May 2012:

http://dev.clojure.org/jira/browse/CLJ-1005

Cheers,

Michał

[Justin Smith]

user> (class (keys {:a 0 :b 1}))

clojure.lang.APersistentMap$KeySeq

Are you sure PersistentMap$KeySeq is lazy? I don't really get how a lazy sequence over an associative would work in Clojure (at least as clojure exists now).

Pardon my ignorance but if this is producing a lazy result, how is it doing so?

https://github.com/clojure/clojure/blob/dff9600387b962f16fc78e6477e10e34651fd366/src/jvm/clojure/lang/APersistentMap.java#L134

[Michał Marczyk]

On 2 February 2014 05:14, Justin Smith <noise...@gmail.com> wrote:

Pardon my ignorance but if this is producing a lazy result, how is it doing so?

https://github.com/clojure/clojure/blob/dff9600387b962f16fc78e6477e10e34651fd366/src/jvm/clojure/lang/APersistentMap.java#L134

APersistentMap's KeySeq.create and ValSeq.create are pretty much equivalent to (map key entry-seq) and (map val entry-seq). The logic producing entry-seq lives in the individual map types and is indeed lazy.

Cheers,

Michał

[Ambrose Bonnaire-Sergeant]

Thanks Michał, voted.

Ambrose

[Ambrose Bonnaire-Sergeant]

It also might help to notice KeySeq defines first/next, but never explicitly walks the seq.

That's left to the user of the KeySeq.

Thanks,

Ambrose

[Chouser]

There's no substitute for measurement.

(defn maptest [f]
  (let [m (apply hash-map (range 40))]
    (time (dotimes [_ 100000] (f m)))
    (f m)))

(maptest #(zipmap (keys %) (map inc (vals %))))
; "Elapsed time: 1405.890766 msecs"
;=> {0 2, 32 34, 2 4, 34 36, 4 6, 36 38, 6 8, 38 40, 8 10, 10 12, 12 14, 14 16, 16 18, 18 20, 20 22, 22 24, 24 26, 26 28, 28 30, 30 32}

(maptest #(into {} (map (fn [[k v]] [k (inc v)]) %)))
; "Elapsed time: 1433.270362 msecs"
;=> {0 2, 32 34, 2 4, 34 36, 4 6, 36 38, 6 8, 38 40, 8 10, 10 12, 12 14, 14 16, 16 18, 18 20, 20 22, 22 24, 24 26, 26 28, 28 30, 30 32}

(maptest #(reduce-kv (fn [m k v] (assoc m k (inc v))) {} %))
; "Elapsed time: 649.452695 msecs"
;=> {0 2, 32 34, 2 4, 34 36, 4 6, 36 38, 6 8, 38 40, 8 10, 10 12, 12 14, 14 16, 16 18, 18 20, 20 22, 22 24, 24 26, 26 28, 28 30, 30 32}

These results are fairly robust in relation to each other for other sizes of smallish maps.

--Chouser

--
--Chouser

[Michał Marczyk]

That doesn't mean that we're not walking the seq twice, however. keys and vals work off of separate calls to seq on the map, which of necessity produce distinct seq objects (otherwise traversing a seq over a map would permanently increase its memory consumption).

[Justin Smith]

Excellent, thanks for the information.

I just did a benchmark of zipmap over keys and vals vs. into {} over a map, and despite my intuition, they are actually nearly identical in performance. So if zipmap were using transients zipmap with keys and vals would actually be the better performing option here.

user> (def testmap (zipmap (range 1000) (range 2000 3000)))

user> (crit/bench (zipmap (keys testmap) (map inc (vals testmap))))

Evaluation count : 150900 in 60 samples of 2515 calls.

             Execution time mean : 401.458681 µs

    Execution time std-deviation : 4.912358 µs

   Execution time lower quantile : 393.882254 µs ( 2.5%)

   Execution time upper quantile : 409.534676 µs (97.5%)

                   Overhead used : 2.203076 ns

Found 1 outliers in 60 samples (1.6667 %)

low-severe 1 (1.6667 %)

 Variance from outliers : 1.6389 % Variance is slightly inflated by outliers

nil

user> (crit/bench (into {} (map (fn [[k v]] [k (inc v)]) testmap)))

Evaluation count : 150060 in 60 samples of 2501 calls.

             Execution time mean : 400.684810 µs

    Execution time std-deviation : 3.489015 µs

   Execution time lower quantile : 395.127605 µs ( 2.5%)

   Execution time upper quantile : 407.132405 µs (97.5%)

                   Overhead used : 2.203076 ns

nil

[Michał Marczyk]

I'd expect

(persistent!

  (reduce-kv (fn [acc k v] (assoc! acc k (inc v)))

    (transient {})

    input-map))

to be the fastest solution.

Cheers,

Michał

[Michał Marczyk]

Oh, sorry, for some reason Gmail didn't alert me to some of the recent messages coming in while I was viewing this thread.

[Justin Smith]

In the same repl as the above benchmarks, and yes, this is definitely the best so far. I'll have to remember reduce-kv for future usage.

user> (crit/bench (persistent!

                   (reduce-kv (fn [acc k v] (assoc! acc k (inc v)))

                              (transient {})

                              testmap)))

Evaluation count : 369540 in 60 samples of 6159 calls.

             Execution time mean : 163.806692 µs

    Execution time std-deviation : 1.090315 µs

   Execution time lower quantile : 162.145827 µs ( 2.5%)

   Execution time upper quantile : 165.628330 µs (97.5%)

                   Overhead used : 2.203076 ns

nil