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

Groups > comp.lang.python > #64402

Re: which data structure to use?

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 <rosuav@gmail.com>
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 <a0d3734d-5275-4b28-9a3f-6957474674d7@googlegroups.com>
References <a0d3734d-5275-4b28-9a3f-6957474674d7@googlegroups.com>
Date Tue, 21 Jan 2014 22:27:53 +1100
Subject Re: which data structure to use?
From Chris Angelico <rosuav@gmail.com>
Cc "python-list@python.org" <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 <python-list.python.org>
List-Unsubscribe <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive <http://mail.python.org/pipermail/python-list/>
List-Post <mailto:python-list@python.org>
List-Help <mailto:python-list-request@python.org?subject=help>
List-Subscribe <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups comp.lang.python
Message-ID <mailman.5777.1390303676.18130.python-list@python.org> (permalink)
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

Show key headers only | View raw

On Tue, Jan 21, 2014 at 10:17 PM, Robert Voigtländer
<r.voigtlaender@gmail.com> 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

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

Thread

which data structure to use? Robert Voigtländer <r.voigtlaender@gmail.com> - 2014-01-21 03:17 -0800
  Re: which data structure to use? Chris Angelico <rosuav@gmail.com> - 2014-01-21 22:27 +1100
  Re: which data structure to use? Ben Finney <ben+python@benfinney.id.au> - 2014-01-21 22:34 +1100
  Re: which data structure to use? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-01-21 11:49 +0000
    Re: which data structure to use? Robert Voigtländer <r.voigtlaender@gmail.com> - 2014-01-21 05:38 -0800
      Re: which data structure to use? Robert Voigtländer <r.voigtlaender@gmail.com> - 2014-01-21 05:43 -0800
        Re: which data structure to use? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-01-21 18:03 +0000
      Re: which data structure to use? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-01-21 13:59 +0000
      Re: which data structure to use? Peter Otten <__peter__@web.de> - 2014-01-21 15:09 +0100
      Re: which data structure to use? Peter Otten <__peter__@web.de> - 2014-01-21 15:19 +0100
        Re: which data structure to use? Robert Voigtländer <r.voigtlaender@gmail.com> - 2014-01-21 07:33 -0800
          Re: which data structure to use? Robert Voigtländer <r.voigtlaender@gmail.com> - 2014-01-21 07:37 -0800
            Re: which data structure to use? Peter Otten <__peter__@web.de> - 2014-01-21 19:39 +0100
              Re: which data structure to use? Robert Voigtländer <r.voigtlaender@gmail.com> - 2014-01-22 01:38 -0800

csiph-web