Author: Oliver Roese
Date: 19:21:25 10/19/99
Go up one level in this thread
On October 18, 1999 at 23:34:04, Robert Hyatt wrote: (...) >>BTW, by glancing through an older crafty version i stumpeld across a remarkable >>comment there. Dr. Hyatt says there, that Bubblesort has outperformed all other >>sortalgorithms for a particular sortproblem! (...) >>Is there a explanation to that? Thanks for your response! (I have read the other articles, but i will answer them here) >yes... a couple. First, it is not uncommon to have one reasonable capture, >and it is very common to have only 2-3. Compare bubble-sort (with early exit) >to quicksort. But compare the total number of instructions executed, not the >number of items/comparisons done. You'll get the idea quickly. Bubble sort >is very good for really small N. And captures are _always_ small N. > Ok, but i had this idea already. In general nobody uses quicksort for small sortproblems, since the overhead is too large. >Second, bubble sort runs with two branches in the loop, counting the loop >branch itself. quicksort is much worse. > >Third, bubble sort is very small, with the resulting small cache footprint, >which avoids dislodging other important data in the small L1/L2 cache. > That sounds like the explanation. Normally one was in habit to use insertionsort for small sortproblems. For example STL switches to insertionsort if there are less than __stl_threshold = 16 elements. An older qsort from my libc switches if n <= 4 (i thought this was too late). I conducted an experiment with simple integers a few years ago and came to n = 12. There are all wrong?? I took a look at insertionsort and found out, that it scans its elements forward and _backwards_. On nowadays hardware this is extremly problematic. Maybe one could learn here something... >If I knew that N would be 40, or if I couldn't generate captures by themselves >and had to sort all the moves, I would use something else. But when N=1,2,3 >(typically) bubble-sort is impossible to beat. That was completely new to me! Oliver
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.