4 ms·

That first example in the article was interesting because it made me realise that I have a strong aversion to pushing the complexity into the data rather than i

That first example in the article was interesting because it made me realise that I have a strong aversion to pushing the complexity into the data rather than into the code. Modifying the list seems to me that it could be a cause of other bugs (what if the list is re-used and something depends on it?).

DarkWiiPlayer 8y ago
Never mind bugs, imagine that array has 5 million elements. Good luck re-allocating and copying that to add an element at the start and another at the end.
- dpark 8y ago
  I don't like the approach of pointlessly reallocating the array this way, but 5 million elements is not a problem on any machine built in the last 20 years. That's just 20 megs for 4-byte integers. With modern GC, this is cheap. It's not something you'd want to do in a tight loop (the copy time will start to matter), but for something like the example, the cost (in machine terms) is negligible.
pure-awesome 8y ago
I also experienced an instinctual aversion to padding the array that I can't really motivate (honestly) except to say "I don't like it." The version with special cases feels cleaner to me.
- scrabble 8y ago
  Padding the array is a bit of a code smell. You can't just pad an array without allocating a new block of memory. After allocation you need to copy the array into the new space. This is a significant amount of overhead to a fairly straightforward and efficient algorithm.
  - arethuza 8y ago
    Well, that's easy to fix - copy your array into a linked list so you an insert elements at the head efficiently. ;-)
    - klyrs 8y ago
      Yes, the real problem with this implementation is the data structure they use. But is `next == null` a special case? ogod what do we do?!
      - banku_brougham 8y ago
        This is interesting. Is it possible to implement a linked list while eliminating the end of the list ‘edge case’, in the fashion of the parent article?
        pure-awesome 8y ago
        Create a "sentinel" node which represents null and also points to itself, perhaps?

DarkWiiPlayer 8y ago

Never mind bugs, imagine that array has 5 million elements. Good luck re-allocating and copying that to add an element at the start and another at the end.

dpark 8y ago
I don't like the approach of pointlessly reallocating the array this way, but 5 million elements is not a problem on any machine built in the last 20 years. That's just 20 megs for 4-byte integers. With modern GC, this is cheap. It's not something you'd want to do in a tight loop (the copy time will start to matter), but for something like the example, the cost (in machine terms) is negligible.

pure-awesome 8y ago

I also experienced an instinctual aversion to padding the array that I can't really motivate (honestly) except to say "I don't like it." The version with special cases feels cleaner to me.

scrabble 8y ago
Padding the array is a bit of a code smell. You can't just pad an array without allocating a new block of memory. After allocation you need to copy the array into the new space. This is a significant amount of overhead to a fairly straightforward and efficient algorithm.
- arethuza 8y ago
  Well, that's easy to fix - copy your array into a linked list so you an insert elements at the head efficiently. ;-)
  - klyrs 8y ago
    Yes, the real problem with this implementation is the data structure they use. But is `next == null` a special case? ogod what do we do?!
    - banku_brougham 8y ago
      This is interesting. Is it possible to implement a linked list while eliminating the end of the list ‘edge case’, in the fashion of the parent article?
      - pure-awesome 8y ago
        Create a "sentinel" node which represents null and also points to itself, perhaps?