Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.008 X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; 'keys,': 0.09; 'cc:addr :python-list': 0.11; 'jan': 0.12; 'dict': 0.16; 'dictionary,': 0.16; 'element,': 0.16; 'fine.': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'iteration': 0.16; 'order?': 0.16; 'roy': 0.16; 'storing': 0.16; 'usage,': 0.16; 'sat,': 0.16; 'wrote:': 0.18; 'small,': 0.19; 'memory': 0.22; 'cc:addr:python.org': 0.22; 'example.': 0.24; 'skip:% 10': 0.24; 'cc:2**0': 0.24; 'compare': 0.26; 'values': 0.27; 'header:In- Reply-To:1': 0.27; 'am,': 0.29; "doesn't": 0.30; 'waste': 0.30; 'subject:list': 0.30; 'message-id:@mail.gmail.com': 0.30; "i'm": 0.30; 'run': 0.32; 'another': 0.32; 'maybe': 0.34; 'subject:with': 0.35; 'something': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'should': 0.36; 'so,': 0.37; 'list': 0.37; 'issue': 0.38; 'highest': 0.39; 'sure': 0.39; 'how': 0.40; 'read': 0.60; "you're": 0.61; 'back': 0.62; 'beat': 0.68; 'smith': 0.68; 'to:none': 0.92 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:cc :content-type; bh=P9PY5f5iutw2sKBvgPmfSkDh3NpQG6rYG/abf4Z8pcw=; b=PZOgMGaTYa3sKTb7568j0nBUF0za3wTSqVhLyklnb0L5pcaROzSG/N4v0l52Mc0k8c knRCbX2/N8aJWrNiCbwEV7iGnTWE4evkE9vsSM+TKRZEbPV0tV+CrVppCb51w4YYZpbB QSEiCaOWaHpTU8aQ3m+2rT7MTjRC9w1Y0lfgxcvZzZldCfv168CenVCKV/noG6nWZ+Eh 2wrjNpHGAj+Dx3s+5n/AsPsesCM4j0dHAMNlwCw7y+eY5DSMViJbMefg1i8NkeOXoz0U +PdqF/XjH0qZPW0MEttPESv6QRI+Pb3nie6W5wqWpJKUaKyg539+hZG8QkURE/z3k3qZ ALtQ== MIME-Version: 1.0 X-Received: by 10.66.129.133 with SMTP id nw5mr49699340pab.98.1388763964642; Fri, 03 Jan 2014 07:46:04 -0800 (PST) In-Reply-To: References: Date: Sat, 4 Jan 2014 02:46:04 +1100 Subject: Re: Creating a list with holes From: Chris Angelico Cc: "python-list@python.org" Content-Type: text/plain; charset=UTF-8 X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 37 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1388763968 news.xs4all.nl 2848 [2001:888:2000:d::a6]:40936 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:63066 On Sat, Jan 4, 2014 at 2:38 AM, Roy Smith 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