Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed1a.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.016 X-Spam-Evidence: '*H*': 0.97; '*S*': 0.00; '21,': 0.07; 'attribute': 0.07; 'already.': 0.09; 'cc:addr:python-list': 0.11; 'jan': 0.12; '10:17': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'heapq': 0.16; 'subject:which': 0.16; 'index': 0.16; 'wrote:': 0.18; 'all,': 0.19; 'cc:addr:python.org': 0.22; 'looks': 0.24; '(or': 0.24; 'cc:2**0': 0.24; 'values': 0.27; 'header:In-Reply-To:1': 0.27; 'change,': 0.30; 'robert': 0.30; 'message-id:@mail.gmail.com': 0.30; 'code': 0.31; 'constant': 0.31; 'node': 0.31; 'pos': 0.31; 'values.': 0.31; 'probably': 0.32; 'maintaining': 0.32; 'but': 0.35; 'received:google.com': 0.35; 'subject:data': 0.36; 'subject:?': 0.36; 'so,': 0.37; 'list': 0.37; 'list.': 0.37; 'performance': 0.37; 'easiest': 0.38; 'mapping': 0.38; 'whatever': 0.38; 'pm,': 0.38; 'remove': 0.60; 'matter': 0.61; "you're": 0.61; "you'll": 0.62; 'worth': 0.66; 'lowest': 0.74; '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:content-transfer-encoding; bh=v6WHlfhUDXrg2eD7r/vHAl8AKbMSZd2tBpgiEq8/eY0=; b=sbIlmNkBNH9FR6GWyJqe5vNefbA53+Wz7umZqnokvLNAfi20R8KjRGKSOX494r8646 NBkj5w3OyAd8fmA3KxjxTQ5X/z6IOCvxoNuHMUDIO8nfcnW7jQCvm6bkFSFnZinBzfMo NUfx+Ay0A97SCvZfshYbwYeLkA39BLYK5s6Xk0exDE0gQBx3Opm+lGbjB6kgg9FuFDB1 o8+EliOi0N2XHvc5kKMaecAV021Iy8PsPUGMjX9hfBMfSGZgwcJOMyERd+drjVYdZyUp v56F7ZzHVwUHHsReXVAlvB/HKfaQeMGm/aHamTOvltPDlHz8Dvm2tgqbmewPrDgW3zrG +24g== MIME-Version: 1.0 X-Received: by 10.66.26.176 with SMTP id m16mr8738066pag.142.1390303673695; Tue, 21 Jan 2014 03:27:53 -0800 (PST) In-Reply-To: References: Date: Tue, 21 Jan 2014 22:27:53 +1100 Subject: Re: which data structure to use? From: Chris Angelico Cc: "python-list@python.org" Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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: 18 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1390303676 news.xs4all.nl 2961 [2001:888:2000:d::a6]:41373 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:64402 On Tue, Jan 21, 2014 at 10:17 PM, Robert Voigtl=C3=A4nder wrote: > 1. check if a specific item - identified by Node.pos - is in the list. > 2. find the object with the lowest Node.f attribute and update or remove = it Are both those values constant once the Node is added? If so, the easiest way would be to maintain a dictionary mapping pos to the Node (or to a list of Nodes, if you can have multiple with the same pos), and probably heapq for the f values. But if they change, you'll have to update both data structures. If they change often, it's probably not worth maintaining index structures - just search for what you want, when you want it. And if you're working with a small list (say, less than a thousand items), performance isn't going to matter at all, so just do whatever looks cleanest in your code - probably you have that already. ChrisA