JeanPierre
Joined 16 years ago
Karma
997
Submissions
174
Member since
Mar 14
Recent submissions
Comment · 12 years ago
Agreed on the benchmarks – that's the next (and last) part on the list I'm going to do with this series.
And yes, of course, at some point, constant factors break into applications. Would it be better if add in a short comment on "practically O(1) for non-HPC applications", or would you phrase it differently to give it better context?
Comment · 12 years ago
I understand your concern, but I don't really think the problem is within Clojure people: When I started out explaining the structure to other people and that most operations have O(log n) runtime, people dismissed Clojure as being too slow for practical purposes. Part of this is because programmers, not Clojure devs in particular, connotate O(log n) with "much slower than O(1)". However, this data structure is incredibly much faster than the "O(log n)" people are generally used to.
And this is the problem. As you yourself say, most programmers usually associate/assume "Big-O notation is intended to describe how the time required for an operation grows as the number of items being handled gets large".
But formally, this is not the case at all. O(g(x)) tells you the that the worst case input to the algorithm will require less operations (usually operations, sometimes memory or other things) than the function g multiplied by some positive constant. g is usually determined by the size of the input. (This definition is also simplified somewhat, but it illustrates the problem)
We can say that ArrayLists.add have O(n) runtime and that quicksort have O(n²) runtime, but they both also have O(n³) and O(n!) runtime.
In addition, Big-O does not describe how the algorithm runs in the average case, or how frequent the worst case is. In and of itself, the Big-O notation tells us almost nothing about an algorithm – you barely conclude anything from it. I guess that is part of why it has become this very simplified term with a very wibbly-wobbly definition from time to time.
So when you're saying that calling it "practically O(1)" is lying, I agree if this was in an academic context. But for the average programmer (regardless of language!), O(g(x)) is usually thought of as the "worst case runtime for an algorithm". Since the actual runtime is – well – effectively constant, I considered it okay.
---
That being said, I have formally explained the persistent vector if you're interested in the academic version. The background chapter in http://hypirion.com/thesis.pdf should cover it.
Comment · 12 years ago
That's a red herring: You're asking why the majority of software is written in imperative languages instead of functional ones, which is a very complex question with very many factors. It is not an argument which invalidates nor counters the author's claim: Namely that "mostly functional languages" is unfeasible and only increases the bugs caused by side effects.
Comment · 12 years ago
Mori doesn't implement RRB-trees, thus doesn't support logarithmic concatenation.
Comment · 12 years ago
Constant time in practise is a notable difference from saying constant time.
I can always sort a 32-bit int array in worst case linear time using counting sort, which in theory is better than the worst case runtime of quicksort, O(n²). Is it better in practise? Of course not, the constant factor is just too high, both for time and memory.
Comment · 12 years ago
I've managed to do the opposite: Scala didn't stick, Clojure did. I guess there's some subjective reason why or why not Clojure/Scala would stick with someone.
However, it's false that Clojure doesn't have a company behind it: Cognitect is certainly backing up Clojure by developing ClojureScript and Clojure itself, Clojure consulting, the Datomic database and the Pedestal "framework".
Comment · 12 years ago
And if you ask me, its just so good that we haven't needed a revision in 20 years.
Comment · 12 years ago
Could you elaborate on how generics makes code less safe? In my experience, the lack of generics is much more type unsafe, as you often have to do casts at runtime (and handle them) when you have to implement your own data structures. In contrast, languages with generics handle those at compile time.
Comment · 13 years ago
Just for reference, a single goroutine has a 8 kb stack size. Having one million of these things in memory at once would require 8 Gb of memory. Obviously, the scheduler kicks in, but 8 kb chunks of memory still has to be assigned and freed for every routine started and stopped.
Comment · 13 years ago
Using val King = 13; val Queen = 12; in Scala is not equivalent with using Clojure keywords, as their printed variant will be 13 and 12, not :king and :queen. Reading debugging output or logs would force you to manually convert those values.
Ordering for free is valuable, I guess, but it sort of depends on the situation. Sometimes face cards are worth 10, other times they are worth 11, 12, 13. If you use val King = 10;, then it suddenly is impossible to distinguish between face cards and tens.
Comment · 13 years ago
I do agree that the structure is influenced by the paper, so I've added that in. I don't agree that they are "virtually identical" however, because there are significant differences leading to a lot of performance improvements (never any hash collisions, insertion and removal only at the end, resulting in perfect balancing, etc) and, as swanodette mentioned, Bagwell himself mentioned that they were pioneered by Hickey.
> Rich goes through this in one of his talks but I don't recall which.
If you figure out which, I'd love to know! :)
Comment · 13 years ago
Author here: I think you talk about the persistent hashmaps, not the persistent vectors. I've been looking for papers explaining Clojure's persistent collections, and Bagwell seems to cover the hash maps and hash sets quite well. However, I've not seen a paper on the persistent vectors, which was quite a bummer, and that was the reason I started explaining them in the first place.
If you have a reference to a paper explaining something similar (or the actual implementation), I'd love to put it in the post for others.
http://hypirion.com