Author: Andrew Dados
Date: 14:48:32 02/20/03
Go up one level in this thread
On February 20, 2003 at 16:30:55, Ricardo Gibert wrote:
>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.
>
Eds problem can be improved in 2 ways imo.
We know hashtable move + 2 killers produce cutoff in about 95% in FH nodes.
So if there is HT move and/or killers are legal Ed can postpone generating that
moveordering table.
For FL nodes all moves will be checked. So for 30 moves it is 900 comparisons in
'naive' approach. You are definitely right here that array is sparsely
populated. Lets limit our values to 0..128 (shr is fast).
I actually took 20 min and wrote simple routine to compare times to return n-th
best move. In array of 128 possible values with 30 moves distribution sort
breaks even when returning 5th best (it takes about 2x more time when all we
request is first element in sorted order).
However it was over _4 times_ faster when we want all 30 elements sorted (FL
nodes).
As usual YMMV - asm optimization may change those fugures.
-Andrew-
>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.
Thanks, english is not my native language.
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.