Hacker News Reader

Comment by cogman10 | Hacker News Reader

The one benefit of n^2 is it is really easy to do without any additional memory or data structure requirements.

To make an n^2 algorithm n (or n log n), you pretty much always need to add in some constant time or logarithmic data structure. That requires tracking that structure, usually generating a good key, etc.

I'm not saying that's really all that extreme. It just means your previous 5 line algorithm will often "bloat" to 10 or more lines with a new concept to track. This is where I see some saying "not elegant".

View on HN

That still makes no sense. The GP is literally just talking about switching from an association list to a hashmap:

> Being written in a functional language meant that using association lists (linked lists for key/value) was very natural. […] After changing all the places to use a hash table it again ran in sub-second, although the code was nowhere near as elegant.

You're not tracking more things (just tracking a hashmap instead of a list), you're not generating anything different, you don't have any new concept to track.

All I'm asking is where the apparently significant loss of elegance would come from.

> apparently significant loss of elegance would come from.

In a word, you're losing a persistent data structure[1]. And this can go beyond just loss of elegance. Sometimes, functional programs will depend on immutability of data structures for performance optimizations and even for functionality (like keeping a version history).

1. https://en.wikipedia.org/wiki/Persistent_data_structure

When was this story from? From my limited knowledge, I think persistent hashmaps have been available since Clojure 1.0 (2009) or before? (hash-map, https://clojure.github.io/clojure/clojure.core-api.html#cloj...).

He was working in OCaml, which even now isn't fortunate to have a persistent O(1) hashmap like Clojure (and Scala, I think) does in the standard library.

It's true that there are a few 3rd party implementations that I've noticed before, but not sure how robust and well-tested these are. I'd hesitate to use them or something I wrote in production without careful review.

In any case, persistent HAMTs are a relatively new phenomenon that are just starting to catch on, and this story is described as being "back in the day". It's unlikely this option was available to him even if he were willing to write an implementation himself or use an untested 3rd-party implementation.

Maybe one will be added eventually to one of the OCaml standard libraries, which would be great.

I am not OP but I definitely have been in similar circumstances where an algorithm became slightly more complex when adding a hash map to cover performance issues with a list.

A trivial example, I recall about 1 month ago calling it out on a Javascript code review where someone was doing a `someList.find(x => x === "something")` inside a loop creating O(n^2) complexity. Rather than change the entire codebase wherever `someList` is used into a new type it is often easier just to suggest we build a Set (linear on length of `someList`) before the loop and use that for lookups within the loop (constant).

Of course, I am talking about circumstances clearly outside of your original model of OPs description. I am tracking more things (the new Set). However, I realize that to give the full context as to why the type of `someList` from my trivial example _couldn't_ be changed easily and why creating a new Set was the most prudent option would require a comment even longer than this essay. So I give OP the benefit of the doubt that he was in a similar situation where using the hashmap everywhere was either difficult or impossible.

Not OP, but I'm guessing it's because linked lists are recursive and hashtables are not, so in a functional programming language you can do lots of clever things in a recursive way.

Reply on news.ycombinator.com