10 ms·

This article points out a few right things, but also skips over the wrong parts. Namely, the amortised time complexity of dynamic lists. Amortised analysis tr

• mezuzza 10y ago
  This point should be understood very clearly: The article isn't wrong that an ArrayList has O(n) for a single insertion. However, the article misses that amortized analysis shows that the same structure can be made to have O(n) for n insertions as well. In effect, ArrayLists can be thought to have O(1) insertion time in practice meaning that all you are comparing are the differences in constants between the two structures. I think the biggest takeaway from this isn't that big-O can fool you (which it very well can), but that misunderstanding analysis can lead to poor decisions. A better argument for big-O fooling you can be found using Quicksort and any proper O(n Log(n)) sorting algorithm. Quicksort will outperform most in practical cases, but is technically O(n^2) in the worst case (average case O(n Log(n)).
  • firethief 10y ago
    Isn't that an argument for average case performance being a better predictor of average cases than worst case performance?
    • brianwawok 10y ago
      Well except quick sorts worst case is very easy to hit. Hence why you don't use it in CS101 form.
• jameshart 10y ago
  Insertion at the head of a dynamic list avoids the issue of amortized complexity, though, since every element in the array needs to be copied on every insert, whether a new array needed to be allocated or not. Unless you're concerned about the time complexity of the memory allocator?
• bfstein 10y ago
  The nuance you're missing here is that the author is always inserting at the front of the arraylist. So even though the list grows dynamically, it still needs to move every value one spot over. e.g. arraylist: [0][1][2][3][ ] Even though there is space left in the array, we still need to move all the values one index to the right to be able to insert at the front, which takes O(n) time. In contrast, inserting at the front of a linked list is simply a matter of moving pointers and therefore constant time.
  • gens 10y ago
    Can't you just imagine it is reversed, where the_array[num_things-1] is the first ?
    • hinkley 10y ago
      The awful thing about writing benchmarks is that if you don't give the worst case example, people give you shit for coming up with metrics that say whatever you want to say. If you give metrics for the case that should be worst for your argument, people give you shit about using such a stupid example. There's no way to avoid someone giving you grief no matter what you do.
      • andrewflnr 10y ago
        Um, give both?
        • hinkley 10y ago
          Then both groups agree that your examples are terrible ;)
    • DougBTX 10y ago
      Yes, then it would be a discussion about append performance instead of insert performance. Might be handy to do if you know that all the changes to an array will be inserts at the front, then you can just write the array in reverse and also read in reverse. But it is helpful to keep the terminology clear, because an insert in the middle of a linked list is still O(1), but inserting into the middle of an array will require moving some fraction of the data. The OP is discussing inserts at the start just because it is the worst-case scenario for arrays, then a positive result will still be true if some of the inserts are in the midddle or even near the end.
• jackmott 10y ago
  I think what you are saying is only true if you insert at the end of the ArrayList, (or at the beginning if you have one which leaves open space at either end) If you insert into arbitrary positions, or the front of these particular array lists, it will be O(n) even ignoring the growth issue, because every element has to be copied over 1 spot.
• barrkel 10y ago
  Amortising allocation won't help the article's example, which is insertion at the front, unless you have a quite unorthodox implementation of your array list (e.g. implementing something like a deque using a circular buffer). The Python growth allocation doesn't look peculiar to me. It's just calculating exponential growth without floating point operations. Whether you over-allocate in 50%, 25%, 12.5%, or whatever proportional increments (all trivial to calculate using bit shifts), they are all enough to make dynamic growth of the array O(n) over time. Any exponential growth will do. If anything, Python's list growth looks to me like it trades off slightly too much time to save space. Actual results will vary depending on realloc implementation etc of course.
• gingerrr 10y ago
  Would be interesting to see the performance of Python's overallocation algo compared to a simpler one like Lua's, which just overallocates to the next power of 2 (so if you have a list with 4 items and want to add, it jumps to 8, then 16, then 32). I can't imagine the bitwise operations adding up to that much time added in Python, but Lua needs to increase size much less the larger the list (after 7 iterations Lua has room for 64 items, Python only 46 according to that link). Interesting choices, wonder which optimizes for what. Would love to get Ierusalimschy and van Rossum in a room together and let them talk it out.
  • jwatte 10y ago
    Even with only 25% growth per realloc, you hit logarithmic overhead (only with a higher k because more actual copying.)