Author: Peter McKenzie
Date: 12:30:45 02/20/03
Go up one level in this thread
<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:
>
>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.