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.
Diffs against commit 49124613f134b04594b1a5c46368eb0a5db16d4b
(i.e. tip of master as of when I re-made the diff).
On my system the patches pass a ./configure; make; make check
--
nw
>From c7f3c7cc37f943481b2358149210789be3d39ee9 Mon Sep 17 00:00:00 2001
From: Nathan Wagner <n...@hydaspes.if.org>
Date: Sun, 21 Sep 2014 09:30:01 +0000
Subject: [PATCH 1/2] cleanup geqo_mutation.c
Avoid a possible random number collision by choosing random
ranges better. This will potentially change the output
of the algorithm since it avoids extra calls to geqo_randint().
---
src/backend/optimizer/geqo/geqo_mutation.c | 8 +++-----
1 file changed, 3 insertions(+), 5 deletions(-)
diff --git a/src/backend/optimizer/geqo/geqo_mutation.c
b/src/backend/optimizer/geqo/geqo_mutation.c
index 1a06d49..c78bd2c 100644
--- a/src/backend/optimizer/geqo/geqo_mutation.c
+++ b/src/backend/optimizer/geqo/geqo_mutation.c
@@ -43,20 +43,18 @@ geqo_mutation(PlannerInfo *root, Gene *tour, int num_gene)
int num_swaps = geqo_randint(root, num_gene / 3, 0);
Gene temp;
-
while (num_swaps > 0)
{
swap1 = geqo_randint(root, num_gene - 1, 0);
- swap2 = geqo_randint(root, num_gene - 1, 0);
+ swap2 = geqo_randint(root, num_gene - 2, 0);
- while (swap1 == swap2)
- swap2 = geqo_randint(root, num_gene - 1, 0);
+ if (swap2 >= swap1)
+ swap2++;
temp = tour[swap1];
tour[swap1] = tour[swap2];
tour[swap2] = temp;
-
num_swaps -= 1;
}
}
--
2.5.0
>From 47979bb844eda3821f08c1f00afc081ee0a3a260 Mon Sep 17 00:00:00 2001
From: Nathan Wagner <n...@hydaspes.if.org>
Date: Sun, 21 Sep 2014 13:02:48 +0000
Subject: [PATCH 2/2] rewrote array shuffler for geqo_recombination
This simplifies the array shuffling by doing it inplace
and eliminating a memory allocation and array initialization.
The output is identical in the sense that it still randomizes
an array, but the actual shuffled array will be different.
---
src/backend/optimizer/geqo/geqo_recombination.c | 32 +++++++------------------
1 file changed, 9 insertions(+), 23 deletions(-)
diff --git a/src/backend/optimizer/geqo/geqo_recombination.c
b/src/backend/optimizer/geqo/geqo_recombination.c
index 652fadc..b327776 100644
--- a/src/backend/optimizer/geqo/geqo_recombination.c
+++ b/src/backend/optimizer/geqo/geqo_recombination.c
@@ -37,31 +37,17 @@
void
init_tour(PlannerInfo *root, Gene *tour, int num_gene)
{
- Gene *tmp;
- int remainder;
- int next,
- i;
+ int i, j;
- /* Fill a temp array with the IDs of all not-yet-visited cities */
- tmp = (Gene *) palloc(num_gene * sizeof(Gene));
-
- for (i = 0; i < num_gene; i++)
- tmp[i] = (Gene) (i + 1);
-
- remainder = num_gene - 1;
-
- for (i = 0; i < num_gene; i++)
- {
- /* choose value between 0 and remainder inclusive */
- next = geqo_randint(root, remainder, 0);
- /* output that element of the tmp array */
- tour[i] = tmp[next];
- /* and delete it */
- tmp[next] = tmp[remainder];
- remainder--;
+ /* shuffle tour in-place, uses Fisher-Yates inside-out algorithm */
+ for (i=0; i < num_gene; i++) {
+ j = geqo_randint(root, i, 0);
+ /* we could skip the compare and just assign */
+ if (i != j) {
+ tour[i] = tour[j];
+ }
+ tour[j] = (Gene) i+1;
}
-
- pfree(tmp);
}
/* alloc_city_table
--
2.5.0
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
