Author: Heiner Marxen
Date: 05:31:14 02/20/03
Go up one level in this thread
On February 20, 2003 at 05:38:44, S. Loinjak wrote: >how about a reduced heap sort algorithm: > > >1) insert all entries in a sorted heap [can be implemented as array] > >(binary tree where all parents have higher priority than their 2 children - at >the end the element with highest prio is on top [i.e. at first place in an array >like heap]) > >costs: n*log(n) in worst case (where n is the number of current entries in the >heap) > >2) get the entry with highest prio from top of the heap (constant costs) and >afterwards put the last element on the top of the heap and let it sink to the >place where it belongs according to its priority > >now the heap property (parents have higher prio than children) is fullfilled >again and you can get the next most important entry again from top of the heap > >costs: n*log*n > > > >Of course this method is only worth considering if you need several elements >with highest (remaining) prio and not only the first one. > > ><details: search for e.g. priority queues, heap, heapify, sink> > >--> http://www.onthenet.com.au/~grahamis/int2008/week11/lect11.html > > >Sini > >P.S: I've used this method successfully in a queue simulation but also intend to >use it in my chess engine if I'll ever write one. Several thoughts ... Using a priority queue asymtotically is a very good solution. It is comparable to a n*log(n) sorting method. But... In case the list of moves is not scanned completely, but after using the first and second entries (say) we get a cut-off and junk the rest of the list, we have done all the sorting or heapifying overhead without really benefitting from it. Also, short lists (at most 5 elements or so) may be dealt fastest with with Ed's simple method. Hence, when we expect a cut off, and the list is long enough, we could pull out the first two with the simple method, and if we are still going, now start to heapify or sort. Sorting can be very fast, here: the sort key is very small (1 byte). Radix sorting comes to mind: 2 phases, each for 4 bit of the key, using 16 buckets, sound like a fast method. And swapping around your values isn't expensive, either. Besides the key you have just 2 bytes (from and to). You could combine them into one "short" to be even faster. For radix sort we want a linked list. We can get that by linking with indexes (in a single byte) instead of pointers (eating up 4 bytes each). unsigned char move_next[5000]; We could reserve the first slot to contain the start-index, and then use index 0 as the NIL-linkage. The from and to values of this reserved slot can be used for book-keeping the list status (not yet sorted / is short and shall not be sorted etc). Once we have established such a linking, we can sort by changing just the entries in move_next[]. Scanning such a list does one extra memory fetch for each step, but we avoid all scanning and skipping of already searched moves. Details and coding left as exercise for the reader :-) Cheers, Heiner
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.