PurelyFunctional.tv Newsletter 318: Tip: Beware the order of keys in hashmaps
Issue 318 - March 18, 2019 · Archives · Subscribe
Clojure Tip 💡
Beware the order of keys in hashmaps
You cannot rely on key-value pairs in hashmaps coming out in the same order as they went in. The trouble is, when you test, it might appear that you can. It won't be until later, with a larger input, that the problem arises. But at that point, your mind has moved onto new problems, and you won't know where to look.
This tip is probably obvious to you, but just to make sure it's really clear, I'll demonstrate.
Maps may keep their order for small inputs
Here's some code, with a small input, that shows that the keys come out in the same order as they went in.
(keys (into {} [[:a 1] [:b 2] [:c 3]]))
;=> (:a :b :c)
In fact, I can go all the way up to 8 key-value pairs in a map on my machine and it still maintains the order:
(keys (into {} [[:a 1] [:b 2] [:c 3] [:d 4] [:e 5] [:f 6] [:g 7] [:h 8]]))
;=> (:a :b :c :d :e :f :g :h)
But adding a ninth scrambles them:
(keys (into {} [[:a 1] [:b 2] [:c 3] [:d 4] [:e 5] [:f 6] [:g 7] [:h 8] [:i
9]]))
;=> (:e :g :c :h :b :d :f :i :a)
Why do maps keep their order for small inputs?
Well, it's an implementation detail. Small maps are of type
PersistentArrayMap.
(type (into {} [[:a 1] [:b 2] [:c 3]]))
;=> clojure.lang.PersistentArrayMap
Large maps are of type PersistentHashMap.
(type (into {} [[:a 1] [:b 2] [:c 3] [:d 4] [:e 5] [:f 6] [:g 7] [:h 8] [:i
9]]))
;=> clojure.lang.PersistentHashMap
ArrayMaps happen to maintain order (though the interface does not
guarantee it). And at some point, associng one more key-value pair
will flip it over into a HashMap.
Why is this a problem?
Well, at small inputs, if you're doing interactive tests, it looks like you are getting a correct result. It looks like your algorithm is correct, even if you are relying on order.
The trouble is that we often use small inputs when we're testing. That testing will give you a false confidence. You'll move on to other areas of the code. And when things start breaking, you won't know where to look.
How to fix it
Well, it's not so easy. I suggest two habits.
- Think of all maps as unordered, like bags of stuff. You put stuff in a bag, shake it up, and things get mixed up.
- Always test with an input at lest 10 elements long. I usually do this test at the end, just to catch ordering problems.
Brain skill 😎
Y'all, we all need to practice a little bit more deliberate practice. Deliberate practice is when you practice with a purpose, and it is the key to mastery. We all write a lot of code, either at work or for school assignments, or even for fun. But are we focused on improving a particular skill?
In deliberate practice, you break down a large skill (say, Clojure programming) into smaller skills (paren management, IDE keystrokes, data structure usage, concurrency, etc). You then focus practice on that skill until mastery. Then you move on to the next.
How small should the skills be? Research shows that you want a skill you can master (achieve 95% accuracy) within 1-3 45-minute sessions (1 is better than 3). If you can't master it in that time, you need smaller skills.
At 95% accuracy, the skill is reliable and automatic. Under that, you can still do the skill, but only with effort. The trouble is, without pushing past the 95% limit, we'll have lots of skills that take a lot of effort. It's better to have a partial skill at 95% accuracy than a full skill at anything less. That's why it's important to break things down and focus on one at a time.
Also, you'll need to have a way of measuring your progress. How do you know how accurate you are? That's one place where a REPL really shines. It gives you really fast feedback to let you know you're on track.
Reference: Badass: Making Users Awesome by Kathy Sierra.
Action
Write down a skill you would like to learn. Could you master it in 45 minutes? Chances are, it's too big. Break it into smaller skills until you're confident that 45 minutes of practice will get you there.
Clojure Puzzle 🤔
Last two weeks of puzzles
When I got back from vacation, I was so happy to see so many great submissions to both puzzles.
Issue 316 drop every nth element
It's really amazing how concise these can be. See the submissions.
Issue 317 run-length encoding/decoding
There were some really great answers. See them here.
Thanks to all those who submitted.
This week's puzzle
generate combinations
If I have 4 flowers to choose from (#{:rose :lily :daisy :tulip}), I
can generate 4 different combinations of 3 flowers.
(#{:rose :lily :daisy}, #{:rose :lily :tulip}, #{:rose :daisy :tulip}, #{:lily
:daisy :tulip})
Write a function combinations that takes a collection of values and a
number of items to choose and generates all combinations of that size.
Example:
(defn combinations [coll n]
...)
(combinations #{:rose :lily :daisy :tulip} 3)
; => (#{:rose :lily :daisy}, #{:rose :lily :tulip}, #{:rose :daisy :tulip},
#{:lily :daisy :tulip})
Bonus points for clarity, interest, and efficiency.
As usual, please send me your implementations. I'll share them all in next week's issue. If you send me one, but you don't want me to share it publicly, please let me know.
Rock on! Eric Normand
PS ✍️
I have started recording a new course called Repl-Driven Development in Clojure. It's an important topic and there just isn't enough of a comprehensive take on the subject. Repl-Driven Development is where Clojure shines, and without it, Clojure can seem like a drag.
The course is available as of right now as part of an early access program (read serious discount). If y ou buy now, you'll receive updates to the course as new lessons come out. There is already 1.5 hours of video, and many more coming. If I had to guess, I'd say 6-8 hours total when I'm done. But I can't be sure. That's what the discount is for. As the course is fleshed out, the price will go up.
Of course, members of PurelyFunctional.tv will get the course as part of their membership for no extra cost. Just another benefit of being a member.
Check out the course. The first lesson is free.
