fastest data structure for retrieving objects identified by (x,y) tuple?

Path	csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed5.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path	<bsj@abzinc.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.018
X-Spam-Evidence	'H': 0.96; 'S': 0.00; 'objects,': 0.07; "object's": 0.09; 'pointers': 0.09; 'slow.': 0.09; 'value.': 0.15; 'doing,': 0.16; 'neighbor,': 0.16; 'pairs': 0.16; 'pairs,': 0.16; 'received:192.168.1.16': 0.16; 'subject:fastest': 0.16; 'example': 0.23; 'testing': 0.24; 'header:User-Agent:1': 0.26; 'environment.': 0.27; 'scale': 0.27; 'skip:# 10': 0.27; "doesn't": 0.28; 'obj': 0.29; 'objects': 0.29; 'null': 0.33; 'subject:data': 0.33; 'to:addr:python-list': 0.33; 'that,': 0.34; "can't": 0.34; 'or,': 0.34; 'fastest': 0.35; 'identified': 0.35; 'subject:?': 0.35; 'there': 0.35; 'too': 0.36; 'subject: (': 0.36; 'store': 0.38; 'to:addr:python.org': 0.39; 'received:192': 0.39; 'received:192.168': 0.40; 'header:Received:5': 0.40; 'subject:,': 0.81; '2400': 0.84; 'alone,': 0.84; 'received:98.172': 0.84
Date	Wed, 03 Oct 2012 18:30:24 -0400
From	Benjamin Jessup <bsj@abzinc.com>
User-Agent	Mozilla/5.0 (Windows NT 6.1; WOW64; rv:15.0) Gecko/20120907 Thunderbird/15.0.1
MIME-Version	1.0
To	python-list@python.org
Subject	fastest data structure for retrieving objects identified by (x,y) tuple?
Content-Type	text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding	7bit
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	<http://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	<http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.1777.1349303447.27098.python-list@python.org> (permalink)
Lines	22
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1349303447 news.xs4all.nl 6946 [2001:888:2000:d::a6]:38217
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:30701

Show key headers only | View raw

I have a group of objects identified by unique (x,y) pairs and I want to 
find out an object's "neighbors" in a matrix of size 2400 x 2400.
        #############
        #obj#   #   #
        #############
        #   #   #obj#      3 x 3 Example
        #############
        #   #   #   #
        #############
There is either a neighbor, or a null value. I always know the (x,y) 
pair to check the neighbors of, so is doing,
 >> obj = grid[x][y] #lists, doesn't scale with num of objects
or,
 >> obj = grid.get((x,y),None) #dictionary, scales with num of objects
the fastest? I can't seem to find a conclusion by testing each alone, 
then in the full environment. Is it that, depending on the number of 
objects, each has an advantage?

I know the fastest way to retrieve them would be to have them store 
pointers to their neighbors, then use those for retrieval. When large 
numbers of objects are changing their (x,y) pairs, rebuilding the 
pointers is too slow.

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

Thread

fastest data structure for retrieving objects identified by (x,y) tuple? Benjamin Jessup <bsj@abzinc.com> - 2012-10-03 18:30 -0400
  Re: fastest data structure for retrieving objects identified by (x,y) tuple? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-04 01:58 +0000
    Re: fastest data structure for retrieving objects identified by (x,y) tuple? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-04 02:25 +0000
    Re: fastest data structure for retrieving objects identified by (x,y) tuple? Thomas Rachel <nutznetz-0c1b6768-bfa9-48d5-a470-7603bd3aa915@spamschutz.glglgl.de> - 2012-10-04 18:11 +0200
      Re: fastest data structure for retrieving objects identified by (x,y) tuple? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-04 23:37 +0000

csiph-web