title: Speed of using append in python repeatedly
body: <p>Is it faster substantially to start with a preallocated list and set items at each index, as opposed to starting with an empty list and appending items? I need this list to hold 10k-100k items.</p>
  
  <p>I ask because I am trying to implement an algorithm that requires O(n) time at each level of recursion, but I am getting results that indicate O(n^2) time. I thought perhaps python needing to keep resizing the list might cause this slowdown.</p>
  
  <p>I found similar questions but none that explicitly answered my question. One answer indicated that garbage collecting might be very slow with so many items, so I tried turning gc on and off at saw no improvement in results.</p>
  
  <p>PROBLEM SOLVED:
  If anyone is curious, the slowdown was caused by unioning sets together too often. Now I use a different method (involves sorting), to check if the same key is seen twice.</p>