5 ms·

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 t

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.

userbinator 8y ago
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)?
- falsedan 8y ago
  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
  - aoeusnth1 8y ago
    Uh, no, he's assuming that the (+) operator concatenates arrays by allocating a new one. Which is correct. "Read in good faith" indeed.
    - falsedan 8y ago
      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 Coirdially yours, falsedan
  - TeMPOraL 8y ago
    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).
    - falsedan 8y ago
      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
chrismorgan 8y ago
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.
drdrey 8y ago
Appending to an array is O(1). Prepending is going to be O(n).
- bhrgunatha 8y ago
  The amortized cost of prepend (unshift in ruby) is O(1) (since Ruby 2). Of course that means at some point you'll get O(n) prepend. [1] https://stackoverflow.com/questions/8353026/what-is-the-run-time-of-shift-unshift-in-a-ruby-array https://stackoverflow.com/questions/8353026/what-is-the-run-...
  - userbinator 8y ago
    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.
- smitherfield 8y ago
  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 https://news.ycombinator.com/item?id=18988075#18998572
  - boomlinde 8y ago
    > Prepending would be O(1) because it's creating a new array instead of prepending in place. No, you still need to copy the old array to the new array. FWIW, Ruby may already be allocating some space before and after the array to accommodate a few pre-/appendages.
    - smitherfield 8y ago
      >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.
lucio 8y ago
Let's say the array is 1m elements... 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?
- gdy 8y ago
  There are three dots in the range, not two. 1...size-1 == 1..size-2
kstenerud 8y ago
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.

userbinator 8y ago

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)?

falsedan 8y ago
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
- aoeusnth1 8y ago
  Uh, no, he's assuming that the (+) operator concatenates arrays by allocating a new one. Which is correct. "Read in good faith" indeed.
  - falsedan 8y ago
    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 Coirdially yours, falsedan
- TeMPOraL 8y ago
  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).
  - falsedan 8y ago
    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

chrismorgan 8y ago

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.

drdrey 8y ago

Appending to an array is O(1). Prepending is going to be O(n).

bhrgunatha 8y ago
The amortized cost of prepend (unshift in ruby) is O(1) (since Ruby 2). Of course that means at some point you'll get O(n) prepend. [1] https://stackoverflow.com/questions/8353026/what-is-the-run-time-of-shift-unshift-in-a-ruby-array https://stackoverflow.com/questions/8353026/what-is-the-run-...
- userbinator 8y ago
  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.
smitherfield 8y ago
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 https://news.ycombinator.com/item?id=18988075#18998572
- boomlinde 8y ago
  > Prepending would be O(1) because it's creating a new array instead of prepending in place. No, you still need to copy the old array to the new array. FWIW, Ruby may already be allocating some space before and after the array to accommodate a few pre-/appendages.
  - smitherfield 8y ago
    >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.

lucio 8y ago

Let's say the array is 1m elements... 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?

gdy 8y ago
There are three dots in the range, not two. 1...size-1 == 1..size-2

kstenerud 8y ago

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.