Creating a list with holes

[Chris Angelico]

On Sat, Jan 4, 2014 at 2:38 AM, Roy Smith <roy at panix.com> wrote:
> Why do you want holes?  Is the issue that you're storing sparse data and
> don't want to waste memory on unused keys?  If so, a dictionary should
> do you fine.
>
> Do you need to be able to read the values back out in a specific order?
> You can still do that with a dictionary if you're willing to re-sort the
> keys; that's O(n log n) on the number of keys, but if n is small, it
> doesn't matter.

There's another factor, which is iteration time. Maybe you don't care
about the memory usage, but compare these:

foo = [None]*1000
foo[123] = 234
foo[543] = 432

for key,value in enumerate(foo):
    if value: print("Slot %d is %d"%(key,value))

# versus

foo = {}
foo[123] = 234
foo[543] = 432

for key in sorted(foo.keys()):
    value = foo[key]
    if value: print("Slot %d is %d"%(key,value))

Which one's going to be faster? The dictionary, by far, in this
example. I'm not sure how populated the list would have to be to beat
it (as the dict will get slower on O(n log n) on keys, as you mention,
while the list will run at O(n) on the highest element, which may well
be a constant), but it's something to consider.

ChrisA