Comment by geokon | Hacker News Reader

Comment by geokon | Hacker News Reader

Parent Full thread

Thank you for the detailed response! Really thought provoking. It wouldn't occur to me to write code like this. It seems like it'd be harder to parse than an imperative index-based solution, but I'm not sure. Do you find it easy to immediately grok? I'm figuring it's just familiarity

- What's the nested loop in the first solution that you've avoided? The `reduce`? the `count`?

- `conj` feels very Lispy (I mean in contrast to Clojure, not C++) .. Isn't it going to have to run down the list every time to add an item?

My outstanding concerns are what I think are the constant coercion to lists/vectors. You also in effect know the result's size, but your runtime/compiler doesn't know that. So you aren't preallocating `memo` and it feels .. wrong haha

Just curious to hear your thoughts :)

Its probably impossible to keep everything so nicely abstract and composable, but I wish it was smoother to just work with arrays, with random access. The current way of dealing with array is always a bit unwieldy in Clojure. And everything coerced to lists. Working with vectors, with mapv filterv etc is helpful, but they don't have random access so it's not always the solution you want.

> It seems like it'd be harder to parse than an imperative index-based solution, but I'm not sure. Do you find it easy to immediately grok?

These examples are incredibly easy to grok. It takes me a lot longer to grok any index based solution ;-) Especially handling nils, missing indices, checking bounds... you quickly get buried in obvious issues that aren't a concern in clojure.

If it's more complicated, I use comments like the first example. I would say that when grokking more complicated loops, you definitely read it slower on a per character basis, but as I've stated elsewhere I don't think you're grokking the functionality any slower.

> What's the nested loop in the first solution that you've avoided? The `reduce`? the `count`?

Correct, reduce is a loop

> `conj` feels very Lispy (I mean in contrast to Clojure, not C++) .. Isn't it going to have to run down the list every time to add an item?

No, vectors are closer to hash-maps than lists. There are two main sequential collections in clojure, lists and vectors. Lists are O(n) to append, vectors are O(1). Lists ore O(1) to prepend, I'm not actually sure the perf characteristics of prepending to a vector.

> My outstanding concerns are what I think are the constant coercion to lists/vectors.

There is only one coercion from a vector to a list in the code (the first time `rest` is called on the input vector). That's if your input was a vector to begin with. Chances are it will be a list. Also, I'm not sure it's even technically coercion in the computer science sense.

> You also in effect know the result's size, but your runtime/compiler doesn't know that. So you aren't preallocating `memo` and it feels .. wrong

This is not a concern in JavaScript (it always preallocates a bunch of memory for every vector IIRC) and I'm not sure the Java implications, but given the performance people get out of clojure I'm sure it's not an issue ;-)

> The current way of dealing with array is always a bit unwieldy in Clojure. And everything coerced to lists. Working with vectors, with mapv filterv etc is helpful, but they don't have random access so it's not always the solution you want.

I can count on one hand the number of times I use nth in my project. To me it's crazy that people build solutions based on random access XD

That being said random access in O(1) on vectors, including those returned from filterv and mapv (technically O(log32n))

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

  (recur (subvec coll 1) …)

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

Reply on news.ycombinator.com