The repeated if checks inside a loop could easily be less performant than the O(1) operation of adding 2 items to a array.
I think you’re too quick to assume that your preferred solution is faster.
Personally, I’d use the more clear code and only if the code proved to be a bottleneck even consider refactoring for performance. Whether the author’s preferred solutions are clearer, I’m not convinced however.
Finally, the author doesn’t claim that the special cases are gone, but more so that the input is transformed in a way to allow processing that is blind to them.
The checks are indeed an added cost, and that’s why I said “almost certainly less efficient” the first time rather than “less efficient”. (But subsequent times I did drop it.)
But what you call “the O(1) operation of adding two items to an array” is simply not true:
① While appending to arrays is normally O(1) in the cases that there is still spare capacity in the array and the entire thing doesn’t need to be reallocated, prepending is O(n) as it has to move all of the subsequent values along.
② What’s happening is not just adding two items to an array, but rather allocating an entire new array and copying all the values into it; this will be roughly O(n), but with a high constant overhead: allocating memory is expensive.
I can’t speak of any Ruby interpreter’s performance on the matter, and I’m fairly confident that the conditionals will be much more expensive there than they would be in Rust (where I have no doubt at all that the conditional version would smoke the allocating version in all cases), but allocating memory is a pretty expensive business.
> Finally, the author doesn’t claim that the special cases are gone
I quote: “The special cases are gone”. Further, I do not grant your response that the processing is blind to them—the inside of the loop is, but the special cases were moved to the boundary conditions of the loop. They’re still there.
The repeated checks in the loop will be reduced significantly in cost due to branch prediction.
Adding an item to each end of the array induces two problems:
- Adding to the beginning of the array will require all elements of the array to be shifted, and possibly a reallocation and cache miss (depending on implementation language).
- Adding to the end of the array will require traversing the array, potentially causing an extra cache miss.
Cache misses and reallocations are generally the highest performance costs to pay in computing today. O(x) alone is not sufficient to determine an algorithm's real-world performance.
than the O(1) operation of adding 2 items to a array.
Not very familiar with the language, but the code appears to create a new array by concatenating three arrays, which means copying all the elements; how is that O(1)?
Well, read in good faith and assume, if your reading results in an obvious contradiction, you probably assumed something that wasn’t what the author intended: in this case, that arrays are immutable
Well, if you're dealing with immutable arrays, then concatenating is even more expensive on average, because you either end up copying everything (which is O(n)), or the array isn't really an array (and you start paying for various forms of indirection).
We, get this: what if you’re using mutable arrays?
#whoa
I understand that reading is hard and avoiding needless posturing in order to display a personally-appraised superior intellect is harder, but reading in good faith requires that you put in some effort and not knee-jerk
You buffoon, you hydroencephalitic harrumpher, if your pasting on my statement leads to an obvious contradiction, you try again in good faith to find a better syntax tree. If you can, you ask a polite follow up question, not blow hard
the "ifs" inside the loop will be correctly predicted for cases 2..999,999
the processing is not "blind" to the new special case: "the array is padded", the loop is 1..size-1, which I think it's an error. Shouldn't be 1..size-2?
Getting amortised O(1) prepend is interesting because it's just like append, except you "center" or "right-justify" (if you don't care about O(1) append) the array in the allocated space, and exponentially reallocate when full as with append.
Prepending would be O(1) because it's creating a new array instead of prepending in place. Still bugs me (seems inelegant, even if not necessarily inefficient) so I wrote my own version: https://news.ycombinator.com/item?id=18988075#18998572
>No, you still need to copy the old array to the new array.
That's just a lock (nontrivial but O(1)) and a memcpy (technically O(n) but trivial, and O(1) for the common case if it's implemented with vector instructions), plus in any event the sums-of-neighbors method has to be at least O(n) on an idealized Von Neumann machine because it must read every element of the source array and also write every element of the destination.
"Technically" O(n) is the only O(n). There isn't some widespread colloquial use of Big O notation where O(n) means something else. Whether it's trivial is beside the point, but for a large n, O(n) in both time and space can be prohibitive, and it may become important that I don't use such an algorithm. For example, if I have 8 GB of data and 12 GB of working memory I can't satisfy those space requirements.
> and O(1) for the common case if it's implemented with vector instructions)
What is the common case in your view? memcpy in the general case is O(n). That you can perform multiple copies in parallel might affect the real time, but it doesn't affect the time complexity because O(kn) = O(n) for a constant k even if that k = 1/16 or however many copies you can perform at once.
> plus in any event the sums-of-neighbors method has to be at least O(n) on an idealized Von Neumann machine because it must read every element of the source array and also write every element of the destination.
In idealized algorithmic analysis, but not necessarily real life. "Amortized O(1)," which I assume you concede is a commonly-used, meaningful and legitimate term, means "technically" an idealized O(>1) but O(1) in practice.
Calling memcpy inside a Ruby method call is amortized O(1) because for any "n" that fits within available memory, it will always be much faster than the other things in a Ruby method call, which involve dozens of locks, hash table lookups with string keys, dynamic type checks, additional Ruby method calls and so forth.
Likewise, computational complexity on an idealized Von Neumann machine isn't always the same on a real computer, in both directions. Dynamic allocations are theoretically O(n) but may be O(1) if the program never exceeds the preallocated space. Or suppose there were a loop over an array of pointers which dereferenced each pointer; the dereferences are theoretically O(1) but may be O(n) if they evict the parent array from the cache.
> What is the common case in your view?
Such as an array small enough that it can be copied with 10 or fewer vector load/stores.
> O(3n) = O(2n) = O(n)
Yes, that's my point. It's impossible to implement the example in less than idealized O(n) time, so O(n) and O(1) operations are equivalent complexity-wise WRT the entire method.
> In idealized algorithmic analysis, but not necessarily real life.
Big O notation is used for idealized algorithmic analysis. If you want to talk about real life, you can count cycles, seconds, watts etc.
> "Amortized O(1)," which I assume you concede is a commonly-used, meaningful and legitimate term, means "technically" an idealized O(>1) but O(1) in practice.
Yes, but I wouldn't take O(1) on its own to imply amortized complexity. Not that pretending that an array copy is O(1) in practice is particularly useful here since if you measure a copy operation in practice, you'll find that the time it takes scales roughly linearly with the size of the array. Not to mention that the space complexity is O(n) no matter how you put it.
> Such as an array small enough that it can be copied with 10 or fewer vector load/stores.
Are other cases conversely "uncommon"? My point here is that this is entirely your opinion and doesn't pertain to whether an array copy is O(1) or O(n) complex.
> Yes, that's my point. It's impossible to implement the example in less than idealized O(n) time, so O(n) and O(1) operations are equivalent complexity-wise WRT the entire method.
The one where you yourself even say it's O(n)? Big-O is concerned with asymptotic complexity. It's O(n) until you show us it's not (e.g. implementation code, not musings.)
Here's my second reply to him, where I myself point out that idealized Von Neumann machines don't exist in real life, and certain idealized O(n) operations (such as memcpy) may in real life for any possible "n" be cheaper than some baseline constant C (such as the cost of a Ruby method call): https://news.ycombinator.com/item?id=18988075#19001585
I think you’re too quick to assume that your preferred solution is faster.
Personally, I’d use the more clear code and only if the code proved to be a bottleneck even consider refactoring for performance. Whether the author’s preferred solutions are clearer, I’m not convinced however.
Finally, the author doesn’t claim that the special cases are gone, but more so that the input is transformed in a way to allow processing that is blind to them.