Hacker News new | ask | show | jobs
by lostcolony 1544 days ago
Yes and no.

Ultimately, is the Big O scale going to be larger for certain cases? Yes. Is it going to matter? Maybe. Maybe not. The point the original comment is making is that the author seems unaware these data structures even exist; the fact he was having O(n) operations and found them to be too slow tells us nothing about the reasonableness of the O(logn) option for his use case. He mentioned using a 30k byte array; that's the difference between 30k operations, and 15. Cutting it from 15 to 1 is probably not going to be that meaningful; certainly not compared with the first jump.
2 comments
zodiac 1544 days ago
That's a good point.

I wonder if the problem is that efficient persistent arrays aren't in racket's standard library (there are some third-party libraries implementing them though). Since racket isn't a "pure FP" language, they include cons-arrays and mutable vectors, and I imagine they felt that there wasn't a need to include efficient persistent arrays in addition to those.

link
lostcolony 1544 days ago
Sort of - consider when Lisp originated. The heritage/age comes from a time before the research in persistent data structures happened, or even the issues with mutability were fully known. Because of that, idiomatic Lisp tends to be mutable, and no one is writing a new Lisp who isn't already familiar with another one. That's not to say immutability isn't worthwhile there, or that no Lisp standard libraries support it, but mutability tends to be the default assumption from what I've seen.
link
phyrex 1544 days ago
I don’t know about that; clojure was specifically created with persistent data structures in mind, and it’s definitely as much a lisp as racket is
link
lostcolony 1543 days ago
I inserted 'tends' everywhere intentionally.
link
pbiggar 1543 days ago
In addition, the O(logN) only comes into play if you are truly accessing only one item. If you're accessing more you are either reading the whole list (O(N) in total, O(1) per item), or a sublist (in which case it's O(logN) once to get/update the k item sublist and O(k) to operate on it).

If you are accessing just one item, the O(logN) cost is likely dominated by some other cost (eg the user clicking a button, making a web request, etc).

link