5 ms·

Somehow the difference between O(1) and O(log32 n) has never actually been an issue for me in Clojure.

• detrino 13y ago
  Have you profiled the difference? Do you use these containers in places where it matters?
  • cgag 13y ago
    I'm sure there is a difference, I just don't care. They're still damn fast and the semantics of immutability would be worth quite a large speed difference to me. If you do happen to be doing something where the difference is truly going to matter, or you're writing a library anticipating needing that kind of performance, using mutability internally in your functions isn't discouraged as long as they remain referentially transparent: http://clojure.org/transients http://clojure.org/transients
    • tel 13y ago
      And Haskell's ST monad.
    • orclev 13y ago
      That's a good point. People don't understand that functional purity in Haskell, while a nice goal, isn't a law, you can break it if you have a good reason to. IO is sort of the canonical example, it isn't there to prevent you from doing IO, it's there to act as a giant warning sign that either this function, or one of the functions it uses isn't pure. Likewise mutable data structures while not the default, can be implemented in Haskell, they just have some caveats attached and shouldn't be used lightly. In other words, all things being equal, use the immutable data structure, but if you have a good reason to, you can use a mutable data structure instead, just be sure you know what you're getting into.
      • detrino 13y ago
        The problem is that "all things being equal" never happens because immutable data structures have worse performance if not used in a way that benefits from persistence. IMO, that makes them a poor default.
        • cgag 13y ago
          Pretty much everything except performance benefits from immutability and persistence, which is why using anything else as the default seems insane to me.
          • deleted 13y ago
            [deleted]
        • PeterisP 13y ago
          I'd rather say that 'performance+ convenience/safety-' is a poor default - minute performance improvements matter only in the bottlenecks of your code, so it makes sense to use the varsatile though slightly slower implementations as the default, and have the 100%-speed option require some explicit code as they are needed only in a minority/exception segments of your program. :) You could say that "all things being equal" never happens because mutable data structures have worse persistence if they're not used in a way that their performance matters. But also, different defaults make sense for different problem domains.
• reycharles 13y ago
  What do you mean by O(log32 n)?
  • cgag 13y ago
    Clojure's data structures are implemented using trees that have a 32-way branching factor, so each node has 32 children, instead of the 2 you'd see in a binary search tree. A lot of things you might expect to be O(1), like checking for membership in a set, or getting the nth element of a vector, actually take O(log_base_32(n)).
    • reycharles 13y ago
      Ah, I see. That doesn't matter in big-O notation, though, because log_32(n) = log_2(n) / log_2(32), that is the difference between two bases is a constant factor. I was a bit confused because O(log_32(n)) = O(log(n)) = log(32)+log(n) = O(log(32n)), so no matter how I parsed it I would just get O(log(n)) :)