Advice on sorted list please - golang-nuts

The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion Advice on sorted list please
Date: Wed, 16 May 2012 05:22:13 -0700 (PDT)
From: Ethan Burns <burns.et...@gmail.com>
To: golang-nuts@googlegroups.com
Message-ID: <21844597.1325.1337170933409.JavaMail.geo-discussion-forums@ynja13>
In-Reply-To: <23437138.170.1337130567840.JavaMail.geo-discussion-forums@pbctd3>
References: <23437138.170.1337130567840.JavaMail.geo-discussion-forums@pbctd3>
Subject: Re: Advice on sorted list please
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_1323_5129782.1337170933407"

------=_Part_1323_5129782.1337170933407
Content-Type: multipart/alternative; 
	boundary="----=_Part_1324_14910831.1337170933408"

------=_Part_1324_14910831.1337170933408
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit

Hi si guy,

Are you using A* for pathfinding in a grid?  If so, there are two good 
options for the open list depending on whether or not you allow for 
non-integer costs (it is common to use sqrt(2) for diagonal movements in 
grids).  If you allow for non-integer costs then I would recommend using 
container/heap as your open list, with the node with the minimum cost + 
heuristic at the front.  This will give you O(lg n) for most operations 
used by A* (push, pop, remove).  If you are only considering integer-base 
costs then you may want to use a data structure called a 1-level bucket 
priority queue.  A 1-level bucket priority queue is just a simple array of 
lists and gives you constant time insertion, and if you have some fixed 
limit on the number of priority values you also get constant time removal. 
 The 1-level bucket priority queue can make A* significantly faster if it's 
applicable for your problem.

Also, I am guessing that you want via x,y values in order to perform 
lookups in your closed list (to see if you have visited a node already). 
 As John said, a map will work here, however, I would recommend using a 
slice instead as it will be quite a bit faster than a map and you can 
allocate the entire slice upfront, effectively removing all allocations 
from the inner-loop of your A*.

One last thing, I see that you got a 6x improvement by using parallelism: 
that is great!  I do want to warn you that your improvement may be because 
you are no longer finding optimal solutions.  If you don't care about 
optimality and if the paths look good then this is probably not a big 
issue, however, it may be something to think about.  Usually a better and 
slightly more principled technique for relaxing optimality to improve the 
performance of an A*-like algorithm is to multiply the heuristic by some 
value > 1.  This will guarantee that your solution is within a constant 
factor (the factor is the value by which you multiplied the heuristic) of 
optimal.

By the way, Nathan Sturtevant has some interesting resources for grid-based 
pathfinding at http://movingai.com/

Best,
Ethan

On Tuesday, May 15, 2012 9:09:27 PM UTC-4, si guy wrote:
>
> Hi all, I'm trying to optimize an A* implementation and I was going to 
> start by keeping the openList of nodes sorted. I'd like the same data 
> structure to allow for quick access to nodes of arbitrary coordinates. I'm 
> not a compsci grad so I have no idea what method would be the most 
> all-round efficient. I was thinking some sort of two-faced hash map of 
> pointers(combining cost and coordinates somehow) but I'm reluctant to spend 
> lots of time studying a method which may not be best. Any pointers on which 
> data structure to study first?
>
> Thanks.
> -Simon Watt
>

------=_Part_1324_14910831.1337170933408
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

Hi si guy,<div><br></div><div>Are you using A* for pathfinding in a grid? &=
nbsp;If so, there are two good options for the open list depending on wheth=
er or not you allow for non-integer costs (it is common to use sqrt(2) for =
diagonal movements in grids). &nbsp;If you allow for non-integer costs then=
 I would recommend using container/heap as your open list, with the node wi=
th the minimum cost + heuristic at the front. &nbsp;This will give you O(lg=
 n) for most operations used by A* (push, pop, remove). &nbsp;If you are on=
ly considering integer-base costs then you may want to use a data structure=
 called a 1-level bucket priority queue. &nbsp;A 1-level bucket priority qu=
eue is just a simple array of lists and gives you constant time insertion, =
and if you have some fixed limit on the number of priority values you also =
get constant time removal. &nbsp;The 1-level bucket priority queue can make=
 A* significantly faster if it's applicable for your problem.<br></div><div=
><div><br></div><div>Also, I am guessing that you want via x,y values in or=
der to perform lookups in your closed list (to see if you have visited a no=
de already). &nbsp;As John said, a map will work here, however, I would rec=
ommend using a slice instead as it will be quite a bit faster than a map an=
d you can allocate the entire slice upfront, effectively removing all alloc=
ations from the inner-loop of your A*.</div><div><br></div><div>One last th=
ing, I see that you got a 6x improvement by using parallelism: that is grea=
t! &nbsp;I do want to warn you that your improvement may be because you are=
 no longer finding optimal solutions. &nbsp;If you don't care about optimal=
ity and if the paths look good then this is probably not a big issue, howev=
er, it may be something to think about. &nbsp;Usually a better and slightly=
 more principled technique for relaxing optimality to improve the performan=
ce of an A*-like algorithm is to multiply the heuristic by some value &gt; =
1. &nbsp;This will guarantee that your solution is within a constant factor=
 (the factor is the value by which you multiplied the heuristic) of optimal=
.</div><div><br></div><div>By the way,&nbsp;Nathan Sturtevant has some inte=
resting resources for grid-based pathfinding at http://movingai.com/</div><=
div><br></div><div>Best,</div><div>Ethan<br><br>On Tuesday, May 15, 2012 9:=
09:27 PM UTC-4, si guy wrote:<blockquote class=3D"gmail_quote" style=3D"mar=
gin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">H=
i all, I'm trying to optimize an A* implementation and I was going to start=
 by keeping the openList of nodes sorted. I'd like the same data structure =
to allow for quick access to nodes of arbitrary coordinates. I'm not a comp=
sci grad so I have no idea what method would be the most all-round efficien=
t. I was thinking some sort of two-faced hash map of pointers(combining cos=
t and coordinates somehow) but I'm reluctant to spend lots of time studying=
 a method which may not be best. Any pointers on which data structure to st=
udy first?<p>Thanks.<br>-Simon Watt</p></blockquote></div></div>
------=_Part_1324_14910831.1337170933408--

------=_Part_1323_5129782.1337170933407--
Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
Account Options
