Comment by chrismorgan | Hacker News Reader

Comment by chrismorgan | Hacker News Reader

The first example is not at all good. It does not, in fact, eliminate the special cases, and becomes almost certainly less efficient—demonstrating why I would say that for this particular case a Good Programmer would write the code in the first form and not the second.

The special cases: they are not removed, merely transformed from `if` statements to boundary conditions on the iterator. The `i == 0` and `i == input.size - 1` checks effectively move into the iterator, with how the nice and clear `input.map.with_index do |_, i|` becomes the magic `(1...padded.size-1).map do |i|`. The 0 added to the start and end are also easily arguably special cases.

The second form is almost certainly less efficient because you’re creating at least one new array, unnecessarily.

> The special cases are gone, and the simple algorithm shines through.

The algorithm does shine through more, but the special cases are not gone, merely transformed (and into an arguably less clear form), and the code is less efficient.

Simplifying things is a worthy goal, and a lot of special cases are code smells, but be careful in seeking to remove them, and remember to at least consider performance, even if you end up deciding to prefer succinctness instead.

Yeah, a little OCD but I couldn't stand the first example (and some of the others). Here's a more reasonable implementation that doesn't special case (or more precisely wraps the special-casing in a standard library method):

  class Array
    def neighbor_sums
      map.with_index do |_, i|
        fetch(i - 1 & 0xFF_FF_FF_FF, 0) + fetch(i + 1, 0)
      end
    end
  end

  [1, 1, 1, 1].neighbor_sums # [1, 2, 2, 1]

Absolutely! Enumerating the neighbors of an element of a list by definition requires bounds checking. It's not more elegant to instead do some extra additions with numbers known to be 0 at compile time.

Represent the question faithfully first, then optimize later maybe sometimes.

> The first example is not at all good

No, it's not, but in my opinion not because of any of the reasons you just stated. Unless you're writing Go, that code should have been a fold over addition, or a `sum` function if available in the standard library.

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.

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

Uh, no, he's assuming that the (+) operator concatenates arrays by allocating a new one. Which is correct. "Read in good faith" indeed.

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

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

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.

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

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-...

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

> 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.

>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.

In other words, O(n), not O(1).

> technically O(n) but trivial

"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.

O(3n) = O(2n) = O(n)

> "Technically" O(n) is the only O(n).

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.

Not in terms of space.

Array copies are O(n), not O(1).

See my reply to boomlinde: https://news.ycombinator.com/item?id=18988075#19000005

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

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?

There are three dots in the range, not two.

1...size-1 == 1..size-2

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.

Reply on news.ycombinator.com