Author: Ricardo Gibert
Date: 13:30:55 02/20/03
Go up one level in this thread
On February 20, 2003 at 15:30:45, Peter McKenzie wrote:
><snip>
>>
>>Remember the trick to sort values in small range WITHOUT actually sorting
>>anything?
>
>No time to read in detail, but I assume you will be describing some sort of
>radix sort.
>
>Peter
>
>>
>>First consider how could you do it IF your 'preeval' returned all unique values
>>( means all V=table[move_to] - table[move_from] were unique):
>>
>>For this we define move_number to be array [0..255] of move NUMBERS, not values
>>(that is pointers to actual move array). You need to initialize it to some
>>unique value if your array of moves is zero-based, so make it 255
>>
>> Then all you do for each move is:
>>
>>(N means move number in move list)
>>move_number[table[move_to] - table[move_from]]=N;
>>
>>now to get them all in sorted order:
>>for (i=254;i>0;i--)
>> if (move_number[i] !=255) search(moves[i]);
>>
>>
>>Now if values are not unique then move_number table is not enough.
>>We need to keep array of all move values and another array of unique flags.
>>Hopefully those arrays don't need to be initialized:
>>
>>unsorted_values,notunique: array [0..255] of char;
>>
>>now loop generating move values will look:
>>
>>temp v,moveno: char;
>>
>>initialize_move_number_to_255;
>>moveno=0;
>>for each moveno :
>>{
>> v = table[move_to] - table[move_from];
>> if (move_number[v]==255)
>> { //first move of value v:
>> move_number[v]=moveno;
>> notunique[v]=0;
>> } else
>> { //move with value c was previously generated;
>> notunique[v]++;
>> }
>> unsorted_values[moveno]=v;
>>moveno++;
>>}
>>
>>----
>> Now to get it all in sorted order:
This is the problem. With perhaps only 40 legal moves scattered accross a 256
element array, it will be much slower going thru it than to do what Ed is
already doing.
To make it work better, you would need to index by the 5 highest order bits to
shrink the array from 256 elements to 32 (or maybe 4 bits for 16 elements would
be even better) so that the array is not so sparsely populated.
Still, it is probably all too much much work for so few moves to sort. Sometimes
the naive algorithm is best.
BTW, the sort you describe is known by many names: bin sort, distribution sort,
histogram sort, etc.
>>
>>for (i=254;i>0;i--)
>> if (move_number[i] != 255)
>>{
>> search_move(move_number[i]);
>> if (notunique[i])
>> //here need to loop through unsorted_values array starting from
>>move_number[i]+1
>> for (k=move_number[i]+1;k<255;k++)
>> if (unsorted_values[k] == i) search_move(k);
>>
>>}
>>
>>of course you may want to optimize that pseudocode :)
>>====================================================
>>
>>
>>obvious note: in this pseudocode value of move can't be 0; it is easy to change
>>that.
>>
>>
>>-Andrew-
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.