   using binary heap slower than searching list?
  I've been trying to increase the speed of my A* implementation by using a binary min-heap for the open list, however in general; unless the open list becomes very large; simply pushing new nodes onto the list; and searching for the smallest one each pass of the algorithm seems to perform better?Does this seem correct?   
  Yes, frequently the theoretical best data structure for the job isn't as quick for small problems as a more basic algorithm.  If you want to get the benefits from both, you can have your program switch strategies depending on the size of the problem.   ;  How is your heap implemented? Unless it's as fixed continuous array, then the cost of allocation and potentially memory fragmentation, as well as added overhead will be overshadowing benefits from improved search performance.   ;  It is (AS3) I personally can't stand working in actionscript, but it's the target language sadly.Aslong as the number of objects inserted doesn't exceed the value of size passed to the constructor, the array will remain fixed and continuous (and if not, bound checking is done automatically to resize it if needed)package data{public class MBHeap{private var heap:Array;private var heapl:uint;/** Constructor **/public function MBHeap(size:uint=0){heap = new Array(size);heapl = 0;}public function empty():Boolean{return heapl==0;}public function clear():void{heapl = 0;}public function insert(dat:*,ind:*):void{var h:uint = heapl++;heap[h] = new Node(dat,ind);var par:uint;var a:Node, b:Node;while(h!=0 && (a = heap[par=((h-1)>>1)]).ind >  (b = heap[h]).ind){heap[h] = a;heap[h=par] = b;}}public function pop():*{var val:Node = heap[0];var hi:uint = heapl-1;heap[0] = heap[hi];heap[hi] = val;heapl--;hi = 0;var h:Node = heap[0];while(true){var ai:uint = (hi<<1)+1var bi:uint = ai+1;var a:Node = heap[ai];if(bi<heapl){var b:Node = heap[bi];if(a.ind<b.ind){if(h.ind>a.ind){heap[hi] = a;heap[hi=ai] = h;}else break;}else{if(h.ind>b.ind){heap[hi] = b;heap[hi=bi] = h;}else break;}}else if(ai<heapl){if(h.ind>a.ind){heap[hi] = a;heap[hi=ai] = h;}else break;}else break;}return val.data;}}}class Node{public var data:*;public var ind:*;public function Node(dat:*, indd:*){data = dat;ind = indd;}};  Everytime you push a new node into the set, you do N number of copies, which is pretty expensive, compared to a list where an insertion is near constant time ( just assign a few ptrs and your done, in AC this is proably done automatically in background for you ). If the list is small, as you'e mentioned, the search through the list has a fixed overhead of derefrencing some ptrs to iterate through and checking for end of the list. This is less costly than the copies (even if they are just ptr copies) the binary heap performs for each insertion.Since the open set is so dynamic ( grows and shirnks with resepect to the search ), a binary heap isn't the best for this applicaiton.If AC has something like the STL prioiry queues, which are partially sorted lists which only guarentee the first element is sorted, it would be best, also something like STLs map which also has a sort guarentee on the elements, but for small searchs the overhead of both would outweight the benifits, again.In lower level lanagues like C++ and C you can create specalized data strcutures just for this problem, but this proably isn't available to AC.Good Luck!-ddn   ;Quote:Original post by ddn3Everytime you push a new node into the set, you do N number of copies, which is pretty expensive, compared to a list where an insertion is near constant time ( just assign a few ptrs and your done, in AC this is proably done automatically in background for you ).I'm afraid you are mistaken on a number of comments in your post. For example, his push implementation only does O(log(n)) copies, not O(n). That is afterall, how a heap works, and his slightly cryptic implementation (could just be the language) does appear to have the right basic approach.Quote:If the list is small, as you'e mentioned, the search through the list has a fixed overhead of derefrencing some ptrs to iterate through and checking for end of the list. This is less costly than the copies (even if they are just ptr copies) the binary heap performs for each insertion.Simpler data structures always tend to be faster for very small data sets. However I would expect that for somewhere around 15-30 items that a heap would be faster, and for anything less than that, it's already pretty fast either way anyway. The preferred approach which is to use a heap for A* and only if profiling determines that speed is inadequate, and that using a list for smaller numbers of items does improve it, should one consider using both. Otherwise it's just more potential for bugs and perhaps no speed gain at all.Quote:Since the open set is so dynamic ( grows and shirnks with resepect to the search ), a binary heap isn't the best for this applicaiton.On the contrary, a binary heap is about the most efficient method there is for the A* algorithm. That is afterall, why it's the common choice for this, and why it was recommended to him.Quote:If AC has something like the STL prioiry queues, which are partially sorted lists which only guarentee the first element is sorted, it would be best, also something like STLs map which also has a sort guarentee on the elements, but for small searchs the overhead of both would outweight the benifits, again.Ah, I see the lack of understanding that has lead you to some wrong conclusions. A priority queue basically is a heap. 99.9% of the time that is how a priority queue is implemented. So much so that the terms 'heap' and 'priority queue' are pretty much synnonymous. A SC++L heap is more efficient that a set for the operations required here, for reasons such as the items are contiguous in memory, and there is no per-item overhead for example.Quote:In lower level lanagues like C++ and C you can create specalized data strcutures just for this problem, but this proably isn't available to AC.In C++ you should never write your own heap. The SC++L already has all the heap algorithms built in.I think the problem here is that push and pop are incorrectly implemented. Pop is definitely wrong as it shoudn't look anything like that. Push shouldn't be assigning to two items in the loop. It should only do one assignment in the loop, and one after the loop.A quick google search has turned up a reasonable implementation here.   ;Quote:Original post by iMalcI think the problem here is that push and pop are incorrectly implemented.I replaced my implementation with a slight varient of the one in the link you posted (the one in linked had arrays starting at index 1) and also a couple slight optimisations based on the language choice, and it does perform alot better than my own implementation;as it now stands for an average length search, the heap will either perform better; to slightly worse than the list: i can imagine this is due to the individual search wherein the conditions are optimal for the lowest cost node to be always very near the beginning of the list allowing it to perform better.   ;  I probably shoudn't have said "incorrectly implemented" earlier, as I assume it was actually working, but simply wasn't very optimal. It sounds like it's performing as I'd expect now.I hadn't noticed that the one I linked to was one-based. I'm glad you were able to translate that to zero-based. Mind you I didn't know whether actionscript was zero or one based anyway.   ;  Thanks for the info iMalc, good stuff. -ddn   