This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2017-12-06
Channels
- # adventofcode (181)
- # aws (6)
- # beginners (112)
- # boot (38)
- # cider (11)
- # cljs-dev (12)
- # cljsrn (2)
- # clojure (187)
- # clojure-greece (31)
- # clojure-italy (19)
- # clojure-new-zealand (1)
- # clojure-poland (1)
- # clojure-spec (20)
- # clojure-uk (114)
- # clojurescript (97)
- # core-logic (25)
- # cursive (3)
- # data-science (17)
- # datascript (3)
- # datomic (23)
- # defnpodcast (1)
- # duct (5)
- # emacs (3)
- # fulcro (299)
- # graphql (108)
- # jobs (1)
- # juxt (4)
- # lein-figwheel (7)
- # leiningen (1)
- # lumo (9)
- # nrepl (2)
- # off-topic (10)
- # om (2)
- # onyx (36)
- # pedestal (1)
- # perun (3)
- # re-frame (14)
- # reagent (12)
- # ring (2)
- # rum (11)
- # shadow-cljs (6)
- # spacemacs (4)
- # unrepl (8)
TIL.. max-key
Also, TIL: max-key
gives the last instance for which (k x)
is greatest
@borkdude same thing, a bit disappointed 🙂
I almost never use loop in Clojure, but for Advent of Code I used it a couple of times now
I got to use transient
for the first time today. I like it how you can do that inside a tight loop so you don’t have to do the whole functional way for something that you know is never leaving that function.
I did use quot
and rem
for better performance, wondering if that's wasted
yeah, that’s nice, but could you apply iterate to find the solution, as you had to compare the previous ones
it’s what I thought too, iterate is nice, but I can’t use it. I also have a next-state
fn
Of course, this only is possible because we have a small problem today — couldn’t do it with yesterday’s 20 million operations.
If you would only have to compare the last two solutions (as I initially thought) you could maybe do it like lazy fibonacci: https://en.wikibooks.org/wiki/Clojure_Programming/Examples/Lazy_Fibonacci
(count
(let [seen (volatile! #{})]
(take-while #(and (not (@seen %))
(vswap! seen conj %))
(iterate step [0 2 7 0]))))
yeah i did find that, but seems a bit unclear in the end. My takeaway was: if the value has IEditableCollection
, go for transient
unless you want to co-ordinate between multiple threads, in which case use volatile!
for speed and atom
if you need what atom brings.. sound accurate?
i'd be careful with volatile! in a multithreaded context, as vswap! is not atomic, concurrent vswaps will give unreliable results
Ah, I misread: > Volatiles are faster than atoms but give up atomicity guarantees so should only be used with thread isolation.
i think there was a check on volatiles to detect concurrent swaps, but they removed it to use it in transducers
ah, seems like: atoms - mutable, can be updated from multiple threads, guaranteed atomic volatiles - mutable, can be updated from multiple threads, but not atomic so be careful transients - mutable, require thread isolation
I would rephrase this as: - atoms: slowest, no caution required - volatiles: faster, but avoid concurrent updates - transients (or any non-synchronized data structure such as java.util.HashMap): fastest, but don't update after sharing to other threads
if each thread is only, for example, updating a specific index on an array I think it's safe.. but you'd best know what you're doing
https://gist.github.com/minikomi/0bf7bedb64767a832be172c5b0767d1e
Trying some things out, only the atom gives [1000 1000 1000 1000 1000]
every time.
you need to pass the result of transient operation around (for assoc!
, dissoc!
etc), like how you would use normal assoc
I just sat down with pen and paper for day 3 and I think I have a breakthrough lol. Love the aha moments of an interesting problem.
So it's not really equivalent to atom/volatile, in that you have to reassign it or use it in, say, a reduction where it's explicitly the updated version which is being passed around?
(let [t (transient {})]
(assoc! t :test 3)
(assoc! t :banana 4)
(persistent! t))
seems to work fine, but in some cases it might fail?https://clojuredocs.org/clojure.core/assoc! ooh, the docs explain well. thanks for the tip!
@minikomi this shows how it fails:
(let [t (transient {})]
(dotimes [i 1000]
(assoc! t i :test))
(persistent! t))
and for larger maps (> 10) it switches to a hash-map, so then assoc! returns a different object
e.g. (next-state [0 1 2 3 6 4 5 0]) => [1 2 3 3 0 5 6 1]
is hard to do with mapv, where you don’t have some state in the function
@mfikes I would if I could find a more elegant solution, but mapv
didn’t work… curious about other solutions.
I find this a creative way of finding part 2: https://github.com/EsthervdS/AdventOfCode/blob/master/day6/Reallocation.java#L52
@nooga I haven't hooked in any profiling tools, but ClojureScript has a simple-benchmark
core fn. See, for example http://blog.fikesfarm.com/posts/2017-11-18-clojurescript-performance-measurement.html
@nooga Can you try my input for comparison? https://github.com/borkdude/aoc2017/blob/master/resources/day6.txt
My solutions committed https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_06.cljc
https://github.com/mfikes/advent-of-code/blob/master/resources/advent_2017/day_06/input
@minikomi Yes, the behavior of max-key
is crucial if you happen to use it in this problem. Documented in Clojure and pending for ClojureScript https://dev.clojure.org/jira/browse/CLJS-2403
I haven't use loop
/ recur
yet in this year's solutions. (Probably to the detriment of ouright perf.)
not sure if you’ve incorporated this into your optimized solutions, but
(defn max-ndx [banks] (.indexOf banks (apply max banks)))
seems to be quite a bit faster than
(defn max-ndx [v]
(- (dec (count v))
(apply max-key (vec (rseq v)) (range (count v)))))
https://github.com/minikomi/advent-of-code/blob/master/src/advent/2017/day6.clj#L9-L17
first-max-pos
can be optimized using reduce-kv
(defn first-max-pos'
[nums]
(reduce-kv (fn [[_ max-val :as m]
k cur-val]
(if (> cur-val max-val)
[k cur-val] m))
[0 0]
nums))
runs 4-5x faster for me
just commited mine https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day06.clj
sorry didn’t see yours, I’ll check
cljs.user=> (time (dotimes [_ 10000] (first-max-pos [1 2 3 4 6 1])))
"Elapsed time: 146.985052 msecs"
; with reduce-kv
cljs.user=> (time (dotimes [_ 10000] (first-max-pos' [1 2 3 4 6 1])))
"Elapsed time: 33.089442 msecs"
cljs.user=> (time (dotimes [_ 10000] (get-indexed-max [1 2 3 4 6 1])))
"Elapsed time: 68.978079 msecs"
; using .indexOf
cljs.user=> (time (dotimes [_ 10000] (max-i-and-val [1 2 3 4 6 1])))
"Elapsed time: 42.277618 msecs"
so reduce-kv is fastest
the indexOf
solution has to go through the list twice
(defn get-indexed-max [memory-state]
(loop [idx 0
current-max [nil -1]] ;; no values below 0
(if-let [v (get memory-state idx)]
(recur (inc idx)
(if (< (second current-max) v)
[idx v]
current-max))
current-max)))
here was my first attemptmaybe if you get rid of the tuple allocations
@mikelis.vindavs TIL. I suppose it is meant to be a stable / public part of the API: https://github.com/clojure/clojurescript/blob/3b3db232711266f9f41c94c777084664d6d0b71b/src/test/cljs/cljs/seqs_test.cljs#L131-L147
console.time()
var max_idx, max_val=-1;
for (i = 0; i < 10000; i++) {
arr.forEach(function(i,v) {
if(v > max_val) {
max_idx = i; max_val = v;
}
})
}
console.timeEnd()
VM750:10 default: 22.593017578125ms
https://repl.it/repls/AwareOutgoingWolverine but really, it’s nothing special imo
(defn loop-nth [xs]
(let [size (count xs)]
(loop [i 0
maxi 0
m 0]
(if (< i size)
(let [v (nth xs i)]
(if (> v m)
(recur (inc i) i v)
(recur (inc i) maxi m)))
[maxi m]))))
is some 10% faster than reduce-kvAFAICT .indexOf
and .lastIndexOf
are so useful, that they were made to work in ClojureScript
Even crazy construct like (.indexOf (sequence (map inc) '(0 1 2 3 4)) 5)
work in Clojure and ClojureScript
I wonder if these test imply that they are stable / public https://github.com/clojure/clojurescript/blob/3b3db232711266f9f41c94c777084664d6d0b71b/src/test/cljs/cljs/seqs_test.cljs#L131-L168
Thanks for the tip @mikelis.vindavs, I've incorporated it https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_06.cljc
I was surprised that (merge-with + [0 1] {0 7 1 2})
produced a vector. I used it without thinking but then checked afterwards that this is true.
@mikelis.vindavs I looked at reduce-kv
but this won’t work: (first-max-pos' [-1 -2 -5])
, so I stayed with the current
the inputs are always positive
@mikelis.vindavs oh. well, then it works, but only for this puzzle 😉
but it could be made to work with negative ones by providing a different initial value
@bhauman I didn’t think of perf optimizations when I wrote mine, but ended up at 63 ms (on JVM that is). Now let’s see if I understand yours.
Hah, I could see another variation on this, where all solutions are submitted to a server which benchmarks and ranks them.
It seems you can optimize roughly for 3 things: 1. Get it done ASAP so you can get points 2. Write it elegantly so it is mantainable 3. Optimize the crap out of it
Added some println
s to @bhauman’s solution because I had trouble seeing what was going on, but now I get it:
start: [0 2 7 0]
acc i [0 2 0 0] 3
acc i [0 2 0 1] 0
acc i [1 2 0 1] 1
acc i [1 3 0 1] 2
acc i [1 3 1 1] 3
acc i [1 3 1 2] 0
acc i [2 3 1 2] 1
Clever, so it will loop 7 times updating each index by one, starting from the index after the max valueIn my solution I maintained the invariant that the sum of elements should always remain constant, because I had a bug in it that increased the sum
not much different than a loop, oh and I got it down to 93ms with transients but I don't see that as worth it
@bhauman Just for fun, I moved the (count …) to a let bound name, but it becomes slower, not faster … 🙂
@bhauman Yeah, I've concluded it only accidentally works:
(merge-with (fn [_ x] x) [0 3] {0 7 1 2} {0 3 2 32})
and
(merge [0 3] {0 7 1 2} {0 3 2 32})
don't produce the same result.can someone explain this to me? I don’t really get it
@mfikes is this because merge-with
is exploiting a more general interface like get
and assoc
on the first collection?
ah it’s just treating it as an associative collection, just like (assoc [:a :b :c] 1 :x)
works
interesting that (merge-with + [10 11 12 13] [100 101 102 103])
doesn’t work but (merge-with + [10 11 12 13] {0 100 1 101 2 102 3 103})
does
when dynamic typing and implementation details meet
Well, since I want to treat the memory banks as associative and have it work with merge-with
, I'm going to use maps instead of vectors.
Found a slight variation on bhauman’s next-state:
(defn redistribute [block]
(let [[position max-val] (first-max-pos block)
length (count block)]
(reduce (fn [block [p v]]
(update block p
+ v))
(assoc block position 0)
(->> (range (inc position)
(+ (inc position) max-val))
(map #(mod % length))
frequencies))))
This was where the desire to use (merge-with +
on a vector came from. (To avoid an explicit reduce
.)
The original bhauman version is twice as fast though! Provided that you use first-max-pos.. 40 ms now on my machine
It’s an interesting solution with frequencies
, but if focusing on perf, isn’t generating a whole sequence just to squash it down kinda slow vs just adding (quot n-to-distribute num-banks)
and then figuring out where to put the rest ?
it’s rather elegant though