Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #63066

Re: Creating a list with holes

Show all headers | View raw

On Sat, Jan 4, 2014 at 2:38 AM, Roy Smith <roy@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

Back to comp.lang.python | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Creating a list with holes Larry Martell <larry.martell@gmail.com> - 2014-01-03 10:19 -0500
  Re: Creating a list with holes eneskristo@gmail.com - 2014-01-03 07:30 -0800
    Re: Creating a list with holes Larry Martell <larry.martell@gmail.com> - 2014-01-03 10:41 -0500
      Re: Creating a list with holes Denis McMahon <denismfmcmahon@gmail.com> - 2014-01-03 18:07 +0000
        Re: Creating a list with holes Larry Martell <larry.martell@gmail.com> - 2014-01-03 19:15 -0500
          Re: Creating a list with holes Roy Smith <roy@panix.com> - 2014-01-03 20:18 -0500
            Re: Creating a list with holes Denis McMahon <denismfmcmahon@gmail.com> - 2014-01-04 02:03 +0000
  Re: Creating a list with holes Roy Smith <roy@panix.com> - 2014-01-03 10:38 -0500
    Re: Creating a list with holes Chris Angelico <rosuav@gmail.com> - 2014-01-04 02:46 +1100

csiph-web