Author: Robert Hyatt
Date: 13:38:07 10/25/99
Go up one level in this thread
On October 25, 1999 at 16:05:20, Michel Langeveld wrote: >On October 25, 1999 at 14:48:54, Dann Corbit wrote: > >>On October 25, 1999 at 12:26:37, Michel Langeveld wrote: >>>On October 25, 1999 at 10:17:53, Dann Corbit wrote: >>>>On October 23, 1999 at 10:36:40, Robert Hyatt wrote: >>>> >>>>>On October 22, 1999 at 10:03:29, Dann Corbit wrote: >>>>> >>>>>>Change to binary insertion and you will see a much bigger benefit. >>>>> >>>>>I tried both (from Knuth Sorting and Searching). Binary is very bad for >>>>>lists that have 1-5 entries max. from testing on my machine. Simple >>>>>insertion is no faster than the bubble sort I used, but it also turns out >>>>>to be no slower either, after testing Crafty over 300 different positions. >>>>> >>>>>I think I'll leave insertion in, to prevent such discussions in the >>>>>future, however. :) >>>>I have found a new modification to insertion sort (binary or linear) that will >>>>make a large improvement in speed. It has to do with the data movements to >>>>perform the actual insertion. By delaying the insertion, I can do all data >>>>movements as a single permutation and never move any element more than once. It >>>>won't work for big lists though, since the code size is O(n!). With just ten >>>>items there are a million leaves in the tree. However, for very small sublists >>>>I think it will do very well. >>> >>>Best way to prove your statement is code it, and prove it's faster! >>>Good news by the way. >>Got the idea from a web page. Here is an example for n=3. Number of >>comparisons is O(n*log(n)). For the left branch (1,2,3) do not move anything. >>For (1,3,2) permute the 3 & 2. For (3,1,2) and (2,3,1) we must move all of >>them, since none is in the right place, and for (3,2,1) we permute 1 & 3. It is >>very simple, really. I have a code generator to write the output, but I think I >>can simplify it a lot and use the inline keyword (it's C99). The colon in the >>diagram means compare. We don't actually compare twice (e.g. if I test for 1 < >>2 I do not have another test for 2<1 {because that only finds equal which is >>unlikely and therefore a mostly wasted comparison} >> >> 1:2 >> / \ >> < / > \ >> / \ >> 2:3 1:3 >> / \ / \ >> < / > \ < / > \ >> / \ / \ >> 1,2,3 1:3 2,1,3 2:3 >> / \ / \ >> < / > \ < / > \ >> / \ / \ >> 1,3,2 3,1,2 2,3,1 3,2,1 > >Seems to be an hardcoded sort and indeed worth trying!! >Maybe writing it immediatly in assembly will gain an extra kind of speed. >Did you btw. run an profile lately on the source of Crafty 16.19? >I'm wondering which source has to be analyzed to gain an extra speed. > >MichelLangeveld Evaluate() and its children use more CPU time than everything else put together in normal positions. IE > 50% of total time is spent in the various Evaluation() functions.
This page took 0.01 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.