5 ms·

To 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

To 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 ago
Useful 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 ago
  Also, 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 ago
    All logs are asymptotically equivalent, for the same reason that a factor of 10 is invisible.
    - freshhawk 3y ago
      Only 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 ago
      Hickey 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 ago
    You 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.
      - ludston 3y ago
        This is not generally the case. Practically speaking, big O notation is almost always bounded. The clojure vector implementation has a maximum count of 2^32, therefore the behaviour at infinity is O(SomeException)
- ludston 3y ago
  An order of magnitude is not necessarily a factor of 10. Otherwise we would always just say, "factor of 10" which has fewer syllables. The difference between O(logn) to O(1) is often referred to as an order of magnitude. As is O(logn) to O(n).
  - vincent-manis 3y ago
    I taught algorithms and data structures a lot. We never referred to differences in complexity as orders of magnitude, though you might say that Algorithm A's running time differs from B's running time on the same data by an order of magnitude. Also, the point about logarithmic time is that it grows much more slowly than even linear time: log2(128) is only 7, and log2(1024) is only 10.
  - thaumasiotes 3y ago
    > The difference between O(logn) to O(1) is often referred to as an order of magnitude. As is O(logn) to O(n). That isn't good usage, but there was enough context in your comment to guess that that was what you meant. The main problem I was pointing out is that the difference between O(log n) and O(1) is much, much, much, much, much, much smaller than the difference between O(log n) and O(n), so it doesn't make sense to describe those two differences the same way.
- nequo 3y ago
  I am with you on the point about order of magnitude but I don’t understand what you mean by log n being smaller than all positive real numbers. We are talking about asymptotics, since we are talking about O(f(n)) for some function f, right? Doesn’t log n go to infinity then since n goes to infinity?
  - thaumasiotes 3y ago
    I meant something a little bit nerdier. Mostly we worry about algorithms that can run in polynomial time. It's easy to show that when m < n, xᵐ = o(xⁿ), and that when a polynomial's degree is n, the whole polynomial is O(xⁿ), and this leads us to divide up the polynomial-runtime space according to the degree of a representative polynomial. It's very normal to talk about "linear" time requirements -- meaning ϴ(x¹), "constant" requirements [ϴ(x⁰)], "quadratic" requirements [ϴ(x²)], "cubic" requirements [ϴ(x³)], etc. (OK, it's less common to talk about higher degrees, but the concept stays relevant there.) So once you're thinking that way, you can ask where the function f(x) = log x belongs. It isn't a polynomial, but it is asymptotically limited by polynomials and so it's present within the polynomial-runtime space. If you represented the growth rate of the function f(x) = log x by a polynomial approximation, F(x) = xᵏ, what would the value of k be? The answer is that k must be a positive value that is greater than zero but less than all positive real numbers, an infinitesimal. If you're calibrated against polynomials, a logarithmic time requirement is "not constant, but so close to being constant that it's impossible to see the difference".
    - thaumasiotes 3y ago
      > by a polynomial approximation, F(x) = xᵏ (Note that if k is not an integer this isn't really a polynomial.)

freshhawk 3y ago

Useful 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 ago
Also, 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 ago
  All logs are asymptotically equivalent, for the same reason that a factor of 10 is invisible.
  - freshhawk 3y ago
    Only 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 ago
    Hickey 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 ago
  You 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.
    - ludston 3y ago
      This is not generally the case. Practically speaking, big O notation is almost always bounded. The clojure vector implementation has a maximum count of 2^32, therefore the behaviour at infinity is O(SomeException)
ludston 3y ago
An order of magnitude is not necessarily a factor of 10. Otherwise we would always just say, "factor of 10" which has fewer syllables. The difference between O(logn) to O(1) is often referred to as an order of magnitude. As is O(logn) to O(n).
- vincent-manis 3y ago
  I taught algorithms and data structures a lot. We never referred to differences in complexity as orders of magnitude, though you might say that Algorithm A's running time differs from B's running time on the same data by an order of magnitude. Also, the point about logarithmic time is that it grows much more slowly than even linear time: log2(128) is only 7, and log2(1024) is only 10.
- thaumasiotes 3y ago
  > The difference between O(logn) to O(1) is often referred to as an order of magnitude. As is O(logn) to O(n). That isn't good usage, but there was enough context in your comment to guess that that was what you meant. The main problem I was pointing out is that the difference between O(log n) and O(1) is much, much, much, much, much, much smaller than the difference between O(log n) and O(n), so it doesn't make sense to describe those two differences the same way.
nequo 3y ago
I am with you on the point about order of magnitude but I don’t understand what you mean by log n being smaller than all positive real numbers. We are talking about asymptotics, since we are talking about O(f(n)) for some function f, right? Doesn’t log n go to infinity then since n goes to infinity?
- thaumasiotes 3y ago
  I meant something a little bit nerdier. Mostly we worry about algorithms that can run in polynomial time. It's easy to show that when m < n, xᵐ = o(xⁿ), and that when a polynomial's degree is n, the whole polynomial is O(xⁿ), and this leads us to divide up the polynomial-runtime space according to the degree of a representative polynomial. It's very normal to talk about "linear" time requirements -- meaning ϴ(x¹), "constant" requirements [ϴ(x⁰)], "quadratic" requirements [ϴ(x²)], "cubic" requirements [ϴ(x³)], etc. (OK, it's less common to talk about higher degrees, but the concept stays relevant there.) So once you're thinking that way, you can ask where the function f(x) = log x belongs. It isn't a polynomial, but it is asymptotically limited by polynomials and so it's present within the polynomial-runtime space. If you represented the growth rate of the function f(x) = log x by a polynomial approximation, F(x) = xᵏ, what would the value of k be? The answer is that k must be a positive value that is greater than zero but less than all positive real numbers, an infinitesimal. If you're calibrated against polynomials, a logarithmic time requirement is "not constant, but so close to being constant that it's impossible to see the difference".
  - thaumasiotes 3y ago
    > by a polynomial approximation, F(x) = xᵏ (Note that if k is not an integer this isn't really a polynomial.)