Comment by geokon
1 day ago
Oh good point on the hashmapiness of vectors, I forgot about that. That would really change the calculus here.... buuuut
> There is only one coercion from a vector to a list in the code (the first time `rest` is called on the input vector)
So actually.. the whole thing is operating on linked lists.. Is that like a "yikes" moment..? No happy clever vectors? It does seem to still work fine in this case, b/c we pop from one list and append to another and the example is simple.. but generally you want the O() guarantees of vectors or arrays
I'm also a bit surprised reduce is going to give you so much overhead, and destructuring doesn't. It really hardcodes the function to a window size which is a shame.. Last I had to optimize a hot loop in Clojure I found all destructuring terrible for perf (but I think it had to do with type boxing)
> I can count on one hand the number of times I use nth in my project.
Random access is sometimes necessary, but like you say hash-like-vectors cover you here okay. I guess arrays are more about having contiguous memory access. It generally gives you much better cache locality and it will typically make a very sizeable performance difference in a hot loop
Well it’s only iterating on lists because I’m recurring with a function that returns a list. I could use
If I needed to maintain the vector throughout the loop. However you need to change your base case and there’s no reason to have a vector at all in this case.
There is a reason most of the Clojure core functions return lists and not vectors. When you start learning Clojure, you use vectors for everything — after a while you realize how sufficient a list is for 90% of programming.
Also, I believe you could still get the performance guarantees and dynanicism with a dotimes and a volatile. You can definitely get it using nth on the remaining collection with a conditional if you don’t mind a bit of verbosity. Regardless of the goalposts, I promise you there is an ergonomic solution ;-)
I've been writing it for >5 years and I still reach for vectors haha. I think it's my C++ background which makes me a bit allergic to lists. The reality is that if I moved more transducer based solutions this would be a non-factor most of the time. (unfortunately this example doesn't suit transducers very well)
I gotta use transducers, lists and benchmarking more..
Thanks for sharing how you approach these problems