Author: Michel Langeveld
Date: 13:05:20 10/25/99
Go up one level in this thread
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
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.