NotificationsYou must be signed in to change notification settings
Fork6
Star31

Commit59464bd

committed

Improve implementation of GEQO's init_tour() function.

Rather than filling a temporary array and then copying values to theoutput array, we can generate the required random permutation in-placeusing the Fisher-Yates shuffle algorithm. This is shorter as well asmore efficient than before. It's pretty unlikely that anyone wouldnotice a speed improvement, but shorter code is better.Nathan Wagner, edited a bit by me

1 parent7bd099d commit59464bdCopy full SHA for 59464bd

File tree

1 file changed

+19

-25

lines changed

src/backend/optimizer/geqo
- geqo_recombination.c

1 file changed

+19

-25

lines changed

`‎src/backend/optimizer/geqo/geqo_recombination.c`

Lines changed: 19 additions & 25 deletions

Original file line number	Diff line number	Diff line change
`@@ -29,39 +29,33 @@`
`29`	`29`	`*`
`30`	`30`	`* Randomly generates a legal "traveling salesman" tour`
`31`	`31`	`* (i.e. where each point is visited only once.)`
`32`		`- * Essentially, this routine fills an array with all possible`
`33`		`- * points on the tour and randomly chooses the 'next' city from`
`34`		`- * this array. When a city is chosen, the array is shortened`
`35`		`- * and the procedure repeated.`
`36`	`32`	`*/`
`37`	`33`	`void`
`38`	`34`	`init_tour(PlannerInforoot,Genetour,intnum_gene)`
`39`	`35`	`{`
`40`		`-Gene*tmp;`
`41`		`-intremainder;`
`42`		`-intnext,`
`43`		`-i;`
	`36`	`+inti,`
	`37`	`+j;`
`44`	`38`
`45`		`-/* Fill a temp array with the IDs of all not-yet-visited cities */`
`46`		`-tmp= (Gene)palloc(num_genesizeof(Gene));`
`47`		`-`
`48`		`-for (i=0;i<num_gene;i++)`
`49`		`-tmp[i]= (Gene) (i+1);`
`50`		`-`
`51`		`-remainder=num_gene-1;`
	`39`	`+/*`
	`40`	`+ * We must fill the tour[] array with a random permutation of the numbers`
	`41`	`+ * 1 .. num_gene. We can do that in one pass using the "inside-out"`
	`42`	`+ * variant of the Fisher-Yates shuffle algorithm. Notionally, we append`
	`43`	`+ * each new value to the array and then swap it with a randomly-chosen`
	`44`	`+ * array element (possibly including itself, else we fail to generate`
	`45`	`+ * permutations with the last city last). The swap step can be optimized`
	`46`	`+ * by combining it with the insertion.`
	`47`	`+ */`
	`48`	`+if (num_gene>0)`
	`49`	`+tour[0]= (Gene)1;`
`52`	`50`
`53`		`-for (i=0;i<num_gene;i++)`
	`51`	`+for (i=1;i<num_gene;i++)`
`54`	`52`	`{`
`55`		`-/* choose value between 0 and remainder inclusive */`
`56`		`-next=geqo_randint(root,remainder,0);`
`57`		`-/* output that element of the tmp array */`
`58`		`-tour[i]=tmp[next];`
`59`		`-/* and delete it */`
`60`		`-tmp[next]=tmp[remainder];`
`61`		`-remainder--;`
	`53`	`+j=geqo_randint(root,i,0);`
	`54`	`+/* i != j check avoids fetching uninitialized array element */`
	`55`	`+if (i!=j)`
	`56`	`+tour[i]=tour[j];`
	`57`	`+tour[j]= (Gene) (i+1);`
`62`	`58`	`}`
`63`		`-`
`64`		`-pfree(tmp);`
`65`	`59`	`}`
`66`	`60`
`67`	`61`	`/* alloc_city_table`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit59464bd

File tree

1 file changed

1 file changed

`‎src/backend/optimizer/geqo/geqo_recombination.c`

0 commit comments