6 ms·
If we're mentioning Clojure: 1) Clojure is secretly a compiled language. A lot of routine errors in Clojure dev are compiler errors. 2) Clojure aims for super
by roenxi 3y ago
If we're mentioning Clojure:
1) Clojure is secretly a compiled language. A lot of routine errors in Clojure dev are compiler errors.
2) Clojure aims for super-native performance. Immutability in practice gives weird benefits. The obvious example is copying a large object but making a small change. As a native operation in C that is very expensive. In Clojure, the cost is roughly equivalent to the cost of making the small change, because the structure of the big object can be safely reused (everything is immutable, why not?). It enables completely different styles of coding, it is a very practical benefit of Clojure.
- ludston 3y agoTo drill down into this, adding or removing from a vector or hashset in clojure is O(logn). This also means that random access is also O(logn). Most operations on clojure persistent data structures are an order of magnitude less efficient than they are on the mutable equivalents, excepting a full copy which free due to it being unnecessary.
- freshhawk 3y agoUseful to specify that it is log32N, not log2N since that makes an enormous different in practice. Also, if you care about that then you can use transients (if no one knows you mutated the data structure then it still counts as immutable) or mutable structures - both of which are pretty simple.
- thaumasiotes 3y ago> Most operations on clojure persistent data structures are an order of magnitude less efficient than they are on the mutable equivalents It's not really clear what you mean by "order of magnitude" here. The notation you're using suggests that you're thinking in terms of asymptotic algorithmic resource requirements, which are most often characterized by polynomial degree; an order of magnitude ("factor of 10") is invisible in those terms. But a factor of log n, while not invisible, is nearly so. If you're thinking in terms of polynomial degree, a factor of log n is literally an infinitesimal value - it's more than 0, but less than all positive real numbers.
- loumf 3y agoAlso, I’m pretty sure it log base 32. The underlying data-structure is a Trie with a span of 32 nodes. So for 32^2 items, the depth is 2.
- thaumasiotes 3y agoAll logs are asymptotically equivalent, for the same reason that a factor of 10 is invisible.
- freshhawk 3y agoOnly in theory, with branching factors of 32, they are not remotely equivalent unless you have a supercomputer counting atoms in a universe or something.
- loumf 3y agoHickey has made the point that in real world (not asymptomatic) uses, the constants and depths make a difference he cares about. 10x takes seconds to a minute.
- ludston 3y agoYou know this would mean that a change to a vector under 32 elements is O(n) right? (Which it isn't quite in all cases, because the actual implementation is a bit more complex) But this doesn't apply to hashset because hashmaps are sparse, and stored as pairs, meaning that they're effectively base 16. Also the clojure implementation of sets is just hashmaps where the key is the same as the value.
- thaumasiotes 3y ago> You know this would mean that a change to a vector under 32 elements is O(n) right? Technically true, but only because a change to a vector of under 32 elements is O(1) by definition (as long as the algorithm is deterministic) and O(n) includes O(1). It's equally true that a change to a vector of under 32 elements is O(n!). The notation you're using is not meaningful in the context of bounded input. Big-O notation is not concerned with any behavior except the behavior at infinity.