Another Boost in the CryptoQuip Performance
Today I got an email from my friend about the times we were getting on the pattern function in the code - that function that turns the word into a sequence of ints that corresponds to the character pattern of the word. So we might have:
=> (pattern "see") [0 1 1] => (pattern "rabbit") [0 1 2 2 3 4]
At the time, my best code looked like this:
(defn pattern [word] (mapv (into {} (map vector (distinct word) (range))) word))
and the times we were getting just for this function were not as good as his version:
(defn pattern [word] (loop [p [] d {} n 0 f (first word) r (rest word)] (if f (if (contains? d f) (recur (conj p (d f)) d n (first r) (rest r)) (recur (conj p n) (assoc d f n) (inc n) (first r) (rest r))) p)))
On 1000 calls he was beating me by a couple of milliseconds - and it makes sense... he's building the map as he goes, and I took the time to build it up-front, and I'm paying the cost for it. The big cost is that I then have to run map again to use the map I just created. His code builds and uses the map at the same time.
So I was trying to think of a way to speed up the process, and I couldn't think of a simple way, and then I decided just to try a simple test - use the Java indexOf method to get the index on the distinct string and then return that. The code then becomes:
(defn pattern [word] (let [dw (distinct word)] (map #(.indexOf dw %) word)))
The times were startling:
cq.main=> (time (dotimes [_ 1000] (bob "bivteclnbklzn"))) "Elapsed time: 0.342 msecs" nil cq.main=> (time (dotimes [_ 1000] (bret "bivteclnbklzn"))) "Elapsed time: 3.605 msecs" nil
where bob is my new version with indexOf and bret is his version with the loop/recur.
A factor of 10x. Wow! Ten times faster. Make the string and use the inherent properly of the string and it's index to do the mapping. What a hoot! I have really enjoyed working on this with my friend.
When we put this into the web server, we get even better solve times:
[12:29:13.757:qtp1360409373-14] INFO cq.block - Finished match-up [8 words] in 1ms. [12:29:13.763:qtp1360409373-14] INFO cq.block - Finished solve in 7ms.
...just amazingly fun.