5 ms·

I can't upvote you enough. Too often programmers conflate "functional programming" with "availability of an O(1) array data type". The former does not imply l

I can't upvote you enough. Too often programmers conflate "functional programming" with "availability of an O(1) array data type". The former does not imply lack of the latter, and (as you stated) lack of the latter does not imply the former. The important takeaway I think, is that O(log n) approaches O(1) for all practical values of n. To the downvoters: gee golly, would it hurt you to reply to my comment? If you think I'm wrong then say why!

SamReidHughes 15y ago
Edit: O(log n) is clearly worse than O(1) if you just considered an O(log n) array-replacement data structure or hash table-replacement data structure and considered what its performance would be. I mean, how is this even a question? Also if memory is O(log n) then arrays are O(log n) but BSTs are O((log n)^2). (Edit II: Let's be clear that BSTs are already (log n)^2 if you're counting CPU cycles with O(1) memory access. They're O(log n) if you count cache misses or comparisons, or you might say they're O((log n)^2) but the first log is base <2 and the second is the logarithm base 2 to the 256th power, so only one really counts. (The second manifests as a cache line miss if your key comparison walks past the first 32 bytes of your key.)) (Actually memory access is at best O(n^(1/3)) thanks to space being three dimensional, but really worse thanks to cooling concerns, and uh, for sufficiently large n, worse because of gravity.)
- btilly 15y ago
  O(log n) is clearly worse than O(1) if you just considered an O(log n) array-replacement data structure or hash table-replacement data structure and considered what its performance would be. I mean, how is this even a question? Why yes, it is worse in some theoretical manner. But if you think it is necessarily worse as a practical manner, you have failed to understand the math fully. Suppose that n is 1000 in some toy problem. Then you scale it up to a huge data set, a billion items! The log(n) factor only got worse by a factor of 3. Maybe we didn't go high enough. Perhaps we can take a large data set. Let's see, how about all of the data that is produced at CERN's Large Hadron Collider in a year? That's 15 petabytes. Now the log(n) factor is a whopping 5.39. In other words while log(n) represents unbounded possible growth, it gets worse in practice by at most a fairly small constant factor. How about O(1)? O(1) does not mean fast. It just means constant relative to the data size. It can be a bad constant, but as long as it is a constant it qualifies as O(1). Let's take a practical example. Wavelets are cool in lots of ways, but one of the properties people noticed quickly is that doing a basic wavelet transform on a data set with n elements takes time O(n). Doing a FFT (Fast Fourier Transform) on the same data set takes time O(n log(n)). Yay, we're faster! But hold on a minute. The interesting wavelets that we like to use are O(n) with a worse constant than the FFT. So the FFT tends to be faster on practical data sets. (There are lots of reasons why one would prefer wavelets over the FFT, but speed of calculation is not generally one of them.)
  - SamReidHughes 15y ago
    > But if you think it is necessarily worse as a practical manner, you have failed to understand the math fully. Congratulations, I don't think one algorithm is necessarily worse, your entire post was a waste of effort. I mean seriously you just made a post teaching about how logarithmic constants can be low enough that they don't matter in reply to my post which provided an example of that very thing.
    - btilly 15y ago
      I was just explaining the comment that O(log(n)) approaches O(1) for all practical values of n. If you understood this, then why did you start off your post arguing that O(log(n)) was worse than O(1)? Incidentally comparing a logarithmic lookup to a hash lookup, a lot of nosql solutions use hash tables because O(1) is good, right? For instance look at Apache's Cassandra. By contrast Google's BigTable uses an ordered data structure which is logarithmic. Guess what, if you've used both, BigTable is better. Because the extra log cost is irrelevant for the normal use case, and being ordered reduces the operational cost of things like range searches.
      - SamReidHughes 15y ago
        It's going to be very hard to tell me how I'm wrong when I agree with everything you're saying.
        sanderjd 15y ago
        I found the non-argument that you two just had to be interesting, informative, and entertaining. So don't feel too bad about losing the argumentative-agreement battle - it was great while it lasted!
dan00 15y ago
"I can't upvote you enough. Too often programmers conflate "functional programming" with "availability of an O(1) array data type". The former does not imply lack of the latter, and (as you stated) lack of the latter does not imply the former." Yes, even the pure Haskell has unboxed, mutable O(1) arrays. They're just a bit hidden for the beginner.

SamReidHughes 15y ago

Edit: O(log n) is clearly worse than O(1) if you just considered an O(log n) array-replacement data structure or hash table-replacement data structure and considered what its performance would be. I mean, how is this even a question? Also if memory is O(log n) then arrays are O(log n) but BSTs are O((log n)^2). (Edit II: Let's be clear that BSTs are already (log n)^2 if you're counting CPU cycles with O(1) memory access. They're O(log n) if you count cache misses or comparisons, or you might say they're O((log n)^2) but the first log is base <2 and the second is the logarithm base 2 to the 256th power, so only one really counts. (The second manifests as a cache line miss if your key comparison walks past the first 32 bytes of your key.)) (Actually memory access is at best O(n^(1/3)) thanks to space being three dimensional, but really worse thanks to cooling concerns, and uh, for sufficiently large n, worse because of gravity.)

btilly 15y ago
O(log n) is clearly worse than O(1) if you just considered an O(log n) array-replacement data structure or hash table-replacement data structure and considered what its performance would be. I mean, how is this even a question? Why yes, it is worse in some theoretical manner. But if you think it is necessarily worse as a practical manner, you have failed to understand the math fully. Suppose that n is 1000 in some toy problem. Then you scale it up to a huge data set, a billion items! The log(n) factor only got worse by a factor of 3. Maybe we didn't go high enough. Perhaps we can take a large data set. Let's see, how about all of the data that is produced at CERN's Large Hadron Collider in a year? That's 15 petabytes. Now the log(n) factor is a whopping 5.39. In other words while log(n) represents unbounded possible growth, it gets worse in practice by at most a fairly small constant factor. How about O(1)? O(1) does not mean fast. It just means constant relative to the data size. It can be a bad constant, but as long as it is a constant it qualifies as O(1). Let's take a practical example. Wavelets are cool in lots of ways, but one of the properties people noticed quickly is that doing a basic wavelet transform on a data set with n elements takes time O(n). Doing a FFT (Fast Fourier Transform) on the same data set takes time O(n log(n)). Yay, we're faster! But hold on a minute. The interesting wavelets that we like to use are O(n) with a worse constant than the FFT. So the FFT tends to be faster on practical data sets. (There are lots of reasons why one would prefer wavelets over the FFT, but speed of calculation is not generally one of them.)
- SamReidHughes 15y ago
  > But if you think it is necessarily worse as a practical manner, you have failed to understand the math fully. Congratulations, I don't think one algorithm is necessarily worse, your entire post was a waste of effort. I mean seriously you just made a post teaching about how logarithmic constants can be low enough that they don't matter in reply to my post which provided an example of that very thing.
  - btilly 15y ago
    I was just explaining the comment that O(log(n)) approaches O(1) for all practical values of n. If you understood this, then why did you start off your post arguing that O(log(n)) was worse than O(1)? Incidentally comparing a logarithmic lookup to a hash lookup, a lot of nosql solutions use hash tables because O(1) is good, right? For instance look at Apache's Cassandra. By contrast Google's BigTable uses an ordered data structure which is logarithmic. Guess what, if you've used both, BigTable is better. Because the extra log cost is irrelevant for the normal use case, and being ordered reduces the operational cost of things like range searches.
    - SamReidHughes 15y ago
      It's going to be very hard to tell me how I'm wrong when I agree with everything you're saying.
      - sanderjd 15y ago
        I found the non-argument that you two just had to be interesting, informative, and entertaining. So don't feel too bad about losing the argumentative-agreement battle - it was great while it lasted!

dan00 15y ago

"I can't upvote you enough. Too often programmers conflate "functional programming" with "availability of an O(1) array data type". The former does not imply lack of the latter, and (as you stated) lack of the latter does not imply the former." Yes, even the pure Haskell has unboxed, mutable O(1) arrays. They're just a bit hidden for the beginner.