Nathan Wagner <nw+pg@hydaspes.if.org> writes:
> I have two patches to make the geqo initialization and mutation
> slightly better.
> The first adjusts the mutation swaps to avoid having to re-pick
> ties. The second changes the initialization and shuffling algorithm
> for the gene array to use an in-place Fisher-Yates shuffling
> algorithm.
I took a quick look at this.
I'm not very impressed with the first patch: it might save a few
geqo_randint() calls, but it seems to do so at the price of making the
swap choices less random --- for instance it sure looks to me like the
last array element is now less likely to participate in swaps than
other elements. Unless you can prove that actually the swapping is
still unbiased, I'm inclined to reject this part.
As for the second part, I had to look up Fisher-Yates ;-) but after
having read Wikipedia's entry about it I think this is a good change.
The code's shorter and more efficient, and it should mathematically
provide an equally-unbiased initial shuffle. It could do with a better
comment, and I'd be inclined to handle the first element outside the loop
rather than uselessly computing geqo_randint(0,0), but those are trivial
changes.
Having said that, though, I believe that it's also probably a
*different* initial shuffle, which may well mean that GEQO gives
different plans in some cases. That doesn't bother me as long as
we only make the change in HEAD, but does anyone want to complain?
regards, tom lane