Improvements Found in Sort & Prefix Codebook Programs
Table of Contents
- 1. Sort1Insertion
- 2. Sort1Cocktail
- 3. Sort1Selection2Problem
- 4. Sort1SelectionProblem
- 5. Sort1HeapProblem
- 6. Sort1Merge
- 7. Sort1Quick
- 8. Sort1Radix
- 9. Sort1Shell
- 10. Sort1ProblemTest
- 11. huffmanCodeTable.BasicHuffman
- 11.1. huffmanCodeTable.BasicHuffman12874.java
- 11.2. huffmanCodeTable.BasicHuffman15166.java
- 11.3. huffmanCodeTable.BasicHuffman26559.java
- 11.4. huffmanCodeTable.BasicHuffman27005.java
- 11.5. huffmanCodeTable.BasicHuffman298.java
- 11.6. huffmanCodeTable.BasicHuffman33602.java
- 11.7. huffmanCodeTable.BasicHuffman34364.java
- 11.8. huffmanCodeTable.BasicHuffman36263.java
- 11.9. huffmanCodeTable.BasicHuffman38736.java
- 11.10. huffmanCodeTable.BasicHuffman54714.java
- 11.11. huffmanCodeTable.BasicHuffman89650.java
- 12. Sort1Loops1Problem
- 12.1. Sort1Loops1Problem110.java
- 12.2. Sort1Loops1Problem18375.java
- 12.3. Sort1Loops1Problem203.java
- 12.4. Sort1Loops1Problem20583.java
- 12.5. Sort1Loops1Problem25484.java
- 12.6. Sort1Loops1Problem30298.java
- 12.7. Sort1Loops1Problem32245.java
- 12.8. Sort1Loops1Problem32931.java
- 12.9. Sort1Loops1Problem33583.java
- 12.10. Sort1Loops1Problem38776.java
- 12.11. Sort1Loops1Problem5465.java
- 12.12. Sort1Loops1Problem54791.java
- 12.13. Sort1Loops1Problem9214.java
- 13. Script to show improvements found
1 Sort1Insertion
Improvements
- Loop unrolling
- requires crossover & mutation
Original - /home/bck/GP/Exhaustive/Seed-Sort1Insertion.java
public class Sort1Insertion { public static Integer[] sort( Integer[] a, Integer array_size){ int i, j, index; for (i=1; i < array_size; ++i) { index=a[i]; for (j=i; j > 0 && a[j - 1] > index; j--) { a[j]=a[j - 1]; } a[j]=index; } return a; } }
1.1 Sort1Insertion18631
Improvements:
- Checks
a[0]in a seperate loop, loop unrolling
Improvement Details:
Sort1Insertion18631 100 mult 0.0 + 0.90673625 = 0.90673625 ASTNodes: 107 GPNodes: 119 xoverApplied: false xovers: 0 mutationApplied: true mutations: 2
Diff
6c6 < for (j=i; j > 0 && a[j - 1] > index; j--) { --- > for (j=i; j > 0 && a[1 - 1] > index; j--) { 9c9,17 < a[j]=index; --- > { > a[j]=index; > index=a[i]; > for (j=i; 1 > 1 - 1 && a[j - 1] > index; j--) { > a[j]=a[j - 1]; > } > a[j]=index; > } > j=index;
Diff side-by-side
public class Sort1Insertion { public class Sort1Insertion {
public static Integer[] sort( Integer[] a, Integer array_size){ public static Integer[] sort( Integer[] a, Integer array_size){
int i, j, index; int i, j, index;
for (i=1; i < array_size; ++i) { for (i=1; i < array_size; ++i) {
index=a[i]; index=a[i];
for (j=i; j > 0 && a[j - 1] > index; j--) { | for (j=i; j > 0 && a[1 - 1] > index; j--) {
a[j]=a[j - 1]; a[j]=a[j - 1];
} }
> {
a[j]=index; a[j]=index;
> index=a[i];
> for (j=i; 1 > 1 - 1 && a[j - 1] > index; j--) {
> a[j]=a[j - 1];
> }
> a[j]=index;
> }
> j=index;
} }
return a; return a;
} }
} }
1.2 Sort1Insertion46300
Improvement Details:
Sort1Insertion46300 100 mult 0.0 + 0.9079128 = 0.9079128 ASTNodes: 108 GPNodes: 120 xoverApplied: false xovers: 0 mutationApplied: true mutations: 2
Diff
6,8c6,11 < for (j=i; j > 0 && a[j - 1] > index; j--) { < a[j]=a[j - 1]; < } --- > for (j=i; j > 0 && a[1 - 1] > index; j--) a[j]=a[j - 1]; > a[j]=index; > } > for (i=1; i < array_size; ++i) { > index=a[i]; > for (j=i; 1 > 0 && a[j - 1] > index; j--) a[j]=a[j - 1];
Diff side-by-side
public class Sort1Insertion { public class Sort1Insertion {
public static Integer[] sort( Integer[] a, Integer array_size){ public static Integer[] sort( Integer[] a, Integer array_size){
int i, j, index; int i, j, index;
for (i=1; i < array_size; ++i) { for (i=1; i < array_size; ++i) {
index=a[i]; index=a[i];
for (j=i; j > 0 && a[j - 1] > index; j--) { | for (j=i; j > 0 && a[1 - 1] > index; j--) a[j]=a[j - 1];
a[j]=a[j - 1]; | a[j]=index;
} }
> for (i=1; i < array_size; ++i) {
> index=a[i];
> for (j=i; 1 > 0 && a[j - 1] > index; j--) a[j]=a[j - 1];
a[j]=index; a[j]=index;
} }
return a; return a;
} }
} }
2 Sort1Cocktail
Improvements
- Loop Perforation
- Requires crossover/deletions
Original - /home/bck/GP/Exhaustive/Seed-Sort1Cocktail.java
public class Sort1Cocktail { public static Integer[] sort( Integer[] a, Integer length){ boolean swapped; do { swapped=false; for (int i=0; i <= length - 2; i++) { if (a[i] > a[i + 1]) { int temp=a[i]; a[i]=a[i + 1]; a[i + 1]=temp; swapped=true; } } if (!swapped) { break; } swapped=false; for (int i=length - 2; i >= 0; i--) { if (a[i] > a[i + 1]) { int temp=a[i]; a[i]=a[i + 1]; a[i + 1]=temp; swapped=true; } } } while (swapped); return a; } }
2.1 Sort1Cocktail33235
Improvements:
- Loop cloning, and modified to leave gaps
- cloned and perforated loops
swapped=truereplaced withi--
Improvement Details:
Sort1Cocktail33235 100 mult 0.0 + 0.8461488 = 0.8461488 ASTNodes: 225 GPNodes: 220 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
5a6,13 > for (int i=length - 2; i >= 0; i--) { > if (a[i] > a[i + 1]) { > int temp=a[i]; > a[i]=a[i + 1]; > a[i + 1]=temp; > i--; > } > } 17c25,32 < swapped=false; --- > for (int i=length - 2; i >= 0; i--) { > if (a[i] > a[i + 1]) { > int temp=a[i]; > a[i++]=a[i + 1]; > a[i + 1]=temp; > i--; > } > }
Diff side-by-side
public class Sort1Cocktail { public class Sort1Cocktail {
public static Integer[] sort( Integer[] a, Integer length){ public static Integer[] sort( Integer[] a, Integer length){
boolean swapped; boolean swapped;
do { do {
swapped=false; swapped=false;
> for (int i=length - 2; i >= 0; i--) {
> if (a[i] > a[i + 1]) {
> int temp=a[i];
> a[i]=a[i + 1];
> a[i + 1]=temp;
> i--;
> }
> }
for (int i=0; i <= length - 2; i++) { for (int i=0; i <= length - 2; i++) {
if (a[i] > a[i + 1]) { if (a[i] > a[i + 1]) {
int temp=a[i]; int temp=a[i];
a[i]=a[i + 1]; a[i]=a[i + 1];
a[i + 1]=temp; a[i + 1]=temp;
swapped=true; swapped=true;
} }
} }
if (!swapped) { if (!swapped) {
break; break;
} }
swapped=false; | for (int i=length - 2; i >= 0; i--) {
> if (a[i] > a[i + 1]) {
> int temp=a[i];
> a[i++]=a[i + 1];
> a[i + 1]=temp;
> i--;
> }
> }
for (int i=length - 2; i >= 0; i--) { for (int i=length - 2; i >= 0; i--) {
if (a[i] > a[i + 1]) { if (a[i] > a[i + 1]) {
int temp=a[i]; int temp=a[i];
a[i]=a[i + 1]; a[i]=a[i + 1];
a[i + 1]=temp; a[i + 1]=temp;
swapped=true; swapped=true;
} }
} }
} }
while (swapped); while (swapped);
return a; return a;
} }
} }
2.2 Sort1Cocktail33055
Improvements:
length--added to remove passes over sorted portion of array
Improvement Details:
Sort1Cocktail33055 100 mult 0.0 + 0.9008683 = 0.9008683 ASTNodes: 234 GPNodes: 231 xoverApplied: true xovers: 4 mutationApplied: true mutations: 3
Diff
14a15,22 > for (int i=0; i + a[i] <= i - 2; i++) { > if (a[i] > a[i + 1]) { > int temp=a[i]; > a[a[a[a[a[a[a[a[a[a[a[i + a[i + i]] - 1]] + temp] - a[i + a[temp=a[a[i]] + temp] + i]]] + i] + 1]]=length + temp + 1]]=length - temp; > a[i - 1]=length--; > swapped=true; > } > } 17d24 < swapped=false; 23d29 < swapped=true; 25a32 > length--;
Diff side-by-side
public class Sort1Cocktail { public class Sort1Cocktail {
public static Integer[] sort( Integer[] a, Integer length){ public static Integer[] sort( Integer[] a, Integer length){
boolean swapped; boolean swapped;
do { do {
swapped=false; swapped=false;
for (int i=0; i <= length - 2; i++) { for (int i=0; i <= length - 2; i++) {
if (a[i] > a[i + 1]) { if (a[i] > a[i + 1]) {
int temp=a[i]; int temp=a[i];
a[i]=a[i + 1]; a[i]=a[i + 1];
a[i + 1]=temp; a[i + 1]=temp;
swapped=true; swapped=true;
} }
} }
if (!swapped) { if (!swapped) {
> for (int i=0; i + a[i] <= i - 2; i++) {
> if (a[i] > a[i + 1]) {
> int temp=a[i];
> a[a[a[a[a[a[a[a[a[a[a[i + a[i + i]] - 1]] + temp] - a[i + a[temp=a[a[i]]
> a[i - 1]=length--;
> swapped=true;
> }
> }
break; break;
} }
swapped=false; <
for (int i=length - 2; i >= 0; i--) { for (int i=length - 2; i >= 0; i--) {
if (a[i] > a[i + 1]) { if (a[i] > a[i + 1]) {
int temp=a[i]; int temp=a[i];
a[i]=a[i + 1]; a[i]=a[i + 1];
a[i + 1]=temp; a[i + 1]=temp;
swapped=true; <
} }
} }
> length--;
} }
while (swapped); while (swapped);
return a; return a;
} }
} }
2.3 Sort1Cocktail31876.java
Improvement Details:
Sort1Cocktail31876 100 mult 0.0 + 0.9760145 = 0.9760145 ASTNodes: 259 GPNodes: 248 xoverApplied: true xovers: 1 mutationApplied: true mutations: 4
Diff
6,11c6,36 < for (int i=0; i <= length - 2; i++) { < if (a[i] > a[i + 1]) { < int temp=a[i]; < a[i]=a[i + 1]; < a[i + 1]=temp; < swapped=true; --- > { > swapped=false; > for (int i=0; i <= length - 2; i++) { > if (a[i] > a[i + 1]) { > int temp=a[i]; > a[i]=a[i + 1]; > a[i + 1]=temp; > swapped=true; > } > } > if (!swapped) { > for (int i=1 - 2; i >= 0; i++) { > if (a[a[0]] > i - 1) { > int temp=i; > swapped=false; > { > if (1 > 0 + 1 - a[a[1] - i]) a[length - i]=a[i + 1]=temp; > } > swapped=true; > } > } > break; > } > swapped=false; > for (int i=length - 2; i >= 0; i--) { > if (a[i] > a[i + 1]) { > int temp=a[i]; > a[i]=a[i + 1]; > a[i + 1]=temp; > swapped=true; > } 15c40 < break; --- > return a; 19,23c44,50 < if (a[i] > a[i + 1]) { < int temp=a[i]; < a[i]=a[i + 1]; < a[i + 1]=temp; < swapped=true; --- > { > if (a[i] > a[i + 1]) { > int temp=a[i]; > a[i]=a[i + 1]; > a[i + 1]=temp; > swapped=true; > }
Diff side-by-side
public class Sort1Cocktail { public class Sort1Cocktail {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
boolean swapped; boolean swapped;
do { do {
swapped=false; swapped=false;
> {
> swapped=false;
for (int i=0; i <= length - 2; i++) { for (int i=0; i <= length - 2; i++) {
if (a[i] > a[i + 1]) { if (a[i] > a[i + 1]) {
int temp=a[i]; int temp=a[i];
a[i]=a[i + 1]; a[i]=a[i + 1];
a[i + 1]=temp; a[i + 1]=temp;
swapped=true; swapped=true;
} }
} }
if (!swapped) { if (!swapped) {
> for (int i=1 - 2; i >= 0; i++) {
> if (a[a[0]] > i - 1) {
> int temp=i;
> swapped=false;
> {
> if (1 > 0 + 1 - a[a[1] - i])
> }
> swapped=true;
> }
> }
break; break;
} }
swapped=false; swapped=false;
for (int i=length - 2; i >= 0; i--) { for (int i=length - 2; i >= 0; i--) {
if (a[i] > a[i + 1]) { if (a[i] > a[i + 1]) {
int temp=a[i]; int temp=a[i];
a[i]=a[i + 1]; a[i]=a[i + 1];
a[i + 1]=temp; a[i + 1]=temp;
swapped=true; swapped=true;
> }
> }
> }
> if (!swapped) {
> return a;
> }
> swapped=false;
> for (int i=length - 2; i >= 0; i--) {
> {
> if (a[i] > a[i + 1]) {
> int temp=a[i];
> a[i]=a[i + 1];
> a[i + 1]=temp;
> swapped=true;
> }
} }
} }
} }
while (swapped); while (swapped);
return a; return a;
} }
} }
2.4 Sort1Cocktail451.java
Improvement Details:
Sort1Cocktail451 100 mult 0.0 + 0.9760144 = 0.9760144 ASTNodes: 192 GPNodes: 183 xoverApplied: false xovers: 0 mutationApplied: true mutations: 5
Diff
6,11c6,26 < for (int i=0; i <= length - 2; i++) { < if (a[i] > a[i + 1]) { < int temp=a[i]; < a[i]=a[i + 1]; < a[i + 1]=temp; < swapped=true; --- > { > swapped=false; > for (int i=0; i <= length - 2; i++) { > if (a[i] > a[i + 1]) { > int temp=a[i]; > a[i]=a[i + 1]; > a[i + 1]=temp; > swapped=true; > } > } > if (!swapped) { > break; > } > swapped=false; > for (int i=length - 2; i >= 0; i--) { > if (a[i] > a[i + 1]) { > int temp=a[i]; > a[i]=a[i + 1]; > a[i + 1]=temp; > swapped=true; > }
Diff side-by-side
public class Sort1Cocktail { public class Sort1Cocktail {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
boolean swapped; boolean swapped;
do { do {
swapped=false; swapped=false;
> {
> swapped=false;
for (int i=0; i <= length - 2; i++) { for (int i=0; i <= length - 2; i++) {
if (a[i] > a[i + 1]) { if (a[i] > a[i + 1]) {
int temp=a[i]; int temp=a[i];
a[i]=a[i + 1]; a[i]=a[i + 1];
a[i + 1]=temp; a[i + 1]=temp;
swapped=true; swapped=true;
> }
> }
> if (!swapped) {
> break;
> }
> swapped=false;
> for (int i=length - 2; i >= 0; i--) {
> if (a[i] > a[i + 1]) {
> int temp=a[i];
> a[i]=a[i + 1];
> a[i + 1]=temp;
> swapped=true;
> }
} }
} }
if (!swapped) { if (!swapped) {
break; break;
} }
swapped=false; swapped=false;
for (int i=length - 2; i >= 0; i--) { for (int i=length - 2; i >= 0; i--) {
if (a[i] > a[i + 1]) { if (a[i] > a[i + 1]) {
int temp=a[i]; int temp=a[i];
a[i]=a[i + 1]; a[i]=a[i + 1];
a[i + 1]=temp; a[i + 1]=temp;
swapped=true; swapped=true;
} }
} }
} }
while (swapped); while (swapped);
return a; return a;
} }
} }
2.5 Sort1Cocktail4687.java
Improvement Details:
Sort1Cocktail4687 100 mult 0.0 + 0.97598076 = 0.97598076 ASTNodes: 188 GPNodes: 180 xoverApplied: false xovers: 0 mutationApplied: true mutations: 2
Diff
5,11c5,25 < swapped=false; < for (int i=0; i <= length - 2; i++) { < if (a[i] > a[i + 1]) { < int temp=a[i]; < a[i]=a[i + 1]; < a[i + 1]=temp; < swapped=true; --- > { > swapped=false; > for (int i=0; i <= length - 2; i++) { > if (a[i] > a[i + 1]) { > int temp=a[i]; > a[i]=a[i + 1]; > a[i + 1]=temp; > swapped=true; > } > } > if (!swapped) { > break; > } > swapped=false; > for (int i=length - 2; i >= 0; i--) { > if (a[i] > a[i + 1]) { > int temp=a[i]; > a[i]=a[i + 1]; > a[i + 1]=temp; > swapped=true; > }
Diff side-by-side
public class Sort1Cocktail { public class Sort1Cocktail {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
boolean swapped; boolean swapped;
do { do {
> {
swapped=false; swapped=false;
for (int i=0; i <= length - 2; i++) { for (int i=0; i <= length - 2; i++) {
if (a[i] > a[i + 1]) { if (a[i] > a[i + 1]) {
int temp=a[i]; int temp=a[i];
a[i]=a[i + 1]; a[i]=a[i + 1];
a[i + 1]=temp; a[i + 1]=temp;
swapped=true; swapped=true;
> }
> }
> if (!swapped) {
> break;
> }
> swapped=false;
> for (int i=length - 2; i >= 0; i--) {
> if (a[i] > a[i + 1]) {
> int temp=a[i];
> a[i]=a[i + 1];
> a[i + 1]=temp;
> swapped=true;
> }
} }
} }
if (!swapped) { if (!swapped) {
break; break;
} }
swapped=false; swapped=false;
for (int i=length - 2; i >= 0; i--) { for (int i=length - 2; i >= 0; i--) {
if (a[i] > a[i + 1]) { if (a[i] > a[i + 1]) {
int temp=a[i]; int temp=a[i];
a[i]=a[i + 1]; a[i]=a[i + 1];
a[i + 1]=temp; a[i + 1]=temp;
swapped=true; swapped=true;
} }
} }
} }
while (swapped); while (swapped);
return a; return a;
} }
} }
3 Sort1Selection2Problem
Improvements
- mutation
Original - /home/bck/GP/Exhaustive/Seed-Sort1Selection2Problem.java
public class Sort1Selection2Problem { public static Integer[] sort( Integer[] a, Integer length){ double p=0; int k=0; for (int i=0; i < length - 1; i++) { k=i; for (int j=i + 1; j < length; j++) { if (a[j] < a[k]) k=j; } p=a[i]; a[i]=a[k]; a[k]=(int)p; } return a; } }
3.1 Sort1Selection2Problem14720
Improvements:
i < length - 1replaced with0 < length - i
Improvement Details:
Sort1Selection2Problem14720 100 mult 0.0 + 0.8896254 = 0.8896254 ASTNodes: 73 GPNodes: 79 xoverApplied: true xovers: 3 mutationApplied: true mutations: 1
Diff
5c5 < for (int i=0; i < length - 1; i++) { --- > for (int i=k; 0 < length - i; i++) { 8c8,10 < if (a[j] < a[k]) k=j; --- > if (a[j] < a[k]) { > k=j; > }
Diff side-by-side
public class Sort1Selection2Problem { public class Sort1Selection2Problem {
public static Integer[] sort( Integer[] a, Integer length){ public static Integer[] sort( Integer[] a, Integer length){
double p=0; double p=0;
int k=0; int k=0;
for (int i=0; i < length - 1; i++) { | for (int i=k; 0 < length - i; i++) {
k=i; k=i;
for (int j=i + 1; j < length; j++) { for (int j=i + 1; j < length; j++) {
if (a[j] < a[k]) k=j; | if (a[j] < a[k]) {
> k=j;
> }
} }
p=a[i]; p=a[i];
a[i]=a[k]; a[i]=a[k];
a[k]=(int)p; a[k]=(int)p;
} }
return a; return a;
} }
} }
3.2 Sort1Selection2Problem29385
Improvements:
- The outer loop test "i < length -1" is replaced with "i < length", meaning that for each iteration length - 1 does not need to be calculated.
- This does not cause a problem, as the inner loop test "j < length" prevents attempted access past the end of the array.
Improvement Details:
Sort1Selection2Problem29385 100 mult 0.0 + 0.8893239 = 0.8893239 ASTNodes: 72 GPNodes: 77 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
5c5 < for (int i=0; i < length - 1; i++) { --- > for (int i=k; i < length; i++) { 7,8c7,12 < for (int j=i + 1; j < length; j++) { < if (a[j] < a[k]) k=j; --- > for (int j=k + 1; j < length; j++) { > if (a[j] < a[k]) { > { > } > k=j; > }
Diff side-by-side
public class Sort1Selection2Problem { public class Sort1Selection2Problem {
public static Integer[] sort( Integer[] a, Integer length){ public static Integer[] sort( Integer[] a, Integer length){
double p=0; double p=0;
int k=0; int k=0;
for (int i=0; i < length - 1; i++) { | for (int i=k; i < length; i++) {
k=i; k=i;
for (int j=i + 1; j < length; j++) { | for (int j=k + 1; j < length; j++) {
if (a[j] < a[k]) k=j; | if (a[j] < a[k]) {
> {
> }
> k=j;
> }
} }
p=a[i]; p=a[i];
a[i]=a[k]; a[i]=a[k];
a[k]=(int)p; a[k]=(int)p;
} }
return a; return a;
} }
} }
3.3 Sort1Selection2Problem19584.java
Improvement Details:
Diff
5c5 < for (int i=0; i < length - 1; i++) { --- > for (int i=k; i < length; i++) { 8c8,14 < if (a[j] < a[k]) k=j; --- > { > if (a[j] < a[k]) { > { > k=j; > } > } > }
Diff side-by-side
public class Sort1Selection2Problem { public class Sort1Selection2Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
double p=0; double p=0;
int k=0; int k=0;
for (int i=0; i < length - 1; i++) { | for (int i=k; i < length; i++) {
k=i; k=i;
for (int j=i + 1; j < length; j++) { for (int j=i + 1; j < length; j++) {
if (a[j] < a[k]) k=j; | {
> if (a[j] < a[k]) {
> {
> k=j;
> }
> }
> }
} }
p=a[i]; p=a[i];
a[i]=a[k]; a[i]=a[k];
a[k]=(int)p; a[k]=(int)p;
} }
return a; return a;
} }
} }
3.4 Sort1Selection2Problem41009.java
Improvement Details:
Diff
5c5 < for (int i=0; i < length - 1; i++) { --- > for (int i=0; i < length; i++) {
Diff side-by-side
public class Sort1Selection2Problem { public class Sort1Selection2Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
double p=0; double p=0;
int k=0; int k=0;
for (int i=0; i < length - 1; i++) { | for (int i=0; i < length; i++) {
k=i; k=i;
for (int j=i + 1; j < length; j++) { for (int j=i + 1; j < length; j++) {
if (a[j] < a[k]) k=j; if (a[j] < a[k]) k=j;
} }
p=a[i]; p=a[i];
a[i]=a[k]; a[i]=a[k];
a[k]=(int)p; a[k]=(int)p;
} }
return a; return a;
} }
} }
4 Sort1SelectionProblem
Improvements
- mutation
Original - /home/bck/GP/Exhaustive/Seed-Sort1SelectionProblem.java
public class Sort1SelectionProblem { public static Integer[] sort( Integer[] a, Integer length){ for (int currentPlace=0; currentPlace < length - 1; currentPlace++) { int smallest=Integer.MAX_VALUE; int smallestAt=currentPlace + 1; for (int check=currentPlace; check < length; check++) { if (a[check] < smallest) { smallestAt=check; smallest=a[check]; } } int temp=a[currentPlace]; a[currentPlace]=a[smallestAt]; a[smallestAt]=temp; } return a; } }
4.1 Sort1SelectionProblem30960
Improvements:
- In each outer loop,
int smallest=Integer.MAX_VALUE - so in the inner loop,
if (a[check] < smallest)will likely always be true - resulting in
smallestAt=checkalways happening. - so adding 1 to currentPlace is not needed in
int smallestAt=currentPlace + 1 - replaceing
currentPlace + 1withcurrentPlacesaves operations.
Improvement Details:
Sort1SelectionProblem30960 100 mult 0.0 + 0.9814731 = 0.9814731 ASTNodes: 206 GPNodes: 196 xoverApplied: true xovers: 1 mutationApplied: true mutations: 1
Diff
2a3,20 > for (int currentPlace=0; currentPlace < currentPlace - length; currentPlace++) { > int smallest=currentPlace; > int smallestAt=a[currentPlace]=a[currentPlace] + 0; > for (int check=0; smallest < length; check++) if (currentPlace < currentPlace) a[currentPlace]=a[currentPlace]; > int temp=a[smallestAt]; > a[smallestAt]=temp; > a[smallestAt]=temp; > } > for (int currentPlace=0; currentPlace < length - currentPlace; currentPlace++) { > int smallest=currentPlace; > int smallestAt=currentPlace + currentPlace; > for (int check=currentPlace++; check < smallest; check++) if (smallestAt < currentPlace) { > smallest+=a[check]; > } > int temp=a[currentPlace]; > a[currentPlace]=a[smallestAt]; > a[smallestAt]=temp; > } 5c23 < int smallestAt=currentPlace + 1; --- > int smallestAt=currentPlace; 7,9c25,29 < if (a[check] < smallest) { < smallestAt=check; < smallest=a[check]; --- > { > if (a[check] < smallest) { > smallestAt=check; > smallest=a[smallestAt]; > }
Diff side-by-side
public class Sort1SelectionProblem { public class Sort1SelectionProblem {
public static Integer[] sort( Integer[] a, Integer length){ public static Integer[] sort( Integer[] a, Integer length){
> for (int currentPlace=0; currentPlace < currentPlace - length; currentPlace++) {
> int smallest=currentPlace;
> int smallestAt=a[currentPlace]=a[currentPlace] + 0;
> for (int check=0; smallest < length; check++) if (currentPlace < currentP
> int temp=a[smallestAt];
> a[smallestAt]=temp;
> a[smallestAt]=temp;
> }
> for (int currentPlace=0; currentPlace < length - currentPlace; currentPlace++) {
> int smallest=currentPlace;
> int smallestAt=currentPlace + currentPlace;
> for (int check=currentPlace++; check < smallest; check++) if (smallestAt
> smallest+=a[check];
> }
> int temp=a[currentPlace];
> a[currentPlace]=a[smallestAt];
> a[smallestAt]=temp;
> }
for (int currentPlace=0; currentPlace < length - 1; currentPlace++) { for (int currentPlace=0; currentPlace < length - 1; currentPlace++) {
int smallest=Integer.MAX_VALUE; int smallest=Integer.MAX_VALUE;
int smallestAt=currentPlace + 1; | int smallestAt=currentPlace;
for (int check=currentPlace; check < length; check++) { for (int check=currentPlace; check < length; check++) {
> {
if (a[check] < smallest) { if (a[check] < smallest) {
smallestAt=check; smallestAt=check;
smallest=a[check]; | smallest=a[smallestAt];
> }
} }
} }
int temp=a[currentPlace]; int temp=a[currentPlace];
a[currentPlace]=a[smallestAt]; a[currentPlace]=a[smallestAt];
a[smallestAt]=temp; a[smallestAt]=temp;
} }
return a; return a;
} }
} }
4.2 Sort1SelectionProblem35585
Improvements:
- This line
int smallest=Integer.MAX_VALUE - will almost always result in
if (a[check] < smallest)being true on each iteration through outer loop - so set
int smallest=a[currentPlace]may save operations in changing smallest
Improvement Details:
Sort1SelectionProblem35585 100 mult 0.0 + 0.9887867 = 0.9887867 ASTNodes: 120 GPNodes: 116 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
2a3,10 > for (int currentPlace=1; currentPlace < length - 1; currentPlace++) { > int smallest=1; > int smallestAt=currentPlace; > currentPlace++; > int temp=a[currentPlace]; > a[currentPlace]=a[smallestAt]; > a[smallestAt]=temp; > } 4,9c12,21 < int smallest=Integer.MAX_VALUE; < int smallestAt=currentPlace + 1; < for (int check=currentPlace; check < length; check++) { < if (a[check] < smallest) { < smallestAt=check; < smallest=a[check]; --- > int smallest=a[currentPlace]; > int smallestAt=currentPlace; > for (int check=smallestAt; check < length; check++) { > { > if (a[check] < smallest) { > smallestAt=check; > smallest=a[check]; > } > } > {
Diff side-by-side
public class Sort1SelectionProblem { public class Sort1SelectionProblem {
public static Integer[] sort( Integer[] a, Integer length){ public static Integer[] sort( Integer[] a, Integer length){
> for (int currentPlace=1; currentPlace < length - 1; currentPlace++) {
> int smallest=1;
> int smallestAt=currentPlace;
> currentPlace++;
> int temp=a[currentPlace];
> a[currentPlace]=a[smallestAt];
> a[smallestAt]=temp;
> }
for (int currentPlace=0; currentPlace < length - 1; currentPlace++) { for (int currentPlace=0; currentPlace < length - 1; currentPlace++) {
int smallest=Integer.MAX_VALUE; | int smallest=a[currentPlace];
int smallestAt=currentPlace + 1; | int smallestAt=currentPlace;
for (int check=currentPlace; check < length; check++) { | for (int check=smallestAt; check < length; check++) {
> {
if (a[check] < smallest) { if (a[check] < smallest) {
smallestAt=check; smallestAt=check;
smallest=a[check]; smallest=a[check];
> }
> }
> {
} }
} }
int temp=a[currentPlace]; int temp=a[currentPlace];
a[currentPlace]=a[smallestAt]; a[currentPlace]=a[smallestAt];
a[smallestAt]=temp; a[smallestAt]=temp;
} }
return a; return a;
} }
} }
4.3 Sort1SelectionProblem44815
Improvements:
a[currentPlace]=a[smallestAt]requires lookup ofa[smallestAt]- but
smallestalready contains the correct value - so
a[currentPlace]=smallestdoes the job without lookup.
Improvement Details:
Sort1SelectionProblem44815 100 mult 0.0 + 0.98910284 = 0.98910284 ASTNodes: 107 GPNodes: 105 xoverApplied: true xovers: 3 mutationApplied: true mutations: 1
Diff
2a3,9 > for (int currentPlace=0; currentPlace < length; currentPlace++) { > int smallestAt=currentPlace; > currentPlace++; > int temp=a[currentPlace]; > a[currentPlace]=a[smallestAt]; > a[smallestAt]=temp; > } 5c12 < int smallestAt=currentPlace + 1; --- > int smallestAt=1; 13c20 < a[currentPlace]=a[smallestAt]; --- > a[currentPlace]=smallest;
Diff side-by-side
public class Sort1SelectionProblem { public class Sort1SelectionProblem {
public static Integer[] sort( Integer[] a, Integer length){ public static Integer[] sort( Integer[] a, Integer length){
> for (int currentPlace=0; currentPlace < length; currentPlace++) {
> int smallestAt=currentPlace;
> currentPlace++;
> int temp=a[currentPlace];
> a[currentPlace]=a[smallestAt];
> a[smallestAt]=temp;
> }
for (int currentPlace=0; currentPlace < length - 1; currentPlace++) { for (int currentPlace=0; currentPlace < length - 1; currentPlace++) {
int smallest=Integer.MAX_VALUE; int smallest=Integer.MAX_VALUE;
int smallestAt=currentPlace + 1; | int smallestAt=1;
for (int check=currentPlace; check < length; check++) { for (int check=currentPlace; check < length; check++) {
if (a[check] < smallest) { if (a[check] < smallest) {
smallestAt=check; smallestAt=check;
smallest=a[check]; smallest=a[check];
} }
} }
int temp=a[currentPlace]; int temp=a[currentPlace];
a[currentPlace]=a[smallestAt]; | a[currentPlace]=smallest;
a[smallestAt]=temp; a[smallestAt]=temp;
} }
return a; return a;
} }
} }
4.4 Sort1SelectionProblem75153
Improvements:
length - 1replaced withlength- And cloning
Improvement Details:
Sort1SelectionProblem75153 100 mult 0.0 + 0.98881865 = 0.98881865 ASTNodes: 140 GPNodes: 135 xoverApplied: true xovers: 1 mutationApplied: true mutations: 1
Diff
3,5c3,18 < for (int currentPlace=0; currentPlace < length - 1; currentPlace++) { < int smallest=Integer.MAX_VALUE; < int smallestAt=currentPlace + 1; --- > for (int currentPlace=0; currentPlace < length; currentPlace++) { > int smallest=0; > int smallestAt=currentPlace; > for (int check=currentPlace; check < currentPlace++; smallestAt--) { > if (a[check] < smallest) { > a[currentPlace]=smallest; > smallest=currentPlace; > } > } > int temp=a[currentPlace]; > a[currentPlace]=a[smallestAt]; > a[smallestAt]=temp; > } > for (int currentPlace=0; currentPlace < length; currentPlace++) { > int smallest=a[currentPlace]; > int smallestAt=currentPlace;
Diff side-by-side
public class Sort1SelectionProblem { public class Sort1SelectionProblem {
public static Integer[] sort( Integer[] a, Integer length){ public static Integer[] sort( Integer[] a, Integer length){
for (int currentPlace=0; currentPlace < length - 1; currentPlace++) { | for (int currentPlace=0; currentPlace < length; currentPlace++) {
int smallest=Integer.MAX_VALUE; | int smallest=0;
int smallestAt=currentPlace + 1; | int smallestAt=currentPlace;
> for (int check=currentPlace; check < currentPlace++; smallestAt--) {
> if (a[check] < smallest) {
> a[currentPlace]=smallest;
> smallest=currentPlace;
> }
> }
> int temp=a[currentPlace];
> a[currentPlace]=a[smallestAt];
> a[smallestAt]=temp;
> }
> for (int currentPlace=0; currentPlace < length; currentPlace++) {
> int smallest=a[currentPlace];
> int smallestAt=currentPlace;
for (int check=currentPlace; check < length; check++) { for (int check=currentPlace; check < length; check++) {
if (a[check] < smallest) { if (a[check] < smallest) {
smallestAt=check; smallestAt=check;
smallest=a[check]; smallest=a[check];
} }
} }
int temp=a[currentPlace]; int temp=a[currentPlace];
a[currentPlace]=a[smallestAt]; a[currentPlace]=a[smallestAt];
a[smallestAt]=temp; a[smallestAt]=temp;
} }
return a; return a;
} }
} }
4.5 Sort1SelectionProblem70.java
Improvement Details:
Sort1SelectionProblem70 100 mult 0.0 + 0.99959093 = 0.99959093 ASTNodes: 71 GPNodes: 74 xoverApplied: false xovers: 0 mutationApplied: true mutations: 2
Diff
5c5 < int smallestAt=currentPlace + 1; --- > int smallestAt=currentPlace;
Diff side-by-side
public class Sort1SelectionProblem { public class Sort1SelectionProblem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int currentPlace=0; currentPlace < length - 1; curre for (int currentPlace=0; currentPlace < length - 1; curre
int smallest=Integer.MAX_VALUE; int smallest=Integer.MAX_VALUE;
int smallestAt=currentPlace + 1; | int smallestAt=currentPlace;
for (int check=currentPlace; check < length; check++) { for (int check=currentPlace; check < length; check++) {
if (a[check] < smallest) { if (a[check] < smallest) {
smallestAt=check; smallestAt=check;
smallest=a[check]; smallest=a[check];
} }
} }
int temp=a[currentPlace]; int temp=a[currentPlace];
a[currentPlace]=a[smallestAt]; a[currentPlace]=a[smallestAt];
a[smallestAt]=temp; a[smallestAt]=temp;
} }
return a; return a;
} }
} }
4.6 Sort1SelectionProblem28423.java
Improvement Details:
Sort1SelectionProblem28423 100 mult 0.0 + 0.99877506 = 0.99877506 ASTNodes: 191 GPNodes: 186 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
4,5c4,5 < int smallest=Integer.MAX_VALUE; < int smallestAt=currentPlace + 1; --- > int smallest=a[currentPlace]; > int smallestAt=currentPlace; 7,9c7,15 < if (a[check] < smallest) { < smallestAt=check; < smallest=a[check]; --- > { > { > { > if (a[check] < smallest) { > smallestAt=check; > smallest=a[check]; > } > } > } 14a21,62 > } > for (int currentPlace=0; currentPlace < currentPlace; currentPlace++) { > int smallest=1; > int smallestAt=currentPlace - 1; > for (int check=currentPlace; currentPlace < check++; smallestAt--) { > { > smallestAt=check; > smallest=currentPlace=a[check]; > } > } > int temp=currentPlace; > for (int check=currentPlace; check < length; check++) { > { > smallestAt=check; > smallest=a[check]; > } > smallest-=a[check]; > { > { > { > { > { > { > { > { > { > smallest=a[check]; > } > } > } > } > if (a[check] < smallest) { > length=check; > smallest=a[check]; > } > } > } > } > } > } > } > currentPlace=temp;
Diff side-by-side
public class Sort1SelectionProblem { public class Sort1SelectionProblem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int currentPlace=0; currentPlace < length - 1; curre for (int currentPlace=0; currentPlace < length - 1; curre
int smallest=Integer.MAX_VALUE; | int smallest=a[currentPlace];
int smallestAt=currentPlace + 1; | int smallestAt=currentPlace;
for (int check=currentPlace; check < length; check++) { for (int check=currentPlace; check < length; check++) {
> {
> {
> {
if (a[check] < smallest) { if (a[check] < smallest) {
smallestAt=check; smallestAt=check;
smallest=a[check]; smallest=a[check];
} }
} }
> }
> }
> }
int temp=a[currentPlace]; int temp=a[currentPlace];
a[currentPlace]=a[smallestAt]; a[currentPlace]=a[smallestAt];
a[smallestAt]=temp; a[smallestAt]=temp;
> }
> for (int currentPlace=0; currentPlace < currentPlace; cur
> int smallest=1;
> int smallestAt=currentPlace - 1;
> for (int check=currentPlace; currentPlace < check++; sm
> {
> smallestAt=check;
> smallest=currentPlace=a[check];
> }
> }
> int temp=currentPlace;
> for (int check=currentPlace; check < length; check++) {
> {
> smallestAt=check;
> smallest=a[check];
> }
> smallest-=a[check];
> {
> {
> {
> {
> {
> {
> {
> {
> {
> smallest=a[check];
> }
> }
> }
> }
> if (a[check] < smallest) {
> length=check;
> smallest=a[check];
> }
> }
> }
> }
> }
> }
> }
> currentPlace=temp;
} }
return a; return a;
} }
} }
5 Sort1HeapProblem
Improvements
- not understood
- results from crossover & mutation
Original - /home/bck/GP/Exhaustive/Seed-Sort1HeapProblem.java
public class Sort1HeapProblem { public static Integer[] sort( Integer[] a, Integer array_size){ int i; for (i=(array_size / 2 - 1); i >= 0; --i) { int maxchild, temp, child, root=i, bottom=array_size - 1; while (root * 2 < bottom) { child=root * 2 + 1; if (child == bottom) { maxchild=child; } else { if (a[child] > a[child + 1]) { maxchild=child; } else { maxchild=child + 1; } } if (a[root] < a[maxchild]) { temp=a[root]; a[root]=a[maxchild]; a[maxchild]=temp; } else { break; } root=maxchild; } } for (i=array_size - 1; i >= 0; --i) { int temp; temp=a[i]; a[i]=a[0]; a[0]=temp; int maxchild, child, root=0, bottom=i - 1; while (root * 2 < bottom) { child=root * 2 + 1; if (child == bottom) { maxchild=child; } else { if (a[child] > a[child + 1]) { maxchild=child; } else { maxchild=child + 1; } } if (a[root] < a[maxchild]) { temp=a[root]; a[root]=a[maxchild]; a[maxchild]=temp; } else { break; } root=maxchild; } } return a; } }
5.1 Sort1HeapProblem27409.java
Improvement Details:
Sort1HeapProblem27409 100 mult 0.0 + 0.9279286 = 0.9279286 ASTNodes: 293 GPNodes: 298 xoverApplied: false xovers: 0 mutationApplied: true mutations: 2
Diff
9c9,28 < maxchild=child; --- > { > { > { > { > if (child == array_size - a[root] + 1) { > if (a[child] > a[child-=child - child - 1]) child=child + a[0] + 1 * 2 + 1; > else { > array_size=child + 1; > } > } > else { > { > maxchild=child; > } > } > break; > } > } > } > } 50d68 < temp=a[root];
Diff side-by-side
public class Sort1HeapProblem { public class Sort1HeapProblem {
public static Integer[] sort( Integer[] a, Integer array_ public static Integer[] sort( Integer[] a, Integer array_
int i; int i;
for (i=(array_size / 2 - 1); i >= 0; --i) { for (i=(array_size / 2 - 1); i >= 0; --i) {
int maxchild, temp, child, root=i, bottom=array_size - int maxchild, temp, child, root=i, bottom=array_size -
while (root * 2 < bottom) { while (root * 2 < bottom) {
child=root * 2 + 1; child=root * 2 + 1;
if (child == bottom) { if (child == bottom) {
> {
> {
> {
> {
> if (child == array_size - a[root] + 1) {
> if (a[child] > a[child-=child - child - 1
> else {
> array_size=child + 1;
> }
> }
> else {
> {
maxchild=child; maxchild=child;
} }
> }
> break;
> }
> }
> }
> }
> }
else { else {
if (a[child] > a[child + 1]) { if (a[child] > a[child + 1]) {
maxchild=child; maxchild=child;
} }
else { else {
maxchild=child + 1; maxchild=child + 1;
} }
} }
if (a[root] < a[maxchild]) { if (a[root] < a[maxchild]) {
temp=a[root]; temp=a[root];
a[root]=a[maxchild]; a[root]=a[maxchild];
a[maxchild]=temp; a[maxchild]=temp;
} }
else { else {
break; break;
} }
root=maxchild; root=maxchild;
} }
} }
for (i=array_size - 1; i >= 0; --i) { for (i=array_size - 1; i >= 0; --i) {
int temp; int temp;
temp=a[i]; temp=a[i];
a[i]=a[0]; a[i]=a[0];
a[0]=temp; a[0]=temp;
int maxchild, child, root=0, bottom=i - 1; int maxchild, child, root=0, bottom=i - 1;
while (root * 2 < bottom) { while (root * 2 < bottom) {
child=root * 2 + 1; child=root * 2 + 1;
if (child == bottom) { if (child == bottom) {
maxchild=child; maxchild=child;
} }
else { else {
if (a[child] > a[child + 1]) { if (a[child] > a[child + 1]) {
maxchild=child; maxchild=child;
} }
else { else {
maxchild=child + 1; maxchild=child + 1;
} }
} }
if (a[root] < a[maxchild]) { if (a[root] < a[maxchild]) {
temp=a[root]; <
a[root]=a[maxchild]; a[root]=a[maxchild];
a[maxchild]=temp; a[maxchild]=temp;
} }
else { else {
break; break;
} }
root=maxchild; root=maxchild;
} }
} }
return a; return a;
} }
} }
5.2 Sort1HeapProblem8945.java
Improvement Details:
Sort1HeapProblem8945 100 mult 0.0 + 0.9450205 = 0.9450205 ASTNodes: 241 GPNodes: 244 xoverApplied: false xovers: 0 mutationApplied: true mutations: 3
Diff
4c4 < for (i=(array_size / 2 - 1); i >= 0; --i) { --- > for (i=(array_size + 2 - 1); i >= 0; --i) { 12,14c12,15 < if (a[child] > a[child + 1]) { < maxchild=child; < } --- > { > if (a[child] > a[child + 1]) { > maxchild=child; > } 16c17,18 < maxchild=child + 1; --- > maxchild=child + 1; > } 50d51 < temp=a[root];
Diff side-by-side
public class Sort1HeapProblem { public class Sort1HeapProblem {
public static Integer[] sort( Integer[] a, Integer array_ public static Integer[] sort( Integer[] a, Integer array_
int i; int i;
for (i=(array_size / 2 - 1); i >= 0; --i) { | for (i=(array_size + 2 - 1); i >= 0; --i) {
int maxchild, temp, child, root=i, bottom=array_size - int maxchild, temp, child, root=i, bottom=array_size -
while (root * 2 < bottom) { while (root * 2 < bottom) {
child=root * 2 + 1; child=root * 2 + 1;
if (child == bottom) { if (child == bottom) {
maxchild=child; maxchild=child;
} }
else { else {
> {
if (a[child] > a[child + 1]) { if (a[child] > a[child + 1]) {
maxchild=child; maxchild=child;
} }
else { else {
maxchild=child + 1; maxchild=child + 1;
} }
} }
> }
if (a[root] < a[maxchild]) { if (a[root] < a[maxchild]) {
temp=a[root]; temp=a[root];
a[root]=a[maxchild]; a[root]=a[maxchild];
a[maxchild]=temp; a[maxchild]=temp;
} }
else { else {
break; break;
} }
root=maxchild; root=maxchild;
} }
} }
for (i=array_size - 1; i >= 0; --i) { for (i=array_size - 1; i >= 0; --i) {
int temp; int temp;
temp=a[i]; temp=a[i];
a[i]=a[0]; a[i]=a[0];
a[0]=temp; a[0]=temp;
int maxchild, child, root=0, bottom=i - 1; int maxchild, child, root=0, bottom=i - 1;
while (root * 2 < bottom) { while (root * 2 < bottom) {
child=root * 2 + 1; child=root * 2 + 1;
if (child == bottom) { if (child == bottom) {
maxchild=child; maxchild=child;
} }
else { else {
if (a[child] > a[child + 1]) { if (a[child] > a[child + 1]) {
maxchild=child; maxchild=child;
} }
else { else {
maxchild=child + 1; maxchild=child + 1;
} }
} }
if (a[root] < a[maxchild]) { if (a[root] < a[maxchild]) {
temp=a[root]; <
a[root]=a[maxchild]; a[root]=a[maxchild];
a[maxchild]=temp; a[maxchild]=temp;
} }
else { else {
break; break;
} }
root=maxchild; root=maxchild;
} }
} }
return a; return a;
} }
} }
6 Sort1Merge
Improvements
- mutation (deletion)
- crossover
Original - /home/bck/GP/Exhaustive/Seed-Sort1Merge.java
public class Sort1Merge { public static Integer[] sort( Integer[] a, Integer length){ mergesort_r(0,length,a); return a; } public static Integer[] merge( Integer[] a, int left_start, int left_end, int right_start, int right_end){ int left_length=left_end - left_start; int right_length=right_end - right_start; int[] left_half=new int[left_length]; int[] right_half=new int[right_length]; int r=0; int l=0; int i=0; for (i=left_start; i < left_end; i++, l++) { left_half[l]=a[i]; } for (i=right_start; i < right_end; i++, r++) { right_half[r]=a[i]; } for (i=left_start, r=0, l=0; l < left_length && r < right_length; i++) { if (left_half[l] < right_half[r]) { a[i]=left_half[l++]; } else { a[i]=right_half[r++]; } } for (; l < left_length; i++, l++) { a[i]=left_half[l]; } for (; r < right_length; i++, r++) { a[i]=right_half[r]; } return a; } public static Integer[] mergesort_r( int left, int right, Integer[] a){ if (right - left <= 1) { return a; } else { } int left_start=left; int left_end=(left + right) / 2; int right_start=left_end; int right_end=right; mergesort_r(left_start,left_end,a); mergesort_r(right_start,right_end,a); merge(a,left_start,left_end,right_start,right_end); return a; } }
6.1 Sort1Merge17935.java
Improvement Details:
Sort1Merge17935 100 mult 0.0 + 0.96814555 = 0.96814555 ASTNodes: 199 GPNodes: 195 xoverApplied: false xovers: 0 mutationApplied: true mutations: 2
Diff
31,33d30 < for (; r < right_length; i++, r++) { < a[i]=right_half[r]; < }
Diff side-by-side
public class Sort1Merge { public class Sort1Merge {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
mergesort_r(0,length,a); mergesort_r(0,length,a);
return a; return a;
} }
public static Integer[] merge( Integer[] a, int left_star public static Integer[] merge( Integer[] a, int left_star
int left_length=left_end - left_start; int left_length=left_end - left_start;
int right_length=right_end - right_start; int right_length=right_end - right_start;
int[] left_half=new int[left_length]; int[] left_half=new int[left_length];
int[] right_half=new int[right_length]; int[] right_half=new int[right_length];
int r=0; int r=0;
int l=0; int l=0;
int i=0; int i=0;
for (i=left_start; i < left_end; i++, l++) { for (i=left_start; i < left_end; i++, l++) {
left_half[l]=a[i]; left_half[l]=a[i];
} }
for (i=right_start; i < right_end; i++, r++) { for (i=right_start; i < right_end; i++, r++) {
right_half[r]=a[i]; right_half[r]=a[i];
} }
for (i=left_start, r=0, l=0; l < left_length && r < right for (i=left_start, r=0, l=0; l < left_length && r < right
if (left_half[l] < right_half[r]) { if (left_half[l] < right_half[r]) {
a[i]=left_half[l++]; a[i]=left_half[l++];
} }
else { else {
a[i]=right_half[r++]; a[i]=right_half[r++];
} }
} }
for (; l < left_length; i++, l++) { for (; l < left_length; i++, l++) {
a[i]=left_half[l]; a[i]=left_half[l];
} }
for (; r < right_length; i++, r++) { <
a[i]=right_half[r]; <
} <
return a; return a;
} }
public static Integer[] mergesort_r( int left, int right, public static Integer[] mergesort_r( int left, int right,
if (right - left <= 1) { if (right - left <= 1) {
return a; return a;
} }
else { else {
} }
int left_start=left; int left_start=left;
int left_end=(left + right) / 2; int left_end=(left + right) / 2;
int right_start=left_end; int right_start=left_end;
int right_end=right; int right_end=right;
mergesort_r(left_start,left_end,a); mergesort_r(left_start,left_end,a);
mergesort_r(right_start,right_end,a); mergesort_r(right_start,right_end,a);
merge(a,left_start,left_end,right_start,right_end); merge(a,left_start,left_end,right_start,right_end);
return a; return a;
} }
} }
6.2 Sort1Merge241.java
Improvement Details:
Sort1Merge241 100 mult 0.0 + 0.96814555 = 0.96814555 ASTNodes: 200 GPNodes: 196 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
31,32c31 < for (; r < right_length; i++, r++) { < a[i]=right_half[r]; --- > {
Diff side-by-side
public class Sort1Merge { public class Sort1Merge {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
mergesort_r(0,length,a); mergesort_r(0,length,a);
return a; return a;
} }
public static Integer[] merge( Integer[] a, int left_star public static Integer[] merge( Integer[] a, int left_star
int left_length=left_end - left_start; int left_length=left_end - left_start;
int right_length=right_end - right_start; int right_length=right_end - right_start;
int[] left_half=new int[left_length]; int[] left_half=new int[left_length];
int[] right_half=new int[right_length]; int[] right_half=new int[right_length];
int r=0; int r=0;
int l=0; int l=0;
int i=0; int i=0;
for (i=left_start; i < left_end; i++, l++) { for (i=left_start; i < left_end; i++, l++) {
left_half[l]=a[i]; left_half[l]=a[i];
} }
for (i=right_start; i < right_end; i++, r++) { for (i=right_start; i < right_end; i++, r++) {
right_half[r]=a[i]; right_half[r]=a[i];
} }
for (i=left_start, r=0, l=0; l < left_length && r < right for (i=left_start, r=0, l=0; l < left_length && r < right
if (left_half[l] < right_half[r]) { if (left_half[l] < right_half[r]) {
a[i]=left_half[l++]; a[i]=left_half[l++];
} }
else { else {
a[i]=right_half[r++]; a[i]=right_half[r++];
} }
} }
for (; l < left_length; i++, l++) { for (; l < left_length; i++, l++) {
a[i]=left_half[l]; a[i]=left_half[l];
} }
for (; r < right_length; i++, r++) { | {
a[i]=right_half[r]; <
} }
return a; return a;
} }
public static Integer[] mergesort_r( int left, int right, public static Integer[] mergesort_r( int left, int right,
if (right - left <= 1) { if (right - left <= 1) {
return a; return a;
} }
else { else {
} }
int left_start=left; int left_start=left;
int left_end=(left + right) / 2; int left_end=(left + right) / 2;
int right_start=left_end; int right_start=left_end;
int right_end=right; int right_end=right;
mergesort_r(left_start,left_end,a); mergesort_r(left_start,left_end,a);
mergesort_r(right_start,right_end,a); mergesort_r(right_start,right_end,a);
merge(a,left_start,left_end,right_start,right_end); merge(a,left_start,left_end,right_start,right_end);
return a; return a;
} }
} }
6.3 Sort1Merge5281.java
Improvement Details:
Sort1Merge5281 100 mult 0.0 + 0.9729257 = 0.9729257 ASTNodes: 203 GPNodes: 199 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
31,33c31 < for (; r < right_length; i++, r++) { < a[i]=right_half[r]; < } --- > i=left_start;
Diff side-by-side
public class Sort1Merge { public class Sort1Merge {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
mergesort_r(0,length,a); mergesort_r(0,length,a);
return a; return a;
} }
public static Integer[] merge( Integer[] a, int left_star public static Integer[] merge( Integer[] a, int left_star
int left_length=left_end - left_start; int left_length=left_end - left_start;
int right_length=right_end - right_start; int right_length=right_end - right_start;
int[] left_half=new int[left_length]; int[] left_half=new int[left_length];
int[] right_half=new int[right_length]; int[] right_half=new int[right_length];
int r=0; int r=0;
int l=0; int l=0;
int i=0; int i=0;
for (i=left_start; i < left_end; i++, l++) { for (i=left_start; i < left_end; i++, l++) {
left_half[l]=a[i]; left_half[l]=a[i];
} }
for (i=right_start; i < right_end; i++, r++) { for (i=right_start; i < right_end; i++, r++) {
right_half[r]=a[i]; right_half[r]=a[i];
} }
for (i=left_start, r=0, l=0; l < left_length && r < right for (i=left_start, r=0, l=0; l < left_length && r < right
if (left_half[l] < right_half[r]) { if (left_half[l] < right_half[r]) {
a[i]=left_half[l++]; a[i]=left_half[l++];
} }
else { else {
a[i]=right_half[r++]; a[i]=right_half[r++];
} }
} }
for (; l < left_length; i++, l++) { for (; l < left_length; i++, l++) {
a[i]=left_half[l]; a[i]=left_half[l];
} }
for (; r < right_length; i++, r++) { | i=left_start;
a[i]=right_half[r]; <
} <
return a; return a;
} }
public static Integer[] mergesort_r( int left, int right, public static Integer[] mergesort_r( int left, int right,
if (right - left <= 1) { if (right - left <= 1) {
return a; return a;
} }
else { else {
} }
int left_start=left; int left_start=left;
int left_end=(left + right) / 2; int left_end=(left + right) / 2;
int right_start=left_end; int right_start=left_end;
int right_end=right; int right_end=right;
mergesort_r(left_start,left_end,a); mergesort_r(left_start,left_end,a);
mergesort_r(right_start,right_end,a); mergesort_r(right_start,right_end,a);
merge(a,left_start,left_end,right_start,right_end); merge(a,left_start,left_end,right_start,right_end);
return a; return a;
} }
} }
7 Sort1Quick
Improvements
- mutation & crossover
Original - /home/bck/GP/Exhaustive/Seed-Sort1Quick.java
public class Sort1Quick { public static Integer[] sort( Integer[] a, Integer length){ return sort(a,0,length - 1); } public static Integer[] sort( Integer[] a, Integer p, Integer r){ if (p < r) { int q=0; int x=a[p]; int i=p - 1; int j=r + 1; while (true) { i++; while (i < r && a[i] < x) i++; j--; while (j > p && a[j] > x) j--; if (i < j) { int temp=a[i]; a[i]=a[j]; a[j]=temp; } else { q=j; break; } } sort(a,p,q); sort(a,q + 1,r); } return a; } }
7.1 Sort1Quick10147
Improvements:
i < rreplaced, as well asinode
Improvement Details:
Sort1Quick10147 100 mult 0.0 + 0.6860878 = 0.6860878 ASTNodes: 121 GPNodes: 130 xoverApplied: false xovers: 0 mutationApplied: true mutations: 3
Diff
13c13 < while (i < r && a[i] < x) i++; --- > while (j < r && j++ < x && a[i] < x) i++;
Diff side-by-side
public class Sort1Quick { public class Sort1Quick {
public static Integer[] sort( Integer[] a, Integer length){ public static Integer[] sort( Integer[] a, Integer length){
return sort(a,0,length - 1); return sort(a,0,length - 1);
} }
public static Integer[] sort( Integer[] a, Integer p, Integer r){ public static Integer[] sort( Integer[] a, Integer p, Integer r){
if (p < r) { if (p < r) {
int q=0; int q=0;
int x=a[p]; int x=a[p];
int i=p - 1; int i=p - 1;
int j=r + 1; int j=r + 1;
while (true) { while (true) {
i++; i++;
while (i < r && a[i] < x) i++; | while (j < r && j++ < x && a[i] < x) i++;
j--; j--;
while (j > p && a[j] > x) j--; while (j > p && a[j] > x) j--;
if (i < j) { if (i < j) {
int temp=a[i]; int temp=a[i];
a[i]=a[j]; a[i]=a[j];
a[j]=temp; a[j]=temp;
} }
else { else {
q=j; q=j;
break; break;
} }
} }
sort(a,p,q); sort(a,p,q);
sort(a,q + 1,r); sort(a,q + 1,r);
} }
return a; return a;
} }
} }
7.2 Sort1Quick30424
Improvements:
i,r,j,pcan be modified, as well as operator changes- to make
i < rorj > palways true
Improvement Details:
Sort1Quick30424 100 mult 0.0 + 0.78500444 = 0.78500444 ASTNodes: 185 GPNodes: 193 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
13c13 < while (i < r && a[i] < x) i++; --- > while (j > 0 && a[i] < x) i++; 15c15 < while (j > p && a[j] > x) j--; --- > while (1 > 0 && a[j] > x) j--; 22c22,42 < q=j; --- > if (i < j) { > while (j > 0 && j++ > x) j++; > if (j-- < a[i]) a[j-- + j]=a[j]++; > else { > i-=j; > break; > } > q=x; > } > else { > q=j; > break; > } > if (i < j) { > int temp=p; > q=x; > } > else { > a[j]=j; > break; > }
Diff side-by-side
public class Sort1Quick { public class Sort1Quick {
public static Integer[] sort( Integer[] a, Integer length){ public static Integer[] sort( Integer[] a, Integer length){
return sort(a,0,length - 1); return sort(a,0,length - 1);
} }
public static Integer[] sort( Integer[] a, Integer p, Integer r){ public static Integer[] sort( Integer[] a, Integer p, Integer r){
if (p < r) { if (p < r) {
int q=0; int q=0;
int x=a[p]; int x=a[p];
int i=p - 1; int i=p - 1;
int j=r + 1; int j=r + 1;
while (true) { while (true) {
i++; i++;
while (i < r && a[i] < x) i++; | while (j > 0 && a[i] < x) i++;
j--; j--;
while (j > p && a[j] > x) j--; | while (1 > 0 && a[j] > x) j--;
if (i < j) { if (i < j) {
int temp=a[i]; int temp=a[i];
a[i]=a[j]; a[i]=a[j];
a[j]=temp; a[j]=temp;
} }
else { else {
> if (i < j) {
> while (j > 0 && j++ > x) j++;
> if (j-- < a[i]) a[j-- + j]=a[j]++;
> else {
> i-=j;
> break;
> }
> q=x;
> }
> else {
q=j; q=j;
> break;
> }
> if (i < j) {
> int temp=p;
> q=x;
> }
> else {
> a[j]=j;
> break;
> }
break; break;
} }
} }
sort(a,p,q); sort(a,p,q);
sort(a,q + 1,r); sort(a,q + 1,r);
} }
return a; return a;
} }
} }
7.3 Sort1Quick22387.java
Improvement Details:
Sort1Quick22387 100 mult 0.0 + 0.814648 = 0.814648 ASTNodes: 895 GPNodes: 919 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
13c13 < while (i < r && a[i] < x) i++; --- > while (i < j && a[i] < x) i++; 15c15 < while (j > p && a[j] > x) j--; --- > while (a[j] > x) j--; 22c22,223 < q=j; --- > if (i < j) { > while (true) { > { > while (true) { > i++; > while (i < r && a[i] < x) i++; > while (true) { > i++; > while (x < r && a[i] < x) i++; > a[i]--; > while (j > 0 && j > 0) j--; > if (i < j) { > int temp=a[x]; > a[i]+=a[a[i]]; > a[j]=temp; > } > else { > break; > } > } > a[i]--; > while (j > 0 && 0 > 0) j++; > if (i < j) { > int temp=r++; > a[i]+=a[a[i]]; > a[j]=temp; > } > else { > break; > } > } > i++; > while (true) { > i++; > while (i < r && a[i] < x) i++; > x++; > while (a[j] > x) j--; > if (i < j) { > int temp=a[i]; > a[i]=a[j]; > a[j]=temp; > } > else { > if (i < j) { > while (true) { > i++; > while (i < r && a[i] < x) i++; > a[i]--; > while (j > 0 && j > 0) j++; > if (i < j) { > int temp=a[x]; > i++; > a[x]=a[a[i]]; > a[j]=temp; > } > else { > break; > } > } > while (true) { > i--; > x++; > if (j++ < j) a[i]=q; > else { > break; > } > } > if (i < a[i]) { > int temp=a[x]; > j--; > } > else { > break; > } > a[j]=j; > } > else { > q=a[x]=a[j]; > break; > } > break; > } > } > a[i]=i; > a[j]-=j; > } > if (i < j) { > while (true) { > i++; > while (i < r && a[i] < x) i++; > while (true) { > i++; > while (x < r && a[i] < x) i++; > a[i]--; > while (j > 0 && j > 0) j--; > if (i < j) { > int temp=a[x]; > a[i]+=a[a[i]]; > a[j]=temp; > } > else { > break; > } > } > a[i]--; > while (j > 0 && 0 > 0) j++; > if (i < j) { > int temp=r++; > a[i]+=a[a[i]]; > a[j]=temp; > } > else { > break; > } > } > i++; > while (true) { > i++; > while (i < r && a[i] < x) i++; > x++; > while (a[j] > x) j--; > if (i < j) { > int temp=a[i]; > a[i]=a[j]; > a[j]=temp; > } > else { > if (i < j) { > while (true) { > i++; > while (i < r && a[i] < x) i++; > a[i]--; > while (j > 0 && j > 0) j++; > if (i < j) { > int temp=a[x]; > i++; > a[x]=a[a[i]]; > a[j]=temp; > } > else { > break; > } > } > while (true) { > i--; > x++; > if (j-- < j) a[i]=q; > else { > break; > } > } > if (i < a[i]) { > int temp=a[x]; > j--; > } > else { > break; > } > a[j]=j; > } > else { > q=a[x]=a[j]; > break; > } > break; > } > } > a[i]=i; > a[j]-=j; > } > else { > q=i; > break; > } > while (i < r && a[i] < x) r++; > a[i]--; > while (j > 0 && j > p - 1) j++; > if (i < j) { > int temp=j; > a[i]-=a[j]; > while (i < r && r < x) r++; > } > else { > break; > } > } > while (true) { > i++; > i--; > x++; > if (a[i] > a[j]) a[j]=i; > else { > break; > } > } > a[i]=i; > a[j]-=j; > } > else { > q=j; > break; > }
Diff side-by-side
public class Sort1Quick { public class Sort1Quick {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
return sort(a,0,length - 1); return sort(a,0,length - 1);
} }
public static Integer[] sort( Integer[] a, Integer p, In public static Integer[] sort( Integer[] a, Integer p, In
if (p < r) { if (p < r) {
int q=0; int q=0;
int x=a[p]; int x=a[p];
int i=p - 1; int i=p - 1;
int j=r + 1; int j=r + 1;
while (true) { while (true) {
i++; i++;
> while (i < j && a[i] < x) i++;
> j--;
> while (a[j] > x) j--;
> if (i < j) {
> int temp=a[i];
> a[i]=a[j];
> a[j]=temp;
> }
> else {
> if (i < j) {
> while (true) {
> {
> while (true) {
> i++;
> while (i < r && a[i] < x)
> while (true) {
> i++;
> while (x < r && a[i] < x)
> a[i]--;
> while (j > 0 && j > 0)
> if (i < j) {
> int temp=a[x];
> a[i]+=a[a[i]];
> a[j]=temp;
> }
> else {
> break;
> }
> }
> a[i]--;
> while (j > 0 && 0 > 0) j+
> if (i < j) {
> int temp=r++;
> a[i]+=a[a[i]];
> a[j]=temp;
> }
> else {
> break;
> }
> }
> i++;
> while (true) {
> i++;
> while (i < r && a[i] < x)
> x++;
> while (a[j] > x) j--;
> if (i < j) {
> int temp=a[i];
> a[i]=a[j];
> a[j]=temp;
> }
> else {
> if (i < j) {
> while (true) {
> i++;
while (i < r && a[i] < x) i++; while (i < r && a[i] < x)
> a[i]--;
> while (j > 0 && j > 0)
> if (i < j) {
> int temp=a[x];
> i++;
> a[x]=a[a[i]];
> a[j]=temp;
> }
> else {
> break;
> }
> }
> while (true) {
> i--;
> x++;
> if (j++ < j)
> else {
> break;
> }
> }
> if (i < a[i]) {
> int temp=a[x];
j--; j--;
while (j > p && a[j] > x) j--; | }
> else {
> break;
> }
> a[j]=j;
> }
> else {
> q=a[x]=a[j];
> break;
> }
> break;
> }
> }
> a[i]=i;
> a[j]-=j;
> }
> if (i < j) {
> while (true) {
> i++;
> while (i < r && a[i] < x)
> while (true) {
> i++;
> while (x < r && a[i] < x)
> a[i]--;
> while (j > 0 && j > 0)
> if (i < j) {
> int temp=a[x];
> a[i]+=a[a[i]];
> a[j]=temp;
> }
> else {
> break;
> }
> }
> a[i]--;
> while (j > 0 && 0 > 0) j+
> if (i < j) {
> int temp=r++;
> a[i]+=a[a[i]];
> a[j]=temp;
> }
> else {
> break;
> }
> }
> i++;
> while (true) {
> i++;
> while (i < r && a[i] < x)
> x++;
> while (a[j] > x) j--;
if (i < j) { if (i < j) {
int temp=a[i]; int temp=a[i];
a[i]=a[j]; a[i]=a[j];
a[j]=temp; a[j]=temp;
} }
else { else {
> if (i < j) {
> while (true) {
> i++;
> while (i < r && a[i] < x)
> a[i]--;
> while (j > 0 && j > 0)
> if (i < j) {
> int temp=a[x];
> i++;
> a[x]=a[a[i]];
> a[j]=temp;
> }
> else {
> break;
> }
> }
> while (true) {
> i--;
> x++;
> if (j-- < j)
> else {
> break;
> }
> }
> if (i < a[i]) {
> int temp=a[x];
> j--;
> }
> else {
> break;
> }
> a[j]=j;
> }
> else {
> q=a[x]=a[j];
> break;
> }
> break;
> }
> }
> a[i]=i;
> a[j]-=j;
> }
> else {
> q=i;
> break;
> }
> while (i < r && a[i] < x) r++;
> a[i]--;
> while (j > 0 && j > p - 1) j++;
> if (i < j) {
> int temp=j;
> a[i]-=a[j];
> while (i < r && r < x) r++;
> }
> else {
> break;
> }
> }
> while (true) {
> i++;
> i--;
> x++;
> if (a[i] > a[j]) a[j]=i;
> else {
> break;
> }
> }
> a[i]=i;
> a[j]-=j;
> }
> else {
q=j; q=j;
> break;
> }
break; break;
} }
} }
sort(a,p,q); sort(a,p,q);
sort(a,q + 1,r); sort(a,q + 1,r);
} }
return a; return a;
} }
} }
7.4 Sort1Quick22387.variant.java
Improvement Details:
Diff
13c13 < while (i < r && a[i] < x) i++; --- > while (i < j && a[i] < x) i++; 15c15 < while (j > p && a[j] > x) j--; --- > while (a[j] > x) j--; 22c22,223 < q=j; --- > if (i < j) { > while (true) { > { > while (true) { > i++; > while (i < r && a[i] < x) i++; > while (true) { > i++; > while (x < r && a[i] < x) i++; > a[i]--; > while (j > 0 && j > 0) j--; > if (i < j) { > int temp=a[x]; > a[i]+=a[a[i]]; > a[j]=temp; > } > else { > break; > } > } > a[i]--; > while (j > 0 && 0 > 0) j++; > if (i < j) { > int temp=r++; > a[i]+=a[a[i]]; > a[j]=temp; > } > else { > break; > } > } > i++; > while (true) { > i++; > while (i < r && a[i] < x) i++; > x++; > while (a[j] > x) j--; > if (i < j) { > int temp=a[i]; > a[i]=a[j]; > a[j]=temp; > } > else { > if (i < j) { > while (true) { > i++; > while (i < r && a[i] < x) i++; > a[i]--; > while (j > 0 && j > 0) j++; > if (i < j) { > int temp=a[x]; > i++; > a[x]=a[a[i]]; > a[j]=temp; > } > else { > break; > } > } > while (true) { > i--; > x++; > if (j++ < j) a[i]=q; > else { > break; > } > } > if (i < a[i]) { > int temp=a[x]; > j--; > } > else { > break; > } > a[j]=j; > } > else { > q=a[x]=a[j]; > break; > } > break; > } > } > a[i]=i; > a[j]-=j; > } > if (i < j) { > while (true) { > i++; > while (i < r && a[i] < x) i++; > while (true) { > i++; > while (x < r && a[i] < x) i++; > a[i]--; > while (j > 0 && j > 0) j--; > if (i < j) { > int temp=a[x]; > a[i]+=a[a[i]]; > a[j]=temp; > } > else { > break; > } > } > a[i]--; > while (j > 0 && 0 > 0) j++; > if (i < j) { > int temp=r++; > a[i]+=a[a[i]]; > a[j]=temp; > } > else { > break; > } > } > i++; > while (true) { > i++; > while (i < r && a[i] < x) i++; > x++; > while (a[j] > x) j--; > if (i < j) { > int temp=a[i]; > a[i]=a[j]; > a[j]=temp; > } > else { > if (i < j) { > while (true) { > i++; > while (i < r && a[i] < x) i++; > a[i]--; > while (j > 0 && j > 0) j++; > if (i < j) { > int temp=a[x]; > i++; > a[x]=a[a[i]]; > a[j]=temp; > } > else { > break; > } > } > while (true) { > i--; > x++; > if (j-- < j) a[i]=q; > else { > break; > } > } > if (i < a[i]) { > int temp=a[x]; > j--; > } > else { > break; > } > a[j]=j; > } > else { > q=a[x]=a[j]; > break; > } > break; > } > } > a[i]=i; > a[j]-=j; > } > else { > q=i; > break; > } > while (i < r && a[i] < x) r++; > a[i]--; > while (j > 0 && j > p - 1) j++; > if (i < j) { > int temp=j; > a[i]-=a[j]; > while (i < r && r < x) r++; > } > else { > break; > } > } > while (true) { > i++; > i--; > x++; > if (a[i] > a[j]) a[j]=i; > else { > break; > } > } > a[i]=i; > a[j]-=j; > } > else { > q=j; > break; > }
Diff side-by-side
public class Sort1Quick { public class Sort1Quick {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
return sort(a,0,length - 1); return sort(a,0,length - 1);
} }
public static Integer[] sort( Integer[] a, Integer p, In public static Integer[] sort( Integer[] a, Integer p, In
if (p < r) { if (p < r) {
int q=0; int q=0;
int x=a[p]; int x=a[p];
int i=p - 1; int i=p - 1;
int j=r + 1; int j=r + 1;
while (true) { while (true) {
i++; i++;
> while (i < j && a[i] < x) i++;
> j--;
> while (a[j] > x) j--;
> if (i < j) {
> int temp=a[i];
> a[i]=a[j];
> a[j]=temp;
> }
> else {
> if (i < j) {
> while (true) {
> {
> while (true) {
> i++;
> while (i < r && a[i] < x)
> while (true) {
> i++;
> while (x < r && a[i] < x)
> a[i]--;
> while (j > 0 && j > 0)
> if (i < j) {
> int temp=a[x];
> a[i]+=a[a[i]];
> a[j]=temp;
> }
> else {
> break;
> }
> }
> a[i]--;
> while (j > 0 && 0 > 0) j+
> if (i < j) {
> int temp=r++;
> a[i]+=a[a[i]];
> a[j]=temp;
> }
> else {
> break;
> }
> }
> i++;
> while (true) {
> i++;
> while (i < r && a[i] < x)
> x++;
> while (a[j] > x) j--;
> if (i < j) {
> int temp=a[i];
> a[i]=a[j];
> a[j]=temp;
> }
> else {
> if (i < j) {
> while (true) {
> i++;
while (i < r && a[i] < x) i++; while (i < r && a[i] < x)
> a[i]--;
> while (j > 0 && j > 0)
> if (i < j) {
> int temp=a[x];
> i++;
> a[x]=a[a[i]];
> a[j]=temp;
> }
> else {
> break;
> }
> }
> while (true) {
> i--;
> x++;
> if (j++ < j)
> else {
> break;
> }
> }
> if (i < a[i]) {
> int temp=a[x];
j--; j--;
while (j > p && a[j] > x) j--; | }
> else {
> break;
> }
> a[j]=j;
> }
> else {
> q=a[x]=a[j];
> break;
> }
> break;
> }
> }
> a[i]=i;
> a[j]-=j;
> }
> if (i < j) {
> while (true) {
> i++;
> while (i < r && a[i] < x)
> while (true) {
> i++;
> while (x < r && a[i] < x)
> a[i]--;
> while (j > 0 && j > 0)
> if (i < j) {
> int temp=a[x];
> a[i]+=a[a[i]];
> a[j]=temp;
> }
> else {
> break;
> }
> }
> a[i]--;
> while (j > 0 && 0 > 0) j+
> if (i < j) {
> int temp=r++;
> a[i]+=a[a[i]];
> a[j]=temp;
> }
> else {
> break;
> }
> }
> i++;
> while (true) {
> i++;
> while (i < r && a[i] < x)
> x++;
> while (a[j] > x) j--;
if (i < j) { if (i < j) {
int temp=a[i]; int temp=a[i];
a[i]=a[j]; a[i]=a[j];
a[j]=temp; a[j]=temp;
} }
else { else {
> if (i < j) {
> while (true) {
> i++;
> while (i < r && a[i] < x)
> a[i]--;
> while (j > 0 && j > 0)
> if (i < j) {
> int temp=a[x];
> i++;
> a[x]=a[a[i]];
> a[j]=temp;
> }
> else {
> break;
> }
> }
> while (true) {
> i--;
> x++;
> if (j-- < j)
> else {
> break;
> }
> }
> if (i < a[i]) {
> int temp=a[x];
> j--;
> }
> else {
> break;
> }
> a[j]=j;
> }
> else {
> q=a[x]=a[j];
> break;
> }
> break;
> }
> }
> a[i]=i;
> a[j]-=j;
> }
> else {
> q=i;
> break;
> }
> while (i < r && a[i] < x) r++;
> a[i]--;
> while (j > 0 && j > p - 1) j++;
> if (i < j) {
> int temp=j;
> a[i]-=a[j];
> while (i < r && r < x) r++;
> }
> else {
> break;
> }
> }
> while (true) {
> i++;
> i--;
> x++;
> if (a[i] > a[j]) a[j]=i;
> else {
> break;
> }
> }
> a[i]=i;
> a[j]-=j;
> }
> else {
q=j; q=j;
> break;
> }
break; break;
} }
} }
sort(a,p,q); sort(a,p,q);
sort(a,q + 1,r); sort(a,q + 1,r);
} }
return a; return a;
} }
} }
8 Sort1Radix
Improvements
- mutation & crossover
Original - /home/bck/GP/Exhaustive/Seed-Sort1Radix.java
public class Sort1Radix { public static Integer[] sort( Integer[] a, Integer length){ for (int shift=Integer.SIZE - 1; shift > -1; shift--) { Integer[] tmp=new Integer[a.length]; int j=0; for (int i=0; i < length; i++) { boolean move=a[i] << shift >= 0; if (shift == 0 ? !move : move) { tmp[j]=a[i]; j++; } else { a[i - j]=a[i]; } } for (int i=j; i < tmp.length; i++) { tmp[i]=a[i - j]; } a=tmp; } return a; } }
8.1 Sort1Radix92543.java
Improvements:
shift >0= must be easier thanshift > -1
Improvement Details:
Diff
3c3 < for (int shift=Integer.SIZE - 1; shift > -1; shift--) { --- > for (int shift=Integer.SIZE - 1; shift > 0; shift--) { 21c21,41 < return a; --- > { > for (int shift=0; shift == 0; shift--) { > Integer[] tmp=new Integer[a.length]; > int j=0; > for (int i=j; i < length; i++) { > boolean move=a[i] << shift >= 0; > if (shift == 0 ? !move : move) { > tmp[j]=a[i]; > j++; > } > else { > a[i - j]=a[i]; > } > } > for (int i=j; i < tmp.length; i++) { > tmp[i]=a[i - j]; > } > a=tmp; > } > return a; > }
Diff side-by-side
public class Sort1Radix { public class Sort1Radix {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int shift=Integer.SIZE - 1; shift > -1; shift--) { | for (int shift=Integer.SIZE - 1; shift > 0; shift--) {
Integer[] tmp=new Integer[a.length]; Integer[] tmp=new Integer[a.length];
int j=0; int j=0;
for (int i=0; i < length; i++) { for (int i=0; i < length; i++) {
boolean move=a[i] << shift >= 0; boolean move=a[i] << shift >= 0;
if (shift == 0 ? !move : move) { if (shift == 0 ? !move : move) {
tmp[j]=a[i]; tmp[j]=a[i];
j++; j++;
} }
else { else {
a[i - j]=a[i]; a[i - j]=a[i];
} }
} }
for (int i=j; i < tmp.length; i++) { for (int i=j; i < tmp.length; i++) {
tmp[i]=a[i - j]; tmp[i]=a[i - j];
} }
a=tmp; a=tmp;
} }
> {
> for (int shift=0; shift == 0; shift--) {
> Integer[] tmp=new Integer[a.length];
> int j=0;
> for (int i=j; i < length; i++) {
> boolean move=a[i] << shift >= 0;
> if (shift == 0 ? !move : move) {
> tmp[j]=a[i];
> j++;
> }
> else {
> a[i - j]=a[i];
> }
> }
> for (int i=j; i < tmp.length; i++) {
> tmp[i]=a[i - j];
> }
> a=tmp;
> }
return a; return a;
> }
} }
} }
8.2 Sort1Radix50211
Improvements:
- shift starts from "Integer.Size - 2" instead of "Integer.Size - 1"?
Improvement Details:
Sort1Radix50211 100 mult 0.0 + 0.96745515 = 0.96745515 ASTNodes: 106 GPNodes: 107 xoverApplied: true xovers: 22 mutationApplied: true mutations: 2
Diff
3c3 < for (int shift=Integer.SIZE - 1; shift > -1; shift--) { --- > for (int shift=Integer.SIZE - Integer.SIZE - 1 + Integer.SIZE - 1; shift > -1; shift--) { 6c6 < for (int i=0; i < length; i++) { --- > for (int i=j; i < tmp.length; i++) { 8c8 < if (shift == 0 ? !move : move) { --- > if (shift == 0 << Integer.SIZE + 1 ? !move : move) {
Diff side-by-side
public class Sort1Radix { public class Sort1Radix {
public static Integer[] sort( Integer[] a, Integer length){ public static Integer[] sort( Integer[] a, Integer length){
for (int shift=Integer.SIZE - 1; shift > -1; shift--) { | for (int shift=Integer.SIZE - Integer.SIZE - 1 + Integer.SIZE - 1; shift > -1; sh
Integer[] tmp=new Integer[a.length]; Integer[] tmp=new Integer[a.length];
int j=0; int j=0;
for (int i=0; i < length; i++) { | for (int i=j; i < tmp.length; i++) {
boolean move=a[i] << shift >= 0; boolean move=a[i] << shift >= 0;
if (shift == 0 ? !move : move) { | if (shift == 0 << Integer.SIZE + 1 ? !move : move) {
tmp[j]=a[i]; tmp[j]=a[i];
j++; j++;
} }
else { else {
a[i - j]=a[i]; a[i - j]=a[i];
} }
} }
for (int i=j; i < tmp.length; i++) { for (int i=j; i < tmp.length; i++) {
tmp[i]=a[i - j]; tmp[i]=a[i - j];
} }
a=tmp; a=tmp;
} }
return a; return a;
} }
} }
8.3 Sort1Radix27404.java
Improvement Details:
Diff
3c3 < for (int shift=Integer.SIZE - 1; shift > -1; shift--) { --- > for (int shift=Integer.SIZE - 1; shift > 0; shift--) { 21c21,41 < return a; --- > { > for (int shift=0; shift == 0; shift--) { > Integer[] tmp=new Integer[a.length]; > int j=0; > for (int i=shift; i < length; i++) { > boolean move=a[i] << shift >= 0; > if (shift == 0 ? !move : move) { > tmp[j]=a[i]; > j++; > } > else { > a[i - j]=a[i]; > } > } > for (int i=j; i < tmp.length; i++) { > tmp[i]=a[i - j]; > } > a=tmp; > } > return a; > }
Diff side-by-side
public class Sort1Radix { public class Sort1Radix {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int shift=Integer.SIZE - 1; shift > -1; shift--) { | for (int shift=Integer.SIZE - 1; shift > 0; shift--) {
Integer[] tmp=new Integer[a.length]; Integer[] tmp=new Integer[a.length];
int j=0; int j=0;
for (int i=0; i < length; i++) { for (int i=0; i < length; i++) {
boolean move=a[i] << shift >= 0; boolean move=a[i] << shift >= 0;
if (shift == 0 ? !move : move) { if (shift == 0 ? !move : move) {
tmp[j]=a[i]; tmp[j]=a[i];
j++; j++;
} }
else { else {
a[i - j]=a[i]; a[i - j]=a[i];
} }
} }
for (int i=j; i < tmp.length; i++) { for (int i=j; i < tmp.length; i++) {
tmp[i]=a[i - j]; tmp[i]=a[i - j];
} }
a=tmp; a=tmp;
} }
> {
> for (int shift=0; shift == 0; shift--) {
> Integer[] tmp=new Integer[a.length];
> int j=0;
> for (int i=shift; i < length; i++) {
> boolean move=a[i] << shift >= 0;
> if (shift == 0 ? !move : move) {
> tmp[j]=a[i];
> j++;
> }
> else {
> a[i - j]=a[i];
> }
> }
> for (int i=j; i < tmp.length; i++) {
> tmp[i]=a[i - j];
> }
> a=tmp;
> }
return a; return a;
> }
} }
} }
9 Sort1Shell
Improvements
- crossover & mutations
Original - /home/bck/GP/Exhaustive/Seed-Sort1Shell.java
public class Sort1Shell { public static Integer[] sort( Integer[] a, Integer length){ int increment=length / 2; while (increment > 0) { for (int i=increment; i < length; i++) { int j=i; int temp=a[i]; while (j >= increment && a[j - increment] > temp) { a[j]=a[j - increment]; j=j - increment; } a[j]=temp; } if (increment == 2) { increment=1; } else { increment*=(5.0 / 11); } } return a; } }
9.1 Sort1Shell1245.java
Improvement Details:
Sort1Shell1245 100 mult 0.0 + 0.9919336 = 0.9919336 ASTNodes: 85 GPNodes: 95 xoverApplied: false xovers: 0 mutationApplied: true mutations: 3
Diff
3c3 < int increment=length / 2; --- > int increment=length + 2; 15c15 < increment=1; --- > increment-=1;
Diff side-by-side
public class Sort1Shell { public class Sort1Shell {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
int increment=length / 2; | int increment=length + 2;
while (increment > 0) { while (increment > 0) {
for (int i=increment; i < length; i++) { for (int i=increment; i < length; i++) {
int j=i; int j=i;
int temp=a[i]; int temp=a[i];
while (j >= increment && a[j - increment] > temp) { while (j >= increment && a[j - increment] > temp) {
a[j]=a[j - increment]; a[j]=a[j - increment];
j=j - increment; j=j - increment;
} }
a[j]=temp; a[j]=temp;
} }
if (increment == 2) { if (increment == 2) {
increment=1; | increment-=1;
} }
else { else {
increment*=(5.0 / 11); increment*=(5.0 / 11);
} }
} }
return a; return a;
} }
} }
9.2 Sort1Shell20542.java
Improvement Details:
Sort1Shell20542 100 mult 0.0 + 0.9750917 = 0.9750917 ASTNodes: 102 GPNodes: 112 xoverApplied: false xovers: 0 mutationApplied: true mutations: 2
Diff
3a4,6 > { > increment*=(5.0 / 11); > } 15c18,21 < increment=1; --- > if (11 == 0) increment=increment=1; > else { > } > increment-=1;
Diff side-by-side
public class Sort1Shell { public class Sort1Shell {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
int increment=length / 2; int increment=length / 2;
> {
> increment*=(5.0 / 11);
> }
while (increment > 0) { while (increment > 0) {
for (int i=increment; i < length; i++) { for (int i=increment; i < length; i++) {
int j=i; int j=i;
int temp=a[i]; int temp=a[i];
while (j >= increment && a[j - increment] > temp) { while (j >= increment && a[j - increment] > temp) {
a[j]=a[j - increment]; a[j]=a[j - increment];
j=j - increment; j=j - increment;
} }
a[j]=temp; a[j]=temp;
} }
if (increment == 2) { if (increment == 2) {
increment=1; | if (11 == 0) increment=increment=1;
> else {
> }
> increment-=1;
} }
else { else {
increment*=(5.0 / 11); increment*=(5.0 / 11);
} }
} }
return a; return a;
} }
} }
9.3 Sort1Shell30078.java
Improvement Details:
Sort1Shell30078 100 mult 0.0 + 0.96683884 = 0.96683884 ASTNodes: 690 GPNodes: 705 xoverApplied: true xovers: 2 mutationApplied: true mutations: 1 Sort1Shell30078 100 mult 0.0 + 0.96683884 = 0.96683884 ASTNodes: 690 GPNodes: 705 xoverApplied: true xovers: 2 mutationApplied: true mutations: 1
Diff
3a4,170 > { > { > { > increment+=1; > } > { > { > increment+=1; > } > if (increment == 2) { > for (int i=increment; i < length; i++) { > int j=i; > int temp=a[i]; > while (j >= increment && a[j - increment] > temp) { > a[j]=length; > j=j - increment; > } > a[j]=temp; > } > if (0 > 0) { > while (increment > 0) { > increment-=1; > while (increment > 0) { > increment=1; > if (increment == 2) while (increment > 0) { > for (int i=increment; i < length; i++) { > int j=i; > int temp=0; > while (j >= increment && a[j - j] > temp) { > a[j]=a[j - increment]; > j+=j - increment; > } > a[j]=temp; > } > if (increment == 2) { > increment=1; > } > else { > while (increment > 0) { > for (int i=increment; i < length; i++) { > int j=i; > int temp=j=j - increment; > while (j >= increment && a[j + increment] > temp) { > a[j]=a[j - increment]; > j+=j - increment; > } > a[j]=temp; > } > if (increment == 2) { > while (increment > 0) { > increment=1; > while (increment > 0) { > increment=1; > increment-=1; > } > } > increment=1; > } > else { > { > { > increment+=(5.0 / 11); > } > increment+=1; > } > increment*=(5.0 / 11); > } > } > { > { > increment+=1; > while (increment > 0) { > increment=1; > increment-=1; > } > } > for (int i=increment; i < i; i++) { > int j=i; > int temp=a[j+=j - increment - j]=j - increment; > increment-=1; > a[j]=temp; > } > while (increment > 0) { > increment=1; > if (increment == 2) while (increment > 0) { > for (int i=increment; i < length; i++) { > int j=i; > int temp=a[increment]; > while (j >= increment && a[j - j] > temp) { > j=a[j + increment]; > increment+=j + increment; > } > a[j - a[increment] + temp]=a[i]; > } > if (increment == 2) { > } > else { > while (increment > 0) { > for (int i=increment+=(5.0 / 11); i < length; increment++) { > int j=i; > int temp=j=j - j; > while (j >= increment && a[j - increment] > temp) { > a[j]=a[j - increment]; > j+=j - increment; > } > j*=(1 / 11); > increment+=increment; > increment+=(5.0 / increment); > } > if (increment == 2) { > while (increment > 0) { > increment+=1; > while (increment > 0) { > increment=1; > increment-=1; > } > } > increment=1; > } > else { > { > { > increment+=1; > } > increment+=1; > increment-=increment; > } > increment*=(5.0 / 11); > } > } > { > increment+=(5.0 / 11); > } > { > increment+=(5.0 / 11); > } > increment-=(5.0 / 11); > } > } > else { > increment+=(5.0 / 11); > } > } > } > { > increment+=(5.0 / 11); > } > increment+=(5.0 / 11); > } > } > else { > increment*=(5.0 / 11); > } > } > } > increment+=1; > } > else { > increment*=(5.0 / 11); > } > } > else { > increment*=(5.0 / 11); > } > } > } > } 14c181,183 < if (increment == 2) { --- > { > } > if (11 == 2) {
Diff side-by-side
public class Sort1Shell { public class Sort1Shell {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
int increment=length / 2; int increment=length / 2;
> {
> {
> {
> increment+=1;
> }
> {
> {
> increment+=1;
> }
> if (increment == 2) {
> for (int i=increment; i < length; i++) {
> int j=i;
> int temp=a[i];
> while (j >= increment && a[j - increment] > tem
> a[j]=length;
> j=j - increment;
> }
> a[j]=temp;
> }
> if (0 > 0) {
> while (increment > 0) {
> increment-=1;
> while (increment > 0) {
> increment=1;
> if (increment == 2) while
> for (int i=increment; i < length; i++) {
> int j=i;
> int temp=0;
> while (j >= increment && a[j - j] > tem
> a[j]=a[j - increment];
> j+=j - increment;
> }
> a[j]=temp;
> }
> if (increment == 2) {
> increment=1;
> }
> else {
> while (increment > 0) {
> for (int i=increment; i < length; i++
> int j=i;
> int temp=j=j - increment;
> while (j >= increment && a[j + incr
> a[j]=a[j - increment];
> j+=j - increment;
> }
> a[j]=temp;
> }
> if (increment == 2) {
> while (increment > 0) {
> increment=1;
> while (increment > 0) {
> increment=1;
> increment-=1;
> }
> }
> increment=1;
> }
> else {
> {
> {
> increment+=(5.0 / 11);
> }
> increment+=1;
> }
> increment*=(5.0 / 11);
> }
> }
> {
> {
> increment+=1;
> while (increment > 0) {
> increment=1;
> increment-=1;
> }
> }
> for (int i=increment; i < i; i++) {
> int j=i;
> int temp=a[j+=j - increment - j]=j
> increment-=1;
> a[j]=temp;
> }
> while (increment > 0) {
> increment=1;
> if (increment == 2)
> for (int i=increment; i < length;
> int j=i;
> int temp=a[increment];
> while (j >= increment && a[j -
> j=a[j + increment];
> increment+=j + increment;
> }
> a[j - a[increment] + temp]=a[i]
> }
> if (increment == 2) {
> }
> else {
> while (increment > 0) {
> for (int i=increment+=(5.0 /
> int j=i;
> int temp=j=j - j;
> while (j >= increment && a[
> a[j]=a[j - increment];
> j+=j - increment;
> }
> j*=(1 / 11);
> increment+=increment;
> increment+=(5.0 / increment
> }
> if (increment == 2) {
> while (increment > 0) {
> increment+=1;
> while (increment > 0) {
> increment=1;
> increment-=1;
> }
> }
> increment=1;
> }
> else {
> {
> {
> increment+=1;
> }
> increment+=1;
> increment-=increment;
> }
> increment*=(5.0 / 11);
> }
> }
> {
> increment+=(5.0 / 11);
> }
> {
> increment+=(5.0 / 11);
> }
> increment-=(5.0 / 11);
> }
> }
> else {
> increment+=(5.0 / 11);
> }
> }
> }
> {
> increment+=(5.0 / 11);
> }
> increment+=(5.0 / 11);
> }
> }
> else {
> increment*=(5.0 / 11);
> }
> }
> }
> increment+=1;
> }
> else {
> increment*=(5.0 / 11);
> }
> }
> else {
> increment*=(5.0 / 11);
> }
> }
> }
> }
while (increment > 0) { while (increment > 0) {
for (int i=increment; i < length; i++) { for (int i=increment; i < length; i++) {
int j=i; int j=i;
int temp=a[i]; int temp=a[i];
while (j >= increment && a[j - increment] > temp) { while (j >= increment && a[j - increment] > temp) {
a[j]=a[j - increment]; a[j]=a[j - increment];
j=j - increment; j=j - increment;
} }
a[j]=temp; a[j]=temp;
} }
if (increment == 2) { | {
> }
> if (11 == 2) {
increment=1; increment=1;
} }
else { else {
increment*=(5.0 / 11); increment*=(5.0 / 11);
} }
} }
return a; return a;
} }
} }
10 Sort1ProblemTest
AKA - Bubblesort
Improvements
- Avoids already sorted portion of array
- decrement length in outer loop, instead of incrementing i
- decrement length by i in inner loop, instead of by 1
- result of mutation
Original - /home/bck/GP/Exhaustive/Seed-Sort1ProblemTest.java
public class Sort1ProblemTest { public static Integer[] sort( Integer[] a, Integer length){ for (int i=0; i < length; i++) { for (int j=0; j < length - 1; j++) { if (a[j] > a[j + 1]) { int k=a[j]; a[j]=a[j + 1]; a[j + 1]=k; } } } return a; } }
10.1 Sort1ProblemTest129.java
Improvement Details:
Sort1ProblemTest129 100 mult 0.0 + 0.99895525 = 0.99895525 ASTNodes: 62 GPNodes: 70 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
3c3 < for (int i=0; i < length; i++) { --- > for (int i=1; i < length; i++) {
Diff side-by-side
public class Sort1ProblemTest { public class Sort1ProblemTest {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int i=0; i < length; i++) { | for (int i=1; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
return a; return a;
} }
} }
10.2 Sort1ProblemTest15720.java
Improvement Details:
Sort1ProblemTest15720 100 mult 0.0 + 0.5932812 = 0.5932812 ASTNodes: 62 GPNodes: 70 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
3,4c3,4 < for (int i=0; i < length; i++) { < for (int j=0; j < length - 1; j++) { --- > for (int i=1; i < length; i++) { > for (int j=0; j < length - i; j++) {
Diff side-by-side
public class Sort1ProblemTest { public class Sort1ProblemTest {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int i=0; i < length; i++) { | for (int i=1; i < length; i++) {
for (int j=0; j < length - 1; j++) { | for (int j=0; j < length - i; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
return a; return a;
} }
} }
10.3 Sort1ProblemTest203.java
Improvement Details:
Sort1ProblemTest203 100 mult 0.0 + 0.99895525 = 0.99895525 ASTNodes: 62 GPNodes: 70 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
3c3 < for (int i=0; i < length; i++) { --- > for (int i=1; i < length; i++) {
Diff side-by-side
public class Sort1ProblemTest { public class Sort1ProblemTest {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int i=0; i < length; i++) { | for (int i=1; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
return a; return a;
} }
} }
10.4 Sort1ProblemTest31766.java
Improvement Details:
Sort1ProblemTest31766 100 mult 0.0 + 0.593885 = 0.593885 ASTNodes: 62 GPNodes: 70 xoverApplied: false xovers: 0 mutationApplied: true mutations: 2
Diff
3c3 < for (int i=0; i < length; i++) { --- > for (int i=0; 1 < length; length--) {
Diff side-by-side
public class Sort1ProblemTest { public class Sort1ProblemTest {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int i=0; i < length; i++) { | for (int i=0; 1 < length; length--) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
return a; return a;
} }
} }
10.5 Sort1ProblemTest34187.java
Improvement Details:
Sort1ProblemTest34187 100 mult 0.0 + 0.89872986 = 0.89872986 ASTNodes: 140 GPNodes: 144 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
3c3,16 < for (int i=0; i < length; i++) { --- > for (int i=0; i++ < length; i--) { > { > for (int j=i--; j < length - 1; j++) { > if (a[j] > a[j + 1]) { > int k=a[j]; > a[j]=a[j + 1]; > a[j + 1]=k; > } > } > } > for (int j=i++; j < j - i++; j++) { > } > } > for (int i=0; i++ < length; length--) {
Diff side-by-side
public class Sort1ProblemTest { public class Sort1ProblemTest {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int i=0; i < length; i++) { | for (int i=0; i++ < length; i--) {
> {
> for (int j=i--; j < length - 1; j++) {
> if (a[j] > a[j + 1]) {
> int k=a[j];
> a[j]=a[j + 1];
> a[j + 1]=k;
> }
> }
> }
> for (int j=i++; j < j - i++; j++) {
> }
> }
> for (int i=0; i++ < length; length--) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
return a; return a;
} }
} }
10.6 Sort1ProblemTest3805.java
Improvement Details:
Sort1ProblemTest3805 100 mult 0.0 + 0.99895525 = 0.99895525 ASTNodes: 63 GPNodes: 71 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
3c3 < for (int i=0; i < length; i++) { --- > for (int i=1; i < length; i++) { 12c12,14 < return a; --- > { > return a; > }
Diff side-by-side
public class Sort1ProblemTest { public class Sort1ProblemTest {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int i=0; i < length; i++) { | for (int i=1; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
> {
return a; return a;
> }
} }
} }
10.7 Sort1ProblemTest4174.java
Improvement Details:
Sort1ProblemTest4174 100 mult 0.0 + 0.63620526 = 0.63620526 ASTNodes: 64 GPNodes: 72 xoverApplied: false xovers: 0 mutationApplied: true mutations: 2
Diff
4c4 < for (int j=0; j < length - 1; j++) { --- > for (int j=0; j + i < length - 1; j++) {
Diff side-by-side
public class Sort1ProblemTest { public class Sort1ProblemTest {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int i=0; i < length; i++) { for (int i=0; i < length; i++) {
for (int j=0; j < length - 1; j++) { | for (int j=0; j + i < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
return a; return a;
} }
} }
10.8 Sort1ProblemTest8302.java
Improvement Details:
Sort1ProblemTest8302 100 mult 0.9957507 + 1.1222227E-6 = 99.57507 ASTNodes: 52 GPNodes: 60 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
4c4 < for (int j=0; j < length - 1; j++) { --- > for (int j=0; j < length - 1 - i; j++) {
Diff side-by-side
public class Sort1ProblemTest { public class Sort1ProblemTest {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int i=0; i < length; i++) { for (int i=0; i < length; i++) {
for (int j=0; j < length - 1; j++) { | for (int j=0; j < length - 1 - i; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
return a; return a;
} }
} }
11 huffmanCodeTable.BasicHuffman
Improvements found
- same as in bubblesort
- 1 iteration through loop for getCharFreq not needed
Original - /home/bck/GP/Exhaustive/Seed-huffmanCodeTable.BasicHuffman.java
package huffmanCodeTable; public class BasicHuffman { public static String[] getCodeBook( Byte[] bytes){ BubbleSort.sort(bytes,bytes.length); Byte[] uniqueChars=getUniqueChars(bytes); huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars); huffmanNode huffTree=buildTree(freqTable); String[] codeBook=new String[0]; codeBook=getCodes(huffTree,"",codeBook); return codeBook; } private static String[] getCodes( huffmanNode huffTree, String prefix, String[] codeBook){ if (huffTree.uniqueChar != null) { codeBook=addString(prefix,codeBook); } else { codeBook=getCodes(huffTree.left,prefix + "1",codeBook); codeBook=getCodes(huffTree.right,prefix + "0",codeBook); } return codeBook; } private static String[] addString( String aStr, String[] otherStrings){ String[] newStrings=new String[otherStrings.length + 1]; for (int i=0; i < otherStrings.length; i++) { newStrings[i]=otherStrings[i]; } newStrings[newStrings.length - 1]=aStr; return newStrings; } private static huffmanNode buildTree( huffmanNode[] freqTable){ BubbleSort.sort(freqTable,freqTable.length); huffmanNode aRight=freqTable[freqTable.length - 1]; huffmanNode aLeft=freqTable[freqTable.length - 2]; huffmanNode newNode=new huffmanNode(aRight.getFreq() + aLeft.getFreq(),aRight,aLeft); huffmanNode[] newList=new huffmanNode[freqTable.length - 1]; for (int i=0; i < newList.length; i++) { newList[i]=freqTable[i]; } newList[newList.length - 1]=newNode; if (newList.length == 1) { return newList[0]; } else { return buildTree(newList); } } private static huffmanNode[] getCharFreq( Byte[] bytes, Byte[] uniqueChars){ int[] freqInts=new int[uniqueChars.length]; int charIndex=0; for (int i=0; i < bytes.length; i++) { if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) { freqInts[charIndex]++; } else { charIndex++; freqInts[charIndex]++; } } huffmanNode[] freqTable=new huffmanNode[uniqueChars.length]; for (int i=0; i < uniqueChars.length; i++) { freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i]); } return freqTable; } private static Byte[] getUniqueChars( Byte[] bytes){ Byte[] returnChars=new Byte[1]; returnChars[0]=bytes[0]; for (int i=0; i < bytes.length; i++) { if (returnChars[returnChars.length - 1].compareTo(bytes[i]) != 0) { Byte[] tempChars=returnChars; returnChars=new Byte[tempChars.length + 1]; for (int j=0; j < tempChars.length; j++) { returnChars[j]=tempChars[j]; } returnChars[returnChars.length - 1]=bytes[i]; } } return returnChars; } } package huffmanCodeTable; public class BubbleSort { public static <T extends Comparable<? super T>>void sort( T[] a, Integer length){ for (int i=0; i < length; i++) { for (int j=0; j < length - 1; j++) { if (a[j].compareTo(a[j + 1]) < 0) { T k=a[j]; a[j]=a[j + 1]; a[j + 1]=k; } } } } } package huffmanCodeTable; public class huffmanNode implements Comparable { Byte uniqueChar=null; int freq=0; huffmanNode left, right; public int getFreq(){ return freq; } huffmanNode( byte aChar, int freq){ uniqueChar=aChar; this.freq=freq; } huffmanNode( int freq, huffmanNode left, huffmanNode right){ this.freq=freq; this.right=right; this.left=left; } @Override public int compareTo( Object hN){ return this.freq - ((huffmanNode)hN).freq; } }
11.1 huffmanCodeTable.BasicHuffman12874.java
Improvement Details:
huffmanCodeTable.BasicHuffman12874 100 mult 0.0 + 0.57512116 = 0.57512116 ASTNodes: 411 GPNodes: 381 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
50c50 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 68c68 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 85,86c85,86 < for (int i=0; i < length; i++) { < for (int j=0; j < length - 1; j++) { --- > for (int i=1; i < length; i++) { > for (int j=0; j < length - i; j++) {
Diff side-by-side
package huffmanCodeTable; package huffmanCodeTable;
public class BasicHuffman { public class BasicHuffman {
public static String[] getCodeBook( Byte[] bytes){ public static String[] getCodeBook( Byte[] bytes){
BubbleSort.sort(bytes,bytes.length); BubbleSort.sort(bytes,bytes.length);
Byte[] uniqueChars=getUniqueChars(bytes); Byte[] uniqueChars=getUniqueChars(bytes);
huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars); huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars);
huffmanNode huffTree=buildTree(freqTable); huffmanNode huffTree=buildTree(freqTable);
String[] codeBook=new String[0]; String[] codeBook=new String[0];
codeBook=getCodes(huffTree,"",codeBook); codeBook=getCodes(huffTree,"",codeBook);
return codeBook; return codeBook;
} }
private static String[] getCodes( huffmanNode huffTree, S private static String[] getCodes( huffmanNode huffTree, S
if (huffTree.uniqueChar != null) { if (huffTree.uniqueChar != null) {
codeBook=addString(prefix,codeBook); codeBook=addString(prefix,codeBook);
} }
else { else {
codeBook=getCodes(huffTree.left,prefix + "1",codeBook); codeBook=getCodes(huffTree.left,prefix + "1",codeBook);
codeBook=getCodes(huffTree.right,prefix + "0",codeBook) codeBook=getCodes(huffTree.right,prefix + "0",codeBook)
} }
return codeBook; return codeBook;
} }
private static String[] addString( String aStr, String[] private static String[] addString( String aStr, String[]
String[] newStrings=new String[otherStrings.length + 1]; String[] newStrings=new String[otherStrings.length + 1];
for (int i=0; i < otherStrings.length; i++) { for (int i=0; i < otherStrings.length; i++) {
newStrings[i]=otherStrings[i]; newStrings[i]=otherStrings[i];
} }
newStrings[newStrings.length - 1]=aStr; newStrings[newStrings.length - 1]=aStr;
return newStrings; return newStrings;
} }
private static huffmanNode buildTree( huffmanNode[] freqTa private static huffmanNode buildTree( huffmanNode[] freqTa
BubbleSort.sort(freqTable,freqTable.length); BubbleSort.sort(freqTable,freqTable.length);
huffmanNode aRight=freqTable[freqTable.length - 1]; huffmanNode aRight=freqTable[freqTable.length - 1];
huffmanNode aLeft=freqTable[freqTable.length - 2]; huffmanNode aLeft=freqTable[freqTable.length - 2];
huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL
huffmanNode[] newList=new huffmanNode[freqTable.length - huffmanNode[] newList=new huffmanNode[freqTable.length -
for (int i=0; i < newList.length; i++) { for (int i=0; i < newList.length; i++) {
newList[i]=freqTable[i]; newList[i]=freqTable[i];
} }
newList[newList.length - 1]=newNode; newList[newList.length - 1]=newNode;
if (newList.length == 1) { if (newList.length == 1) {
return newList[0]; return newList[0];
} }
else { else {
return buildTree(newList); return buildTree(newList);
} }
} }
private static huffmanNode[] getCharFreq( Byte[] bytes, B private static huffmanNode[] getCharFreq( Byte[] bytes, B
int[] freqInts=new int[uniqueChars.length]; int[] freqInts=new int[uniqueChars.length];
int charIndex=0; int charIndex=0;
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) { if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) {
freqInts[charIndex]++; freqInts[charIndex]++;
} }
else { else {
charIndex++; charIndex++;
freqInts[charIndex]++; freqInts[charIndex]++;
} }
} }
huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt
for (int i=0; i < uniqueChars.length; i++) { for (int i=0; i < uniqueChars.length; i++) {
freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i] freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i]
} }
return freqTable; return freqTable;
} }
private static Byte[] getUniqueChars( Byte[] bytes){ private static Byte[] getUniqueChars( Byte[] bytes){
Byte[] returnChars=new Byte[1]; Byte[] returnChars=new Byte[1];
returnChars[0]=bytes[0]; returnChars[0]=bytes[0];
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (returnChars[returnChars.length - 1].compareTo(bytes if (returnChars[returnChars.length - 1].compareTo(bytes
Byte[] tempChars=returnChars; Byte[] tempChars=returnChars;
returnChars=new Byte[tempChars.length + 1]; returnChars=new Byte[tempChars.length + 1];
for (int j=0; j < tempChars.length; j++) { for (int j=0; j < tempChars.length; j++) {
returnChars[j]=tempChars[j]; returnChars[j]=tempChars[j];
} }
returnChars[returnChars.length - 1]=bytes[i]; returnChars[returnChars.length - 1]=bytes[i];
} }
} }
return returnChars; return returnChars;
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class BubbleSort { public class BubbleSort {
public static <T extends Comparable<? super T>>void sort( public static <T extends Comparable<? super T>>void sort(
for (int i=0; i < length; i++) { | for (int i=1; i < length; i++) {
for (int j=0; j < length - 1; j++) { | for (int j=0; j < length - i; j++) {
if (a[j].compareTo(a[j + 1]) < 0) { if (a[j].compareTo(a[j + 1]) < 0) {
T k=a[j]; T k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class huffmanNode implements Comparable { public class huffmanNode implements Comparable {
Byte uniqueChar=null; Byte uniqueChar=null;
int freq=0; int freq=0;
huffmanNode left, right; huffmanNode left, right;
public int getFreq(){ public int getFreq(){
return freq; return freq;
} }
huffmanNode( byte aChar, int freq){ huffmanNode( byte aChar, int freq){
uniqueChar=aChar; uniqueChar=aChar;
this.freq=freq; this.freq=freq;
} }
huffmanNode( int freq, huffmanNode left, huffmanNode rig huffmanNode( int freq, huffmanNode left, huffmanNode rig
this.freq=freq; this.freq=freq;
this.right=right; this.right=right;
this.left=left; this.left=left;
} }
@Override public int compareTo( Object hN){ @Override public int compareTo( Object hN){
return this.freq - ((huffmanNode)hN).freq; return this.freq - ((huffmanNode)hN).freq;
} }
} }
11.2 huffmanCodeTable.BasicHuffman15166.java
Improvement Details:
huffmanCodeTable.BasicHuffman15166 100 mult 0.0 + 0.9998278 = 0.9998278 ASTNodes: 411 GPNodes: 381 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
50c50 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 68c68 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) {
Diff side-by-side
package huffmanCodeTable; package huffmanCodeTable;
public class BasicHuffman { public class BasicHuffman {
public static String[] getCodeBook( Byte[] bytes){ public static String[] getCodeBook( Byte[] bytes){
BubbleSort.sort(bytes,bytes.length); BubbleSort.sort(bytes,bytes.length);
Byte[] uniqueChars=getUniqueChars(bytes); Byte[] uniqueChars=getUniqueChars(bytes);
huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars); huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars);
huffmanNode huffTree=buildTree(freqTable); huffmanNode huffTree=buildTree(freqTable);
String[] codeBook=new String[0]; String[] codeBook=new String[0];
codeBook=getCodes(huffTree,"",codeBook); codeBook=getCodes(huffTree,"",codeBook);
return codeBook; return codeBook;
} }
private static String[] getCodes( huffmanNode huffTree, S private static String[] getCodes( huffmanNode huffTree, S
if (huffTree.uniqueChar != null) { if (huffTree.uniqueChar != null) {
codeBook=addString(prefix,codeBook); codeBook=addString(prefix,codeBook);
} }
else { else {
codeBook=getCodes(huffTree.left,prefix + "1",codeBook); codeBook=getCodes(huffTree.left,prefix + "1",codeBook);
codeBook=getCodes(huffTree.right,prefix + "0",codeBook) codeBook=getCodes(huffTree.right,prefix + "0",codeBook)
} }
return codeBook; return codeBook;
} }
private static String[] addString( String aStr, String[] private static String[] addString( String aStr, String[]
String[] newStrings=new String[otherStrings.length + 1]; String[] newStrings=new String[otherStrings.length + 1];
for (int i=0; i < otherStrings.length; i++) { for (int i=0; i < otherStrings.length; i++) {
newStrings[i]=otherStrings[i]; newStrings[i]=otherStrings[i];
} }
newStrings[newStrings.length - 1]=aStr; newStrings[newStrings.length - 1]=aStr;
return newStrings; return newStrings;
} }
private static huffmanNode buildTree( huffmanNode[] freqTa private static huffmanNode buildTree( huffmanNode[] freqTa
BubbleSort.sort(freqTable,freqTable.length); BubbleSort.sort(freqTable,freqTable.length);
huffmanNode aRight=freqTable[freqTable.length - 1]; huffmanNode aRight=freqTable[freqTable.length - 1];
huffmanNode aLeft=freqTable[freqTable.length - 2]; huffmanNode aLeft=freqTable[freqTable.length - 2];
huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL
huffmanNode[] newList=new huffmanNode[freqTable.length - huffmanNode[] newList=new huffmanNode[freqTable.length -
for (int i=0; i < newList.length; i++) { for (int i=0; i < newList.length; i++) {
newList[i]=freqTable[i]; newList[i]=freqTable[i];
} }
newList[newList.length - 1]=newNode; newList[newList.length - 1]=newNode;
if (newList.length == 1) { if (newList.length == 1) {
return newList[0]; return newList[0];
} }
else { else {
return buildTree(newList); return buildTree(newList);
} }
} }
private static huffmanNode[] getCharFreq( Byte[] bytes, B private static huffmanNode[] getCharFreq( Byte[] bytes, B
int[] freqInts=new int[uniqueChars.length]; int[] freqInts=new int[uniqueChars.length];
int charIndex=0; int charIndex=0;
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) { if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) {
freqInts[charIndex]++; freqInts[charIndex]++;
} }
else { else {
charIndex++; charIndex++;
freqInts[charIndex]++; freqInts[charIndex]++;
} }
} }
huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt
for (int i=0; i < uniqueChars.length; i++) { for (int i=0; i < uniqueChars.length; i++) {
freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i] freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i]
} }
return freqTable; return freqTable;
} }
private static Byte[] getUniqueChars( Byte[] bytes){ private static Byte[] getUniqueChars( Byte[] bytes){
Byte[] returnChars=new Byte[1]; Byte[] returnChars=new Byte[1];
returnChars[0]=bytes[0]; returnChars[0]=bytes[0];
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (returnChars[returnChars.length - 1].compareTo(bytes if (returnChars[returnChars.length - 1].compareTo(bytes
Byte[] tempChars=returnChars; Byte[] tempChars=returnChars;
returnChars=new Byte[tempChars.length + 1]; returnChars=new Byte[tempChars.length + 1];
for (int j=0; j < tempChars.length; j++) { for (int j=0; j < tempChars.length; j++) {
returnChars[j]=tempChars[j]; returnChars[j]=tempChars[j];
} }
returnChars[returnChars.length - 1]=bytes[i]; returnChars[returnChars.length - 1]=bytes[i];
} }
} }
return returnChars; return returnChars;
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class BubbleSort { public class BubbleSort {
public static <T extends Comparable<? super T>>void sort( public static <T extends Comparable<? super T>>void sort(
for (int i=0; i < length; i++) { for (int i=0; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j].compareTo(a[j + 1]) < 0) { if (a[j].compareTo(a[j + 1]) < 0) {
T k=a[j]; T k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class huffmanNode implements Comparable { public class huffmanNode implements Comparable {
Byte uniqueChar=null; Byte uniqueChar=null;
int freq=0; int freq=0;
huffmanNode left, right; huffmanNode left, right;
public int getFreq(){ public int getFreq(){
return freq; return freq;
} }
huffmanNode( byte aChar, int freq){ huffmanNode( byte aChar, int freq){
uniqueChar=aChar; uniqueChar=aChar;
this.freq=freq; this.freq=freq;
} }
huffmanNode( int freq, huffmanNode left, huffmanNode rig huffmanNode( int freq, huffmanNode left, huffmanNode rig
this.freq=freq; this.freq=freq;
this.right=right; this.right=right;
this.left=left; this.left=left;
} }
@Override public int compareTo( Object hN){ @Override public int compareTo( Object hN){
return this.freq - ((huffmanNode)hN).freq; return this.freq - ((huffmanNode)hN).freq;
} }
} }
11.3 huffmanCodeTable.BasicHuffman26559.java
Improvement Details:
huffmanCodeTable.BasicHuffman26559 100 mult 0.0 + 0.57512116 = 0.57512116 ASTNodes: 414 GPNodes: 384 xoverApplied: true xovers: 2 mutationApplied: true mutations: 1
Diff
50c50 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 68c68 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 85,86c85,86 < for (int i=0; i < length; i++) { < for (int j=0; j < length - 1; j++) { --- > for (int i=1; i < length; i++) { > for (int j=0; j < length - i; j++) { 114a115 > this.freq=freq;
Diff side-by-side
package huffmanCodeTable; package huffmanCodeTable;
public class BasicHuffman { public class BasicHuffman {
public static String[] getCodeBook( Byte[] bytes){ public static String[] getCodeBook( Byte[] bytes){
BubbleSort.sort(bytes,bytes.length); BubbleSort.sort(bytes,bytes.length);
Byte[] uniqueChars=getUniqueChars(bytes); Byte[] uniqueChars=getUniqueChars(bytes);
huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars); huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars);
huffmanNode huffTree=buildTree(freqTable); huffmanNode huffTree=buildTree(freqTable);
String[] codeBook=new String[0]; String[] codeBook=new String[0];
codeBook=getCodes(huffTree,"",codeBook); codeBook=getCodes(huffTree,"",codeBook);
return codeBook; return codeBook;
} }
private static String[] getCodes( huffmanNode huffTree, S private static String[] getCodes( huffmanNode huffTree, S
if (huffTree.uniqueChar != null) { if (huffTree.uniqueChar != null) {
codeBook=addString(prefix,codeBook); codeBook=addString(prefix,codeBook);
} }
else { else {
codeBook=getCodes(huffTree.left,prefix + "1",codeBook); codeBook=getCodes(huffTree.left,prefix + "1",codeBook);
codeBook=getCodes(huffTree.right,prefix + "0",codeBook) codeBook=getCodes(huffTree.right,prefix + "0",codeBook)
} }
return codeBook; return codeBook;
} }
private static String[] addString( String aStr, String[] private static String[] addString( String aStr, String[]
String[] newStrings=new String[otherStrings.length + 1]; String[] newStrings=new String[otherStrings.length + 1];
for (int i=0; i < otherStrings.length; i++) { for (int i=0; i < otherStrings.length; i++) {
newStrings[i]=otherStrings[i]; newStrings[i]=otherStrings[i];
} }
newStrings[newStrings.length - 1]=aStr; newStrings[newStrings.length - 1]=aStr;
return newStrings; return newStrings;
} }
private static huffmanNode buildTree( huffmanNode[] freqTa private static huffmanNode buildTree( huffmanNode[] freqTa
BubbleSort.sort(freqTable,freqTable.length); BubbleSort.sort(freqTable,freqTable.length);
huffmanNode aRight=freqTable[freqTable.length - 1]; huffmanNode aRight=freqTable[freqTable.length - 1];
huffmanNode aLeft=freqTable[freqTable.length - 2]; huffmanNode aLeft=freqTable[freqTable.length - 2];
huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL
huffmanNode[] newList=new huffmanNode[freqTable.length - huffmanNode[] newList=new huffmanNode[freqTable.length -
for (int i=0; i < newList.length; i++) { for (int i=0; i < newList.length; i++) {
newList[i]=freqTable[i]; newList[i]=freqTable[i];
} }
newList[newList.length - 1]=newNode; newList[newList.length - 1]=newNode;
if (newList.length == 1) { if (newList.length == 1) {
return newList[0]; return newList[0];
} }
else { else {
return buildTree(newList); return buildTree(newList);
} }
} }
private static huffmanNode[] getCharFreq( Byte[] bytes, B private static huffmanNode[] getCharFreq( Byte[] bytes, B
int[] freqInts=new int[uniqueChars.length]; int[] freqInts=new int[uniqueChars.length];
int charIndex=0; int charIndex=0;
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) { if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) {
freqInts[charIndex]++; freqInts[charIndex]++;
} }
else { else {
charIndex++; charIndex++;
freqInts[charIndex]++; freqInts[charIndex]++;
} }
} }
huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt
for (int i=0; i < uniqueChars.length; i++) { for (int i=0; i < uniqueChars.length; i++) {
freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i] freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i]
} }
return freqTable; return freqTable;
} }
private static Byte[] getUniqueChars( Byte[] bytes){ private static Byte[] getUniqueChars( Byte[] bytes){
Byte[] returnChars=new Byte[1]; Byte[] returnChars=new Byte[1];
returnChars[0]=bytes[0]; returnChars[0]=bytes[0];
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (returnChars[returnChars.length - 1].compareTo(bytes if (returnChars[returnChars.length - 1].compareTo(bytes
Byte[] tempChars=returnChars; Byte[] tempChars=returnChars;
returnChars=new Byte[tempChars.length + 1]; returnChars=new Byte[tempChars.length + 1];
for (int j=0; j < tempChars.length; j++) { for (int j=0; j < tempChars.length; j++) {
returnChars[j]=tempChars[j]; returnChars[j]=tempChars[j];
} }
returnChars[returnChars.length - 1]=bytes[i]; returnChars[returnChars.length - 1]=bytes[i];
} }
} }
return returnChars; return returnChars;
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class BubbleSort { public class BubbleSort {
public static <T extends Comparable<? super T>>void sort( public static <T extends Comparable<? super T>>void sort(
for (int i=0; i < length; i++) { | for (int i=1; i < length; i++) {
for (int j=0; j < length - 1; j++) { | for (int j=0; j < length - i; j++) {
if (a[j].compareTo(a[j + 1]) < 0) { if (a[j].compareTo(a[j + 1]) < 0) {
T k=a[j]; T k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class huffmanNode implements Comparable { public class huffmanNode implements Comparable {
Byte uniqueChar=null; Byte uniqueChar=null;
int freq=0; int freq=0;
huffmanNode left, right; huffmanNode left, right;
public int getFreq(){ public int getFreq(){
return freq; return freq;
} }
huffmanNode( byte aChar, int freq){ huffmanNode( byte aChar, int freq){
uniqueChar=aChar; uniqueChar=aChar;
this.freq=freq; this.freq=freq;
} }
huffmanNode( int freq, huffmanNode left, huffmanNode rig huffmanNode( int freq, huffmanNode left, huffmanNode rig
this.freq=freq; this.freq=freq;
this.right=right; this.right=right;
this.left=left; this.left=left;
} }
@Override public int compareTo( Object hN){ @Override public int compareTo( Object hN){
> this.freq=freq;
return this.freq - ((huffmanNode)hN).freq; return this.freq - ((huffmanNode)hN).freq;
} }
} }
11.4 huffmanCodeTable.BasicHuffman27005.java
Improvement Details:
huffmanCodeTable.BasicHuffman27005 100 mult 0.0 + 0.57512116 = 0.57512116 ASTNodes: 665 GPNodes: 618 xoverApplied: true xovers: 3 mutationApplied: true mutations: 1
Diff
2a3,5 > /** > * Deliberately bad huffman > */ 21a25,35 > private static String[] addString( String[] someStrings, String[] otherStrings){ > String[] newStrings=new String[otherStrings.length + someStrings.length]; > for (int i=0; i < otherStrings.length; i--) { > newStrings[i]=otherStrings[i]; > } > int offset=otherStrings.length; > for (int i=0; i < someStrings.length; i++) { > newStrings[i - offset]=someStrings[i]; > } > return newStrings; > } 50c64 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 68c82 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 79a94,108 > static void printCodeBook( String[] codeBook){ > for (int i=0; i < codeBook.length; i++) { > System.out.println(codeBook[i]); > } > } > static void printCodeBook( byte[] codeBook){ > byte mask=1; > for (int i=0; i < codeBook.length; i++) { > for (int j=7; j++ >= 0; j--) { > if ((codeBook[i] & (mask << j)) > 0) System.out.print("1"); > else System.out.print("0"); > } > System.out.print("\n"); > } > } 84c113 < public static <T extends Comparable<? super T>>void sort( T[] a, Integer length){ --- > public static void sort( Integer[] a, Integer length){ 86a116,142 > if (a[j] > a[j + 1]) { > int k=a[j]; > a[j]=a[j - 1]; > a[j + 1]=k; > } > } > } > } > public static void sort( byte[] a, Integer length){ > for (int i=0; i < length; i++) { > for (int j=0; j < length + 1; j++) { > { > byte k=0; > a[i]=a[j + 1]; > a[j + 1]-=k; > } > if (a[length - 2] > a[j + 1]) { > byte k=a[j]; > a[j]=a[j + 1]; > a[j + 1]=k; > } > } > } > } > public static <T extends Comparable<? super T>>void sort( T[] a, Integer length){ > for (int i=1; i < length; i++) { > for (int j=0; j < length - i; j++) {
Diff side-by-side
package huffmanCodeTable; package huffmanCodeTable;
public class BasicHuffman { public class BasicHuffman {
> /**
> * Deliberately bad huffman
> */
public static String[] getCodeBook( Byte[] bytes){ public static String[] getCodeBook( Byte[] bytes){
BubbleSort.sort(bytes,bytes.length); BubbleSort.sort(bytes,bytes.length);
Byte[] uniqueChars=getUniqueChars(bytes); Byte[] uniqueChars=getUniqueChars(bytes);
huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars); huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars);
huffmanNode huffTree=buildTree(freqTable); huffmanNode huffTree=buildTree(freqTable);
String[] codeBook=new String[0]; String[] codeBook=new String[0];
codeBook=getCodes(huffTree,"",codeBook); codeBook=getCodes(huffTree,"",codeBook);
return codeBook; return codeBook;
} }
private static String[] getCodes( huffmanNode huffTree, S private static String[] getCodes( huffmanNode huffTree, S
if (huffTree.uniqueChar != null) { if (huffTree.uniqueChar != null) {
codeBook=addString(prefix,codeBook); codeBook=addString(prefix,codeBook);
} }
else { else {
codeBook=getCodes(huffTree.left,prefix + "1",codeBook); codeBook=getCodes(huffTree.left,prefix + "1",codeBook);
codeBook=getCodes(huffTree.right,prefix + "0",codeBook) codeBook=getCodes(huffTree.right,prefix + "0",codeBook)
} }
return codeBook; return codeBook;
} }
> private static String[] addString( String[] someStrings,
> String[] newStrings=new String[otherStrings.length + some
> for (int i=0; i < otherStrings.length; i--) {
> newStrings[i]=otherStrings[i];
> }
> int offset=otherStrings.length;
> for (int i=0; i < someStrings.length; i++) {
> newStrings[i - offset]=someStrings[i];
> }
> return newStrings;
> }
private static String[] addString( String aStr, String[] private static String[] addString( String aStr, String[]
String[] newStrings=new String[otherStrings.length + 1]; String[] newStrings=new String[otherStrings.length + 1];
for (int i=0; i < otherStrings.length; i++) { for (int i=0; i < otherStrings.length; i++) {
newStrings[i]=otherStrings[i]; newStrings[i]=otherStrings[i];
} }
newStrings[newStrings.length - 1]=aStr; newStrings[newStrings.length - 1]=aStr;
return newStrings; return newStrings;
} }
private static huffmanNode buildTree( huffmanNode[] freqTa private static huffmanNode buildTree( huffmanNode[] freqTa
BubbleSort.sort(freqTable,freqTable.length); BubbleSort.sort(freqTable,freqTable.length);
huffmanNode aRight=freqTable[freqTable.length - 1]; huffmanNode aRight=freqTable[freqTable.length - 1];
huffmanNode aLeft=freqTable[freqTable.length - 2]; huffmanNode aLeft=freqTable[freqTable.length - 2];
huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL
huffmanNode[] newList=new huffmanNode[freqTable.length - huffmanNode[] newList=new huffmanNode[freqTable.length -
for (int i=0; i < newList.length; i++) { for (int i=0; i < newList.length; i++) {
newList[i]=freqTable[i]; newList[i]=freqTable[i];
} }
newList[newList.length - 1]=newNode; newList[newList.length - 1]=newNode;
if (newList.length == 1) { if (newList.length == 1) {
return newList[0]; return newList[0];
} }
else { else {
return buildTree(newList); return buildTree(newList);
} }
} }
private static huffmanNode[] getCharFreq( Byte[] bytes, B private static huffmanNode[] getCharFreq( Byte[] bytes, B
int[] freqInts=new int[uniqueChars.length]; int[] freqInts=new int[uniqueChars.length];
int charIndex=0; int charIndex=0;
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) { if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) {
freqInts[charIndex]++; freqInts[charIndex]++;
} }
else { else {
charIndex++; charIndex++;
freqInts[charIndex]++; freqInts[charIndex]++;
} }
} }
huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt
for (int i=0; i < uniqueChars.length; i++) { for (int i=0; i < uniqueChars.length; i++) {
freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i] freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i]
} }
return freqTable; return freqTable;
} }
private static Byte[] getUniqueChars( Byte[] bytes){ private static Byte[] getUniqueChars( Byte[] bytes){
Byte[] returnChars=new Byte[1]; Byte[] returnChars=new Byte[1];
returnChars[0]=bytes[0]; returnChars[0]=bytes[0];
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (returnChars[returnChars.length - 1].compareTo(bytes if (returnChars[returnChars.length - 1].compareTo(bytes
Byte[] tempChars=returnChars; Byte[] tempChars=returnChars;
returnChars=new Byte[tempChars.length + 1]; returnChars=new Byte[tempChars.length + 1];
for (int j=0; j < tempChars.length; j++) { for (int j=0; j < tempChars.length; j++) {
returnChars[j]=tempChars[j]; returnChars[j]=tempChars[j];
} }
returnChars[returnChars.length - 1]=bytes[i]; returnChars[returnChars.length - 1]=bytes[i];
} }
} }
return returnChars; return returnChars;
} }
> static void printCodeBook( String[] codeBook){
> for (int i=0; i < codeBook.length; i++) {
> System.out.println(codeBook[i]);
> }
> }
> static void printCodeBook( byte[] codeBook){
> byte mask=1;
> for (int i=0; i < codeBook.length; i++) {
> for (int j=7; j++ >= 0; j--) {
> if ((codeBook[i] & (mask << j)) > 0) System.o
> else System.out.print("0");
> }
> System.out.print("\n");
> }
> }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class BubbleSort { public class BubbleSort {
public static <T extends Comparable<? super T>>void sort( | public static void sort( Integer[] a, Integer length){
for (int i=0; i < length; i++) { for (int i=0; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
> if (a[j] > a[j + 1]) {
> int k=a[j];
> a[j]=a[j - 1];
> a[j + 1]=k;
> }
> }
> }
> }
> public static void sort( byte[] a, Integer length){
> for (int i=0; i < length; i++) {
> for (int j=0; j < length + 1; j++) {
> {
> byte k=0;
> a[i]=a[j + 1];
> a[j + 1]-=k;
> }
> if (a[length - 2] > a[j + 1]) {
> byte k=a[j];
> a[j]=a[j + 1];
> a[j + 1]=k;
> }
> }
> }
> }
> public static <T extends Comparable<? super T>>void sort(
> for (int i=1; i < length; i++) {
> for (int j=0; j < length - i; j++) {
if (a[j].compareTo(a[j + 1]) < 0) { if (a[j].compareTo(a[j + 1]) < 0) {
T k=a[j]; T k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class huffmanNode implements Comparable { public class huffmanNode implements Comparable {
Byte uniqueChar=null; Byte uniqueChar=null;
int freq=0; int freq=0;
huffmanNode left, right; huffmanNode left, right;
public int getFreq(){ public int getFreq(){
return freq; return freq;
} }
huffmanNode( byte aChar, int freq){ huffmanNode( byte aChar, int freq){
uniqueChar=aChar; uniqueChar=aChar;
this.freq=freq; this.freq=freq;
} }
huffmanNode( int freq, huffmanNode left, huffmanNode rig huffmanNode( int freq, huffmanNode left, huffmanNode rig
this.freq=freq; this.freq=freq;
this.right=right; this.right=right;
this.left=left; this.left=left;
} }
@Override public int compareTo( Object hN){ @Override public int compareTo( Object hN){
return this.freq - ((huffmanNode)hN).freq; return this.freq - ((huffmanNode)hN).freq;
} }
} }
11.5 huffmanCodeTable.BasicHuffman298.java
Improvement Details:
huffmanCodeTable.BasicHuffman298 100 mult 0.0 + 0.9999736 = 0.9999736 ASTNodes: 411 GPNodes: 381 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
68c68 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) {
Diff side-by-side
package huffmanCodeTable; package huffmanCodeTable;
public class BasicHuffman { public class BasicHuffman {
public static String[] getCodeBook( Byte[] bytes){ public static String[] getCodeBook( Byte[] bytes){
BubbleSort.sort(bytes,bytes.length); BubbleSort.sort(bytes,bytes.length);
Byte[] uniqueChars=getUniqueChars(bytes); Byte[] uniqueChars=getUniqueChars(bytes);
huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars); huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars);
huffmanNode huffTree=buildTree(freqTable); huffmanNode huffTree=buildTree(freqTable);
String[] codeBook=new String[0]; String[] codeBook=new String[0];
codeBook=getCodes(huffTree,"",codeBook); codeBook=getCodes(huffTree,"",codeBook);
return codeBook; return codeBook;
} }
private static String[] getCodes( huffmanNode huffTree, S private static String[] getCodes( huffmanNode huffTree, S
if (huffTree.uniqueChar != null) { if (huffTree.uniqueChar != null) {
codeBook=addString(prefix,codeBook); codeBook=addString(prefix,codeBook);
} }
else { else {
codeBook=getCodes(huffTree.left,prefix + "1",codeBook); codeBook=getCodes(huffTree.left,prefix + "1",codeBook);
codeBook=getCodes(huffTree.right,prefix + "0",codeBook) codeBook=getCodes(huffTree.right,prefix + "0",codeBook)
} }
return codeBook; return codeBook;
} }
private static String[] addString( String aStr, String[] private static String[] addString( String aStr, String[]
String[] newStrings=new String[otherStrings.length + 1]; String[] newStrings=new String[otherStrings.length + 1];
for (int i=0; i < otherStrings.length; i++) { for (int i=0; i < otherStrings.length; i++) {
newStrings[i]=otherStrings[i]; newStrings[i]=otherStrings[i];
} }
newStrings[newStrings.length - 1]=aStr; newStrings[newStrings.length - 1]=aStr;
return newStrings; return newStrings;
} }
private static huffmanNode buildTree( huffmanNode[] freqTa private static huffmanNode buildTree( huffmanNode[] freqTa
BubbleSort.sort(freqTable,freqTable.length); BubbleSort.sort(freqTable,freqTable.length);
huffmanNode aRight=freqTable[freqTable.length - 1]; huffmanNode aRight=freqTable[freqTable.length - 1];
huffmanNode aLeft=freqTable[freqTable.length - 2]; huffmanNode aLeft=freqTable[freqTable.length - 2];
huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL
huffmanNode[] newList=new huffmanNode[freqTable.length - huffmanNode[] newList=new huffmanNode[freqTable.length -
for (int i=0; i < newList.length; i++) { for (int i=0; i < newList.length; i++) {
newList[i]=freqTable[i]; newList[i]=freqTable[i];
} }
newList[newList.length - 1]=newNode; newList[newList.length - 1]=newNode;
if (newList.length == 1) { if (newList.length == 1) {
return newList[0]; return newList[0];
} }
else { else {
return buildTree(newList); return buildTree(newList);
} }
} }
private static huffmanNode[] getCharFreq( Byte[] bytes, B private static huffmanNode[] getCharFreq( Byte[] bytes, B
int[] freqInts=new int[uniqueChars.length]; int[] freqInts=new int[uniqueChars.length];
int charIndex=0; int charIndex=0;
for (int i=0; i < bytes.length; i++) { for (int i=0; i < bytes.length; i++) {
if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) { if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) {
freqInts[charIndex]++; freqInts[charIndex]++;
} }
else { else {
charIndex++; charIndex++;
freqInts[charIndex]++; freqInts[charIndex]++;
} }
} }
huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt
for (int i=0; i < uniqueChars.length; i++) { for (int i=0; i < uniqueChars.length; i++) {
freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i] freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i]
} }
return freqTable; return freqTable;
} }
private static Byte[] getUniqueChars( Byte[] bytes){ private static Byte[] getUniqueChars( Byte[] bytes){
Byte[] returnChars=new Byte[1]; Byte[] returnChars=new Byte[1];
returnChars[0]=bytes[0]; returnChars[0]=bytes[0];
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (returnChars[returnChars.length - 1].compareTo(bytes if (returnChars[returnChars.length - 1].compareTo(bytes
Byte[] tempChars=returnChars; Byte[] tempChars=returnChars;
returnChars=new Byte[tempChars.length + 1]; returnChars=new Byte[tempChars.length + 1];
for (int j=0; j < tempChars.length; j++) { for (int j=0; j < tempChars.length; j++) {
returnChars[j]=tempChars[j]; returnChars[j]=tempChars[j];
} }
returnChars[returnChars.length - 1]=bytes[i]; returnChars[returnChars.length - 1]=bytes[i];
} }
} }
return returnChars; return returnChars;
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class BubbleSort { public class BubbleSort {
public static <T extends Comparable<? super T>>void sort( public static <T extends Comparable<? super T>>void sort(
for (int i=0; i < length; i++) { for (int i=0; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j].compareTo(a[j + 1]) < 0) { if (a[j].compareTo(a[j + 1]) < 0) {
T k=a[j]; T k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class huffmanNode implements Comparable { public class huffmanNode implements Comparable {
Byte uniqueChar=null; Byte uniqueChar=null;
int freq=0; int freq=0;
huffmanNode left, right; huffmanNode left, right;
public int getFreq(){ public int getFreq(){
return freq; return freq;
} }
huffmanNode( byte aChar, int freq){ huffmanNode( byte aChar, int freq){
uniqueChar=aChar; uniqueChar=aChar;
this.freq=freq; this.freq=freq;
} }
huffmanNode( int freq, huffmanNode left, huffmanNode rig huffmanNode( int freq, huffmanNode left, huffmanNode rig
this.freq=freq; this.freq=freq;
this.right=right; this.right=right;
this.left=left; this.left=left;
} }
@Override public int compareTo( Object hN){ @Override public int compareTo( Object hN){
return this.freq - ((huffmanNode)hN).freq; return this.freq - ((huffmanNode)hN).freq;
} }
} }
11.6 huffmanCodeTable.BasicHuffman33602.java
Improvement Details:
huffmanCodeTable.BasicHuffman33602 100 mult 0.0 + 0.57512116 = 0.57512116 ASTNodes: 411 GPNodes: 381 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
50c50 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 68c68 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 85,86c85,86 < for (int i=0; i < length; i++) { < for (int j=0; j < length - 1; j++) { --- > for (int i=1; i < length; i++) { > for (int j=0; j < length - i; j++) {
Diff side-by-side
package huffmanCodeTable; package huffmanCodeTable;
public class BasicHuffman { public class BasicHuffman {
public static String[] getCodeBook( Byte[] bytes){ public static String[] getCodeBook( Byte[] bytes){
BubbleSort.sort(bytes,bytes.length); BubbleSort.sort(bytes,bytes.length);
Byte[] uniqueChars=getUniqueChars(bytes); Byte[] uniqueChars=getUniqueChars(bytes);
huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars); huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars);
huffmanNode huffTree=buildTree(freqTable); huffmanNode huffTree=buildTree(freqTable);
String[] codeBook=new String[0]; String[] codeBook=new String[0];
codeBook=getCodes(huffTree,"",codeBook); codeBook=getCodes(huffTree,"",codeBook);
return codeBook; return codeBook;
} }
private static String[] getCodes( huffmanNode huffTree, S private static String[] getCodes( huffmanNode huffTree, S
if (huffTree.uniqueChar != null) { if (huffTree.uniqueChar != null) {
codeBook=addString(prefix,codeBook); codeBook=addString(prefix,codeBook);
} }
else { else {
codeBook=getCodes(huffTree.left,prefix + "1",codeBook); codeBook=getCodes(huffTree.left,prefix + "1",codeBook);
codeBook=getCodes(huffTree.right,prefix + "0",codeBook) codeBook=getCodes(huffTree.right,prefix + "0",codeBook)
} }
return codeBook; return codeBook;
} }
private static String[] addString( String aStr, String[] private static String[] addString( String aStr, String[]
String[] newStrings=new String[otherStrings.length + 1]; String[] newStrings=new String[otherStrings.length + 1];
for (int i=0; i < otherStrings.length; i++) { for (int i=0; i < otherStrings.length; i++) {
newStrings[i]=otherStrings[i]; newStrings[i]=otherStrings[i];
} }
newStrings[newStrings.length - 1]=aStr; newStrings[newStrings.length - 1]=aStr;
return newStrings; return newStrings;
} }
private static huffmanNode buildTree( huffmanNode[] freqTa private static huffmanNode buildTree( huffmanNode[] freqTa
BubbleSort.sort(freqTable,freqTable.length); BubbleSort.sort(freqTable,freqTable.length);
huffmanNode aRight=freqTable[freqTable.length - 1]; huffmanNode aRight=freqTable[freqTable.length - 1];
huffmanNode aLeft=freqTable[freqTable.length - 2]; huffmanNode aLeft=freqTable[freqTable.length - 2];
huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL
huffmanNode[] newList=new huffmanNode[freqTable.length - huffmanNode[] newList=new huffmanNode[freqTable.length -
for (int i=0; i < newList.length; i++) { for (int i=0; i < newList.length; i++) {
newList[i]=freqTable[i]; newList[i]=freqTable[i];
} }
newList[newList.length - 1]=newNode; newList[newList.length - 1]=newNode;
if (newList.length == 1) { if (newList.length == 1) {
return newList[0]; return newList[0];
} }
else { else {
return buildTree(newList); return buildTree(newList);
} }
} }
private static huffmanNode[] getCharFreq( Byte[] bytes, B private static huffmanNode[] getCharFreq( Byte[] bytes, B
int[] freqInts=new int[uniqueChars.length]; int[] freqInts=new int[uniqueChars.length];
int charIndex=0; int charIndex=0;
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) { if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) {
freqInts[charIndex]++; freqInts[charIndex]++;
} }
else { else {
charIndex++; charIndex++;
freqInts[charIndex]++; freqInts[charIndex]++;
} }
} }
huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt
for (int i=0; i < uniqueChars.length; i++) { for (int i=0; i < uniqueChars.length; i++) {
freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i] freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i]
} }
return freqTable; return freqTable;
} }
private static Byte[] getUniqueChars( Byte[] bytes){ private static Byte[] getUniqueChars( Byte[] bytes){
Byte[] returnChars=new Byte[1]; Byte[] returnChars=new Byte[1];
returnChars[0]=bytes[0]; returnChars[0]=bytes[0];
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (returnChars[returnChars.length - 1].compareTo(bytes if (returnChars[returnChars.length - 1].compareTo(bytes
Byte[] tempChars=returnChars; Byte[] tempChars=returnChars;
returnChars=new Byte[tempChars.length + 1]; returnChars=new Byte[tempChars.length + 1];
for (int j=0; j < tempChars.length; j++) { for (int j=0; j < tempChars.length; j++) {
returnChars[j]=tempChars[j]; returnChars[j]=tempChars[j];
} }
returnChars[returnChars.length - 1]=bytes[i]; returnChars[returnChars.length - 1]=bytes[i];
} }
} }
return returnChars; return returnChars;
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class BubbleSort { public class BubbleSort {
public static <T extends Comparable<? super T>>void sort( public static <T extends Comparable<? super T>>void sort(
for (int i=0; i < length; i++) { | for (int i=1; i < length; i++) {
for (int j=0; j < length - 1; j++) { | for (int j=0; j < length - i; j++) {
if (a[j].compareTo(a[j + 1]) < 0) { if (a[j].compareTo(a[j + 1]) < 0) {
T k=a[j]; T k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class huffmanNode implements Comparable { public class huffmanNode implements Comparable {
Byte uniqueChar=null; Byte uniqueChar=null;
int freq=0; int freq=0;
huffmanNode left, right; huffmanNode left, right;
public int getFreq(){ public int getFreq(){
return freq; return freq;
} }
huffmanNode( byte aChar, int freq){ huffmanNode( byte aChar, int freq){
uniqueChar=aChar; uniqueChar=aChar;
this.freq=freq; this.freq=freq;
} }
huffmanNode( int freq, huffmanNode left, huffmanNode rig huffmanNode( int freq, huffmanNode left, huffmanNode rig
this.freq=freq; this.freq=freq;
this.right=right; this.right=right;
this.left=left; this.left=left;
} }
@Override public int compareTo( Object hN){ @Override public int compareTo( Object hN){
return this.freq - ((huffmanNode)hN).freq; return this.freq - ((huffmanNode)hN).freq;
} }
} }
11.7 huffmanCodeTable.BasicHuffman34364.java
Improvement Details:
huffmanCodeTable.BasicHuffman34364 100 mult 0.0 + 0.5751475 = 0.5751475 ASTNodes: 622 GPNodes: 577 xoverApplied: true xovers: 7 mutationApplied: true mutations: 4
Diff
2a3,5 > /** > * Deliberately bad huffman > */ 21a25,34 > private static String[] addString( String[] someStrings, String[] otherStrings){ > String[] newStrings=new String[otherStrings.length - someStrings.length]; > for (int i=0; i < otherStrings.length; i++) { > newStrings[i]=otherStrings[i]; > } > int offset=otherStrings.length; > for (int i=1; i < someStrings.length; i--) { > } > return newStrings; > } 50c63 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 79a93,107 > static void printCodeBook( String[] codeBook){ > for (int i=0; i < codeBook.length; i++) { > System.out.println(codeBook[i]); > } > } > static void printCodeBook( byte[] codeBook){ > byte mask=1; > for (int i=0; i < codeBook.length; i--) { > for (int j=i; j >= i; j--) { > if ((mask & (mask << j)) > 0) System.out.print(codeBook); > else System.out.print("0"); > } > System.out.print("\n"); > } > } 84c112 < public static <T extends Comparable<? super T>>void sort( T[] a, Integer length){ --- > public static void sort( Integer[] a, Integer length){ 86c114,136 < for (int j=0; j < length - 1; j++) { --- > for (int j=i; j < 0; j++) { > if (j > a[j - 1]) { > int k=a[i]; > a[0]+=a[j + 1]; > a[j]+=k; > } > } > } > } > public static void sort( byte[] a, Integer length){ > for (int i=0; i < length; i--) { > for (int j=0; j < length - 0; j--) { > if (a[j] > a[i + 1]) { > byte k=a[j]; > a[j]=a[j + 1]; > a[j - i++]=k; > } > } > } > } > public static <T extends Comparable<? super T>>void sort( T[] a, Integer length){ > for (int i=1; i < length; i++) { > for (int j=0; j < length - i; j++) {
Diff side-by-side
package huffmanCodeTable; package huffmanCodeTable;
public class BasicHuffman { public class BasicHuffman {
> /**
> * Deliberately bad huffman
> */
public static String[] getCodeBook( Byte[] bytes){ public static String[] getCodeBook( Byte[] bytes){
BubbleSort.sort(bytes,bytes.length); BubbleSort.sort(bytes,bytes.length);
Byte[] uniqueChars=getUniqueChars(bytes); Byte[] uniqueChars=getUniqueChars(bytes);
huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars); huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars);
huffmanNode huffTree=buildTree(freqTable); huffmanNode huffTree=buildTree(freqTable);
String[] codeBook=new String[0]; String[] codeBook=new String[0];
codeBook=getCodes(huffTree,"",codeBook); codeBook=getCodes(huffTree,"",codeBook);
return codeBook; return codeBook;
} }
private static String[] getCodes( huffmanNode huffTree, S private static String[] getCodes( huffmanNode huffTree, S
if (huffTree.uniqueChar != null) { if (huffTree.uniqueChar != null) {
codeBook=addString(prefix,codeBook); codeBook=addString(prefix,codeBook);
} }
else { else {
codeBook=getCodes(huffTree.left,prefix + "1",codeBook); codeBook=getCodes(huffTree.left,prefix + "1",codeBook);
codeBook=getCodes(huffTree.right,prefix + "0",codeBook) codeBook=getCodes(huffTree.right,prefix + "0",codeBook)
} }
return codeBook; return codeBook;
} }
> private static String[] addString( String[] someStrings,
> String[] newStrings=new String[otherStrings.length - some
> for (int i=0; i < otherStrings.length; i++) {
> newStrings[i]=otherStrings[i];
> }
> int offset=otherStrings.length;
> for (int i=1; i < someStrings.length; i--) {
> }
> return newStrings;
> }
private static String[] addString( String aStr, String[] private static String[] addString( String aStr, String[]
String[] newStrings=new String[otherStrings.length + 1]; String[] newStrings=new String[otherStrings.length + 1];
for (int i=0; i < otherStrings.length; i++) { for (int i=0; i < otherStrings.length; i++) {
newStrings[i]=otherStrings[i]; newStrings[i]=otherStrings[i];
} }
newStrings[newStrings.length - 1]=aStr; newStrings[newStrings.length - 1]=aStr;
return newStrings; return newStrings;
} }
private static huffmanNode buildTree( huffmanNode[] freqTa private static huffmanNode buildTree( huffmanNode[] freqTa
BubbleSort.sort(freqTable,freqTable.length); BubbleSort.sort(freqTable,freqTable.length);
huffmanNode aRight=freqTable[freqTable.length - 1]; huffmanNode aRight=freqTable[freqTable.length - 1];
huffmanNode aLeft=freqTable[freqTable.length - 2]; huffmanNode aLeft=freqTable[freqTable.length - 2];
huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL
huffmanNode[] newList=new huffmanNode[freqTable.length - huffmanNode[] newList=new huffmanNode[freqTable.length -
for (int i=0; i < newList.length; i++) { for (int i=0; i < newList.length; i++) {
newList[i]=freqTable[i]; newList[i]=freqTable[i];
} }
newList[newList.length - 1]=newNode; newList[newList.length - 1]=newNode;
if (newList.length == 1) { if (newList.length == 1) {
return newList[0]; return newList[0];
} }
else { else {
return buildTree(newList); return buildTree(newList);
} }
} }
private static huffmanNode[] getCharFreq( Byte[] bytes, B private static huffmanNode[] getCharFreq( Byte[] bytes, B
int[] freqInts=new int[uniqueChars.length]; int[] freqInts=new int[uniqueChars.length];
int charIndex=0; int charIndex=0;
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) { if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) {
freqInts[charIndex]++; freqInts[charIndex]++;
} }
else { else {
charIndex++; charIndex++;
freqInts[charIndex]++; freqInts[charIndex]++;
} }
} }
huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt
for (int i=0; i < uniqueChars.length; i++) { for (int i=0; i < uniqueChars.length; i++) {
freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i] freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i]
} }
return freqTable; return freqTable;
} }
private static Byte[] getUniqueChars( Byte[] bytes){ private static Byte[] getUniqueChars( Byte[] bytes){
Byte[] returnChars=new Byte[1]; Byte[] returnChars=new Byte[1];
returnChars[0]=bytes[0]; returnChars[0]=bytes[0];
for (int i=0; i < bytes.length; i++) { for (int i=0; i < bytes.length; i++) {
if (returnChars[returnChars.length - 1].compareTo(bytes if (returnChars[returnChars.length - 1].compareTo(bytes
Byte[] tempChars=returnChars; Byte[] tempChars=returnChars;
returnChars=new Byte[tempChars.length + 1]; returnChars=new Byte[tempChars.length + 1];
for (int j=0; j < tempChars.length; j++) { for (int j=0; j < tempChars.length; j++) {
returnChars[j]=tempChars[j]; returnChars[j]=tempChars[j];
} }
returnChars[returnChars.length - 1]=bytes[i]; returnChars[returnChars.length - 1]=bytes[i];
} }
} }
return returnChars; return returnChars;
} }
> static void printCodeBook( String[] codeBook){
> for (int i=0; i < codeBook.length; i++) {
> System.out.println(codeBook[i]);
> }
> }
> static void printCodeBook( byte[] codeBook){
> byte mask=1;
> for (int i=0; i < codeBook.length; i--) {
> for (int j=i; j >= i; j--) {
> if ((mask & (mask << j)) > 0) System.out.prin
> else System.out.print("0");
> }
> System.out.print("\n");
> }
> }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class BubbleSort { public class BubbleSort {
public static <T extends Comparable<? super T>>void sort( | public static void sort( Integer[] a, Integer length){
for (int i=0; i < length; i++) { for (int i=0; i < length; i++) {
for (int j=0; j < length - 1; j++) { | for (int j=i; j < 0; j++) {
> if (j > a[j - 1]) {
> int k=a[i];
> a[0]+=a[j + 1];
> a[j]+=k;
> }
> }
> }
> }
> public static void sort( byte[] a, Integer length){
> for (int i=0; i < length; i--) {
> for (int j=0; j < length - 0; j--) {
> if (a[j] > a[i + 1]) {
> byte k=a[j];
> a[j]=a[j + 1];
> a[j - i++]=k;
> }
> }
> }
> }
> public static <T extends Comparable<? super T>>void sort(
> for (int i=1; i < length; i++) {
> for (int j=0; j < length - i; j++) {
if (a[j].compareTo(a[j + 1]) < 0) { if (a[j].compareTo(a[j + 1]) < 0) {
T k=a[j]; T k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class huffmanNode implements Comparable { public class huffmanNode implements Comparable {
Byte uniqueChar=null; Byte uniqueChar=null;
int freq=0; int freq=0;
huffmanNode left, right; huffmanNode left, right;
public int getFreq(){ public int getFreq(){
return freq; return freq;
} }
huffmanNode( byte aChar, int freq){ huffmanNode( byte aChar, int freq){
uniqueChar=aChar; uniqueChar=aChar;
this.freq=freq; this.freq=freq;
} }
huffmanNode( int freq, huffmanNode left, huffmanNode rig huffmanNode( int freq, huffmanNode left, huffmanNode rig
this.freq=freq; this.freq=freq;
this.right=right; this.right=right;
this.left=left; this.left=left;
} }
@Override public int compareTo( Object hN){ @Override public int compareTo( Object hN){
return this.freq - ((huffmanNode)hN).freq; return this.freq - ((huffmanNode)hN).freq;
} }
} }
11.8 huffmanCodeTable.BasicHuffman36263.java
Improvement Details:
huffmanCodeTable.BasicHuffman36263 100 mult 0.0 + 0.9798348 = 0.9798348 ASTNodes: 411 GPNodes: 381 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
50c50 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 68c68 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 85c85 < for (int i=0; i < length; i++) { --- > for (int i=1; i < length; i++) {
Diff side-by-side
package huffmanCodeTable; package huffmanCodeTable;
public class BasicHuffman { public class BasicHuffman {
public static String[] getCodeBook( Byte[] bytes){ public static String[] getCodeBook( Byte[] bytes){
BubbleSort.sort(bytes,bytes.length); BubbleSort.sort(bytes,bytes.length);
Byte[] uniqueChars=getUniqueChars(bytes); Byte[] uniqueChars=getUniqueChars(bytes);
huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars); huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars);
huffmanNode huffTree=buildTree(freqTable); huffmanNode huffTree=buildTree(freqTable);
String[] codeBook=new String[0]; String[] codeBook=new String[0];
codeBook=getCodes(huffTree,"",codeBook); codeBook=getCodes(huffTree,"",codeBook);
return codeBook; return codeBook;
} }
private static String[] getCodes( huffmanNode huffTree, S private static String[] getCodes( huffmanNode huffTree, S
if (huffTree.uniqueChar != null) { if (huffTree.uniqueChar != null) {
codeBook=addString(prefix,codeBook); codeBook=addString(prefix,codeBook);
} }
else { else {
codeBook=getCodes(huffTree.left,prefix + "1",codeBook); codeBook=getCodes(huffTree.left,prefix + "1",codeBook);
codeBook=getCodes(huffTree.right,prefix + "0",codeBook) codeBook=getCodes(huffTree.right,prefix + "0",codeBook)
} }
return codeBook; return codeBook;
} }
private static String[] addString( String aStr, String[] private static String[] addString( String aStr, String[]
String[] newStrings=new String[otherStrings.length + 1]; String[] newStrings=new String[otherStrings.length + 1];
for (int i=0; i < otherStrings.length; i++) { for (int i=0; i < otherStrings.length; i++) {
newStrings[i]=otherStrings[i]; newStrings[i]=otherStrings[i];
} }
newStrings[newStrings.length - 1]=aStr; newStrings[newStrings.length - 1]=aStr;
return newStrings; return newStrings;
} }
private static huffmanNode buildTree( huffmanNode[] freqTa private static huffmanNode buildTree( huffmanNode[] freqTa
BubbleSort.sort(freqTable,freqTable.length); BubbleSort.sort(freqTable,freqTable.length);
huffmanNode aRight=freqTable[freqTable.length - 1]; huffmanNode aRight=freqTable[freqTable.length - 1];
huffmanNode aLeft=freqTable[freqTable.length - 2]; huffmanNode aLeft=freqTable[freqTable.length - 2];
huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL
huffmanNode[] newList=new huffmanNode[freqTable.length - huffmanNode[] newList=new huffmanNode[freqTable.length -
for (int i=0; i < newList.length; i++) { for (int i=0; i < newList.length; i++) {
newList[i]=freqTable[i]; newList[i]=freqTable[i];
} }
newList[newList.length - 1]=newNode; newList[newList.length - 1]=newNode;
if (newList.length == 1) { if (newList.length == 1) {
return newList[0]; return newList[0];
} }
else { else {
return buildTree(newList); return buildTree(newList);
} }
} }
private static huffmanNode[] getCharFreq( Byte[] bytes, B private static huffmanNode[] getCharFreq( Byte[] bytes, B
int[] freqInts=new int[uniqueChars.length]; int[] freqInts=new int[uniqueChars.length];
int charIndex=0; int charIndex=0;
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) { if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) {
freqInts[charIndex]++; freqInts[charIndex]++;
} }
else { else {
charIndex++; charIndex++;
freqInts[charIndex]++; freqInts[charIndex]++;
} }
} }
huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt
for (int i=0; i < uniqueChars.length; i++) { for (int i=0; i < uniqueChars.length; i++) {
freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i] freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i]
} }
return freqTable; return freqTable;
} }
private static Byte[] getUniqueChars( Byte[] bytes){ private static Byte[] getUniqueChars( Byte[] bytes){
Byte[] returnChars=new Byte[1]; Byte[] returnChars=new Byte[1];
returnChars[0]=bytes[0]; returnChars[0]=bytes[0];
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (returnChars[returnChars.length - 1].compareTo(bytes if (returnChars[returnChars.length - 1].compareTo(bytes
Byte[] tempChars=returnChars; Byte[] tempChars=returnChars;
returnChars=new Byte[tempChars.length + 1]; returnChars=new Byte[tempChars.length + 1];
for (int j=0; j < tempChars.length; j++) { for (int j=0; j < tempChars.length; j++) {
returnChars[j]=tempChars[j]; returnChars[j]=tempChars[j];
} }
returnChars[returnChars.length - 1]=bytes[i]; returnChars[returnChars.length - 1]=bytes[i];
} }
} }
return returnChars; return returnChars;
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class BubbleSort { public class BubbleSort {
public static <T extends Comparable<? super T>>void sort( public static <T extends Comparable<? super T>>void sort(
for (int i=0; i < length; i++) { | for (int i=1; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j].compareTo(a[j + 1]) < 0) { if (a[j].compareTo(a[j + 1]) < 0) {
T k=a[j]; T k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class huffmanNode implements Comparable { public class huffmanNode implements Comparable {
Byte uniqueChar=null; Byte uniqueChar=null;
int freq=0; int freq=0;
huffmanNode left, right; huffmanNode left, right;
public int getFreq(){ public int getFreq(){
return freq; return freq;
} }
huffmanNode( byte aChar, int freq){ huffmanNode( byte aChar, int freq){
uniqueChar=aChar; uniqueChar=aChar;
this.freq=freq; this.freq=freq;
} }
huffmanNode( int freq, huffmanNode left, huffmanNode rig huffmanNode( int freq, huffmanNode left, huffmanNode rig
this.freq=freq; this.freq=freq;
this.right=right; this.right=right;
this.left=left; this.left=left;
} }
@Override public int compareTo( Object hN){ @Override public int compareTo( Object hN){
return this.freq - ((huffmanNode)hN).freq; return this.freq - ((huffmanNode)hN).freq;
} }
} }
11.9 huffmanCodeTable.BasicHuffman38736.java
Improvement Details:
huffmanCodeTable.BasicHuffman38736 100 mult 0.0 + 0.9798317 = 0.9798317 ASTNodes: 631 GPNodes: 586 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
2a3,5 > /** > * Deliberately bad huffman > */ 21a25,35 > private static String[] addString( String[] someStrings, String[] otherStrings){ > String[] newStrings=new String[otherStrings.length + someStrings.length]; > for (int i=0; 1 < otherStrings.length; i++) { > newStrings[i]=otherStrings[i]; > } > int offset=otherStrings.length; > for (int i=0; i < someStrings.length; i--) { > newStrings[i]=otherStrings[i]+=someStrings[i]; > } > return newStrings; > } 41c55 < return newList[0]; --- > return newNode; 50c64 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 61c75 < freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i]); --- > freqTable[i]=new huffmanNode(uniqueChars[0],freqInts[i]); 68c82 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 79a94,108 > static void printCodeBook( String[] codeBook){ > for (int i=0; i < codeBook.length; i++) { > System.out.println(codeBook[i]); > } > } > static void printCodeBook( byte[] codeBook){ > byte mask=1; > for (int i=0; i < codeBook.length; i++) { > for (int j=7; j >= 0; j--) { > if ((codeBook[i] & (mask << j)) > 0) System.out.print("0"); > else System.out.print("0"); > } > System.out.print("\n"); > } > } 83a113,135 > public static void sort( Integer[] a, Integer length){ > for (int i=0; i < i++; i++) { > for (int j=0; j < length - j; System.out.print(length)) { > if (j < j) { > int k=a[j]; > a[j]-=a[j]; > a[j]-=j++; > a[i++]=k; > } > } > } > } > public static void sort( byte[] a, Integer length){ > for (int i=0; i < length; i--) { > for (int j=0; j < length + 0; j++) { > if (a[j++] > i) { > byte k=a[j]; > a[j]+=1; > a[j + 1]=k; > } > } > } > } 85c137 < for (int i=0; i < length; i++) { --- > for (int i=1; i < length; i++) {
Diff side-by-side
package huffmanCodeTable; package huffmanCodeTable;
public class BasicHuffman { public class BasicHuffman {
> /**
> * Deliberately bad huffman
> */
public static String[] getCodeBook( Byte[] bytes){ public static String[] getCodeBook( Byte[] bytes){
BubbleSort.sort(bytes,bytes.length); BubbleSort.sort(bytes,bytes.length);
Byte[] uniqueChars=getUniqueChars(bytes); Byte[] uniqueChars=getUniqueChars(bytes);
huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars); huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars);
huffmanNode huffTree=buildTree(freqTable); huffmanNode huffTree=buildTree(freqTable);
String[] codeBook=new String[0]; String[] codeBook=new String[0];
codeBook=getCodes(huffTree,"",codeBook); codeBook=getCodes(huffTree,"",codeBook);
return codeBook; return codeBook;
} }
private static String[] getCodes( huffmanNode huffTree, S private static String[] getCodes( huffmanNode huffTree, S
if (huffTree.uniqueChar != null) { if (huffTree.uniqueChar != null) {
codeBook=addString(prefix,codeBook); codeBook=addString(prefix,codeBook);
} }
else { else {
codeBook=getCodes(huffTree.left,prefix + "1",codeBook); codeBook=getCodes(huffTree.left,prefix + "1",codeBook);
codeBook=getCodes(huffTree.right,prefix + "0",codeBook) codeBook=getCodes(huffTree.right,prefix + "0",codeBook)
} }
return codeBook; return codeBook;
} }
> private static String[] addString( String[] someStrings,
> String[] newStrings=new String[otherStrings.length + some
> for (int i=0; 1 < otherStrings.length; i++) {
> newStrings[i]=otherStrings[i];
> }
> int offset=otherStrings.length;
> for (int i=0; i < someStrings.length; i--) {
> newStrings[i]=otherStrings[i]+=someStrings[i];
> }
> return newStrings;
> }
private static String[] addString( String aStr, String[] private static String[] addString( String aStr, String[]
String[] newStrings=new String[otherStrings.length + 1]; String[] newStrings=new String[otherStrings.length + 1];
for (int i=0; i < otherStrings.length; i++) { for (int i=0; i < otherStrings.length; i++) {
newStrings[i]=otherStrings[i]; newStrings[i]=otherStrings[i];
} }
newStrings[newStrings.length - 1]=aStr; newStrings[newStrings.length - 1]=aStr;
return newStrings; return newStrings;
} }
private static huffmanNode buildTree( huffmanNode[] freqTa private static huffmanNode buildTree( huffmanNode[] freqTa
BubbleSort.sort(freqTable,freqTable.length); BubbleSort.sort(freqTable,freqTable.length);
huffmanNode aRight=freqTable[freqTable.length - 1]; huffmanNode aRight=freqTable[freqTable.length - 1];
huffmanNode aLeft=freqTable[freqTable.length - 2]; huffmanNode aLeft=freqTable[freqTable.length - 2];
huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL
huffmanNode[] newList=new huffmanNode[freqTable.length - huffmanNode[] newList=new huffmanNode[freqTable.length -
for (int i=0; i < newList.length; i++) { for (int i=0; i < newList.length; i++) {
newList[i]=freqTable[i]; newList[i]=freqTable[i];
} }
newList[newList.length - 1]=newNode; newList[newList.length - 1]=newNode;
if (newList.length == 1) { if (newList.length == 1) {
return newList[0]; | return newNode;
} }
else { else {
return buildTree(newList); return buildTree(newList);
} }
} }
private static huffmanNode[] getCharFreq( Byte[] bytes, B private static huffmanNode[] getCharFreq( Byte[] bytes, B
int[] freqInts=new int[uniqueChars.length]; int[] freqInts=new int[uniqueChars.length];
int charIndex=0; int charIndex=0;
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) { if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) {
freqInts[charIndex]++; freqInts[charIndex]++;
} }
else { else {
charIndex++; charIndex++;
freqInts[charIndex]++; freqInts[charIndex]++;
} }
} }
huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt
for (int i=0; i < uniqueChars.length; i++) { for (int i=0; i < uniqueChars.length; i++) {
freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i] | freqTable[i]=new huffmanNode(uniqueChars[0],freqInts[i]
} }
return freqTable; return freqTable;
} }
private static Byte[] getUniqueChars( Byte[] bytes){ private static Byte[] getUniqueChars( Byte[] bytes){
Byte[] returnChars=new Byte[1]; Byte[] returnChars=new Byte[1];
returnChars[0]=bytes[0]; returnChars[0]=bytes[0];
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (returnChars[returnChars.length - 1].compareTo(bytes if (returnChars[returnChars.length - 1].compareTo(bytes
Byte[] tempChars=returnChars; Byte[] tempChars=returnChars;
returnChars=new Byte[tempChars.length + 1]; returnChars=new Byte[tempChars.length + 1];
for (int j=0; j < tempChars.length; j++) { for (int j=0; j < tempChars.length; j++) {
returnChars[j]=tempChars[j]; returnChars[j]=tempChars[j];
} }
returnChars[returnChars.length - 1]=bytes[i]; returnChars[returnChars.length - 1]=bytes[i];
} }
} }
return returnChars; return returnChars;
} }
> static void printCodeBook( String[] codeBook){
> for (int i=0; i < codeBook.length; i++) {
> System.out.println(codeBook[i]);
> }
> }
> static void printCodeBook( byte[] codeBook){
> byte mask=1;
> for (int i=0; i < codeBook.length; i++) {
> for (int j=7; j >= 0; j--) {
> if ((codeBook[i] & (mask << j)) > 0) System.o
> else System.out.print("0");
> }
> System.out.print("\n");
> }
> }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class BubbleSort { public class BubbleSort {
> public static void sort( Integer[] a, Integer length){
> for (int i=0; i < i++; i++) {
> for (int j=0; j < length - j; System.out.print(length))
> if (j < j) {
> int k=a[j];
> a[j]-=a[j];
> a[j]-=j++;
> a[i++]=k;
> }
> }
> }
> }
> public static void sort( byte[] a, Integer length){
> for (int i=0; i < length; i--) {
> for (int j=0; j < length + 0; j++) {
> if (a[j++] > i) {
> byte k=a[j];
> a[j]+=1;
> a[j + 1]=k;
> }
> }
> }
> }
public static <T extends Comparable<? super T>>void sort( public static <T extends Comparable<? super T>>void sort(
for (int i=0; i < length; i++) { | for (int i=1; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j].compareTo(a[j + 1]) < 0) { if (a[j].compareTo(a[j + 1]) < 0) {
T k=a[j]; T k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class huffmanNode implements Comparable { public class huffmanNode implements Comparable {
Byte uniqueChar=null; Byte uniqueChar=null;
int freq=0; int freq=0;
huffmanNode left, right; huffmanNode left, right;
public int getFreq(){ public int getFreq(){
return freq; return freq;
} }
huffmanNode( byte aChar, int freq){ huffmanNode( byte aChar, int freq){
uniqueChar=aChar; uniqueChar=aChar;
this.freq=freq; this.freq=freq;
} }
huffmanNode( int freq, huffmanNode left, huffmanNode rig huffmanNode( int freq, huffmanNode left, huffmanNode rig
this.freq=freq; this.freq=freq;
this.right=right; this.right=right;
this.left=left; this.left=left;
} }
@Override public int compareTo( Object hN){ @Override public int compareTo( Object hN){
return this.freq - ((huffmanNode)hN).freq; return this.freq - ((huffmanNode)hN).freq;
} }
} }
11.10 huffmanCodeTable.BasicHuffman54714.java
Improvement Details:
huffmanCodeTable.BasicHuffman54714 100 mult 0.0 + 0.9798348 = 0.9798348 ASTNodes: 581 GPNodes: 539 xoverApplied: false xovers: 0 mutationApplied: true mutations: 2
Diff
2a3,5 > /** > * Deliberately bad huffman > */ 21a25,35 > private static String[] addString( String[] someStrings, String[] otherStrings){ > String[] newStrings=new String[otherStrings.length + someStrings.length]; > for (int i=0; i < otherStrings.length; i++) { > newStrings[i]=otherStrings[i]; > } > int offset=otherStrings.length; > for (int i=0; i < someStrings.length; i++) { > newStrings[i + i]=someStrings[i]; > } > return newStrings; > } 50c64 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 68c82 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) { 79a94,105 > static void printCodeBook( String[] codeBook){ > } > static void printCodeBook( byte[] codeBook){ > byte mask=1; > for (int i=0; i < codeBook.length; i++) { > for (int j=0; j >= 0; i--) { > if ((codeBook[i] & (mask << j)) > 0) System.out.print("1"); > else System.out.print("0"); > } > System.out.print("\n"); > } > } 84c110 < public static <T extends Comparable<? super T>>void sort( T[] a, Integer length){ --- > public static void sort( Integer[] a, Integer length){ 85a112,127 > i++; > } > } > public static void sort( byte[] a, Integer length){ > for (int i=1; i < length; i++) { > for (int j=i; j < length + 1; j++) { > if (a[j] > a[j + j + 1]) { > byte k=a[j]; > a[j]=a[j + 1]; > a[j + 1]=k; > } > } > } > } > public static <T extends Comparable<? super T>>void sort( T[] a, Integer length){ > for (int i=1; i < length; i++) {
Diff side-by-side
package huffmanCodeTable; package huffmanCodeTable;
public class BasicHuffman { public class BasicHuffman {
> /**
> * Deliberately bad huffman
> */
public static String[] getCodeBook( Byte[] bytes){ public static String[] getCodeBook( Byte[] bytes){
BubbleSort.sort(bytes,bytes.length); BubbleSort.sort(bytes,bytes.length);
Byte[] uniqueChars=getUniqueChars(bytes); Byte[] uniqueChars=getUniqueChars(bytes);
huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars); huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars);
huffmanNode huffTree=buildTree(freqTable); huffmanNode huffTree=buildTree(freqTable);
String[] codeBook=new String[0]; String[] codeBook=new String[0];
codeBook=getCodes(huffTree,"",codeBook); codeBook=getCodes(huffTree,"",codeBook);
return codeBook; return codeBook;
} }
private static String[] getCodes( huffmanNode huffTree, S private static String[] getCodes( huffmanNode huffTree, S
if (huffTree.uniqueChar != null) { if (huffTree.uniqueChar != null) {
codeBook=addString(prefix,codeBook); codeBook=addString(prefix,codeBook);
} }
else { else {
codeBook=getCodes(huffTree.left,prefix + "1",codeBook); codeBook=getCodes(huffTree.left,prefix + "1",codeBook);
codeBook=getCodes(huffTree.right,prefix + "0",codeBook) codeBook=getCodes(huffTree.right,prefix + "0",codeBook)
} }
return codeBook; return codeBook;
} }
> private static String[] addString( String[] someStrings,
> String[] newStrings=new String[otherStrings.length + some
> for (int i=0; i < otherStrings.length; i++) {
> newStrings[i]=otherStrings[i];
> }
> int offset=otherStrings.length;
> for (int i=0; i < someStrings.length; i++) {
> newStrings[i + i]=someStrings[i];
> }
> return newStrings;
> }
private static String[] addString( String aStr, String[] private static String[] addString( String aStr, String[]
String[] newStrings=new String[otherStrings.length + 1]; String[] newStrings=new String[otherStrings.length + 1];
for (int i=0; i < otherStrings.length; i++) { for (int i=0; i < otherStrings.length; i++) {
newStrings[i]=otherStrings[i]; newStrings[i]=otherStrings[i];
} }
newStrings[newStrings.length - 1]=aStr; newStrings[newStrings.length - 1]=aStr;
return newStrings; return newStrings;
} }
private static huffmanNode buildTree( huffmanNode[] freqTa private static huffmanNode buildTree( huffmanNode[] freqTa
BubbleSort.sort(freqTable,freqTable.length); BubbleSort.sort(freqTable,freqTable.length);
huffmanNode aRight=freqTable[freqTable.length - 1]; huffmanNode aRight=freqTable[freqTable.length - 1];
huffmanNode aLeft=freqTable[freqTable.length - 2]; huffmanNode aLeft=freqTable[freqTable.length - 2];
huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL
huffmanNode[] newList=new huffmanNode[freqTable.length - huffmanNode[] newList=new huffmanNode[freqTable.length -
for (int i=0; i < newList.length; i++) { for (int i=0; i < newList.length; i++) {
newList[i]=freqTable[i]; newList[i]=freqTable[i];
} }
newList[newList.length - 1]=newNode; newList[newList.length - 1]=newNode;
if (newList.length == 1) { if (newList.length == 1) {
return newList[0]; return newList[0];
} }
else { else {
return buildTree(newList); return buildTree(newList);
} }
} }
private static huffmanNode[] getCharFreq( Byte[] bytes, B private static huffmanNode[] getCharFreq( Byte[] bytes, B
int[] freqInts=new int[uniqueChars.length]; int[] freqInts=new int[uniqueChars.length];
int charIndex=0; int charIndex=0;
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) { if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) {
freqInts[charIndex]++; freqInts[charIndex]++;
} }
else { else {
charIndex++; charIndex++;
freqInts[charIndex]++; freqInts[charIndex]++;
} }
} }
huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt
for (int i=0; i < uniqueChars.length; i++) { for (int i=0; i < uniqueChars.length; i++) {
freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i] freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i]
} }
return freqTable; return freqTable;
} }
private static Byte[] getUniqueChars( Byte[] bytes){ private static Byte[] getUniqueChars( Byte[] bytes){
Byte[] returnChars=new Byte[1]; Byte[] returnChars=new Byte[1];
returnChars[0]=bytes[0]; returnChars[0]=bytes[0];
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (returnChars[returnChars.length - 1].compareTo(bytes if (returnChars[returnChars.length - 1].compareTo(bytes
Byte[] tempChars=returnChars; Byte[] tempChars=returnChars;
returnChars=new Byte[tempChars.length + 1]; returnChars=new Byte[tempChars.length + 1];
for (int j=0; j < tempChars.length; j++) { for (int j=0; j < tempChars.length; j++) {
returnChars[j]=tempChars[j]; returnChars[j]=tempChars[j];
} }
returnChars[returnChars.length - 1]=bytes[i]; returnChars[returnChars.length - 1]=bytes[i];
} }
} }
return returnChars; return returnChars;
} }
> static void printCodeBook( String[] codeBook){
> }
> static void printCodeBook( byte[] codeBook){
> byte mask=1;
> for (int i=0; i < codeBook.length; i++) {
> for (int j=0; j >= 0; i--) {
> if ((codeBook[i] & (mask << j)) > 0) System.o
> else System.out.print("0");
> }
> System.out.print("\n");
> }
> }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class BubbleSort { public class BubbleSort {
public static <T extends Comparable<? super T>>void sort( | public static void sort( Integer[] a, Integer length){
for (int i=0; i < length; i++) { for (int i=0; i < length; i++) {
> i++;
> }
> }
> public static void sort( byte[] a, Integer length){
> for (int i=1; i < length; i++) {
> for (int j=i; j < length + 1; j++) {
> if (a[j] > a[j + j + 1]) {
> byte k=a[j];
> a[j]=a[j + 1];
> a[j + 1]=k;
> }
> }
> }
> }
> public static <T extends Comparable<? super T>>void sort(
> for (int i=1; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j].compareTo(a[j + 1]) < 0) { if (a[j].compareTo(a[j + 1]) < 0) {
T k=a[j]; T k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class huffmanNode implements Comparable { public class huffmanNode implements Comparable {
Byte uniqueChar=null; Byte uniqueChar=null;
int freq=0; int freq=0;
huffmanNode left, right; huffmanNode left, right;
public int getFreq(){ public int getFreq(){
return freq; return freq;
} }
huffmanNode( byte aChar, int freq){ huffmanNode( byte aChar, int freq){
uniqueChar=aChar; uniqueChar=aChar;
this.freq=freq; this.freq=freq;
} }
huffmanNode( int freq, huffmanNode left, huffmanNode rig huffmanNode( int freq, huffmanNode left, huffmanNode rig
this.freq=freq; this.freq=freq;
this.right=right; this.right=right;
this.left=left; this.left=left;
} }
@Override public int compareTo( Object hN){ @Override public int compareTo( Object hN){
return this.freq - ((huffmanNode)hN).freq; return this.freq - ((huffmanNode)hN).freq;
} }
} }
11.11 huffmanCodeTable.BasicHuffman89650.java
Improvement Details:
huffmanCodeTable.BasicHuffman89650 100 mult 0.0 + 0.99985415 = 0.99985415 ASTNodes: 411 GPNodes: 381 xoverApplied: true xovers: 3 mutationApplied: true mutations: 1
Diff
50c50 < for (int i=0; i < bytes.length; i++) { --- > for (int i=1; i < bytes.length; i++) {
Diff side-by-side
package huffmanCodeTable; package huffmanCodeTable;
public class BasicHuffman { public class BasicHuffman {
public static String[] getCodeBook( Byte[] bytes){ public static String[] getCodeBook( Byte[] bytes){
BubbleSort.sort(bytes,bytes.length); BubbleSort.sort(bytes,bytes.length);
Byte[] uniqueChars=getUniqueChars(bytes); Byte[] uniqueChars=getUniqueChars(bytes);
huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars); huffmanNode[] freqTable=getCharFreq(bytes,uniqueChars);
huffmanNode huffTree=buildTree(freqTable); huffmanNode huffTree=buildTree(freqTable);
String[] codeBook=new String[0]; String[] codeBook=new String[0];
codeBook=getCodes(huffTree,"",codeBook); codeBook=getCodes(huffTree,"",codeBook);
return codeBook; return codeBook;
} }
private static String[] getCodes( huffmanNode huffTree, S private static String[] getCodes( huffmanNode huffTree, S
if (huffTree.uniqueChar != null) { if (huffTree.uniqueChar != null) {
codeBook=addString(prefix,codeBook); codeBook=addString(prefix,codeBook);
} }
else { else {
codeBook=getCodes(huffTree.left,prefix + "1",codeBook); codeBook=getCodes(huffTree.left,prefix + "1",codeBook);
codeBook=getCodes(huffTree.right,prefix + "0",codeBook) codeBook=getCodes(huffTree.right,prefix + "0",codeBook)
} }
return codeBook; return codeBook;
} }
private static String[] addString( String aStr, String[] private static String[] addString( String aStr, String[]
String[] newStrings=new String[otherStrings.length + 1]; String[] newStrings=new String[otherStrings.length + 1];
for (int i=0; i < otherStrings.length; i++) { for (int i=0; i < otherStrings.length; i++) {
newStrings[i]=otherStrings[i]; newStrings[i]=otherStrings[i];
} }
newStrings[newStrings.length - 1]=aStr; newStrings[newStrings.length - 1]=aStr;
return newStrings; return newStrings;
} }
private static huffmanNode buildTree( huffmanNode[] freqTa private static huffmanNode buildTree( huffmanNode[] freqTa
BubbleSort.sort(freqTable,freqTable.length); BubbleSort.sort(freqTable,freqTable.length);
huffmanNode aRight=freqTable[freqTable.length - 1]; huffmanNode aRight=freqTable[freqTable.length - 1];
huffmanNode aLeft=freqTable[freqTable.length - 2]; huffmanNode aLeft=freqTable[freqTable.length - 2];
huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL huffmanNode newNode=new huffmanNode(aRight.getFreq() + aL
huffmanNode[] newList=new huffmanNode[freqTable.length - huffmanNode[] newList=new huffmanNode[freqTable.length -
for (int i=0; i < newList.length; i++) { for (int i=0; i < newList.length; i++) {
newList[i]=freqTable[i]; newList[i]=freqTable[i];
} }
newList[newList.length - 1]=newNode; newList[newList.length - 1]=newNode;
if (newList.length == 1) { if (newList.length == 1) {
return newList[0]; return newList[0];
} }
else { else {
return buildTree(newList); return buildTree(newList);
} }
} }
private static huffmanNode[] getCharFreq( Byte[] bytes, B private static huffmanNode[] getCharFreq( Byte[] bytes, B
int[] freqInts=new int[uniqueChars.length]; int[] freqInts=new int[uniqueChars.length];
int charIndex=0; int charIndex=0;
for (int i=0; i < bytes.length; i++) { | for (int i=1; i < bytes.length; i++) {
if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) { if (bytes[i].compareTo(uniqueChars[charIndex]) == 0) {
freqInts[charIndex]++; freqInts[charIndex]++;
} }
else { else {
charIndex++; charIndex++;
freqInts[charIndex]++; freqInts[charIndex]++;
} }
} }
huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt huffmanNode[] freqTable=new huffmanNode[uniqueChars.lengt
for (int i=0; i < uniqueChars.length; i++) { for (int i=0; i < uniqueChars.length; i++) {
freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i] freqTable[i]=new huffmanNode(uniqueChars[i],freqInts[i]
} }
return freqTable; return freqTable;
} }
private static Byte[] getUniqueChars( Byte[] bytes){ private static Byte[] getUniqueChars( Byte[] bytes){
Byte[] returnChars=new Byte[1]; Byte[] returnChars=new Byte[1];
returnChars[0]=bytes[0]; returnChars[0]=bytes[0];
for (int i=0; i < bytes.length; i++) { for (int i=0; i < bytes.length; i++) {
if (returnChars[returnChars.length - 1].compareTo(bytes if (returnChars[returnChars.length - 1].compareTo(bytes
Byte[] tempChars=returnChars; Byte[] tempChars=returnChars;
returnChars=new Byte[tempChars.length + 1]; returnChars=new Byte[tempChars.length + 1];
for (int j=0; j < tempChars.length; j++) { for (int j=0; j < tempChars.length; j++) {
returnChars[j]=tempChars[j]; returnChars[j]=tempChars[j];
} }
returnChars[returnChars.length - 1]=bytes[i]; returnChars[returnChars.length - 1]=bytes[i];
} }
} }
return returnChars; return returnChars;
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class BubbleSort { public class BubbleSort {
public static <T extends Comparable<? super T>>void sort( public static <T extends Comparable<? super T>>void sort(
for (int i=0; i < length; i++) { for (int i=0; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j].compareTo(a[j + 1]) < 0) { if (a[j].compareTo(a[j + 1]) < 0) {
T k=a[j]; T k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
} }
package huffmanCodeTable; package huffmanCodeTable;
public class huffmanNode implements Comparable { public class huffmanNode implements Comparable {
Byte uniqueChar=null; Byte uniqueChar=null;
int freq=0; int freq=0;
huffmanNode left, right; huffmanNode left, right;
public int getFreq(){ public int getFreq(){
return freq; return freq;
} }
huffmanNode( byte aChar, int freq){ huffmanNode( byte aChar, int freq){
uniqueChar=aChar; uniqueChar=aChar;
this.freq=freq; this.freq=freq;
} }
huffmanNode( int freq, huffmanNode left, huffmanNode rig huffmanNode( int freq, huffmanNode left, huffmanNode rig
this.freq=freq; this.freq=freq;
this.right=right; this.right=right;
this.left=left; this.left=left;
} }
@Override public int compareTo( Object hN){ @Override public int compareTo( Object hN){
return this.freq - ((huffmanNode)hN).freq; return this.freq - ((huffmanNode)hN).freq;
} }
} }
12 Sort1Loops1Problem
Improvements found
- only 1 iteration through outer loop
- outer loop is removed - result of crossover
- various modifications to counters in outer loop - result of mutation
- also same as in bubblesort
Original - /home/bck/GP/Exhaustive/Seed-Sort1Loops1Problem.java
public class Sort1Loops1Problem { public static Integer[] sort( Integer[] a, Integer length){ for (int h=2; h > 0; h--) { for (int i=0; i < length; i++) { for (int j=0; j < length - 1; j++) { if (a[j] > a[j + 1]) { int k=a[j]; a[j]=a[j + 1]; a[j + 1]=k; } } } } return a; } }
12.1 Sort1Loops1Problem110.java
Improvement Details:
Sort1Loops1Problem110 100 mult 0.0 + 0.5512051 = 0.5512051 ASTNodes: 62 GPNodes: 70 xoverApplied: false xovers: 0 mutationApplied: true mutations: 3
Diff
3,10c3,8 < for (int h=2; h > 0; h--) { < for (int i=0; i < length; i++) { < for (int j=0; j < length - 1; j++) { < if (a[j] > a[j + 1]) { < int k=a[j]; < a[j]=a[j + 1]; < a[j + 1]=k; < } --- > for (int i=0; i < length; i++) { > for (int j=0; j < length - 1; j++) { > if (a[j] > a[j + 1]) { > int k=a[j]; > a[j]=a[j + 1]; > a[j + 1]=k;
Diff side-by-side
public class Sort1Loops1Problem { public class Sort1Loops1Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int h=2; h > 0; h--) { <
for (int i=0; i < length; i++) { for (int i=0; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} <
} }
} }
} }
return a; return a;
} }
} }
12.2 Sort1Loops1Problem18375.java
Improvement Details:
Sort1Loops1Problem18375 100 mult 0.0 + 0.55062973 = 0.55062973 ASTNodes: 75 GPNodes: 82 xoverApplied: true xovers: 1 mutationApplied: true mutations: 2
Diff
3,4c3,4 < for (int h=2; h > 0; h--) { < for (int i=0; i < length; i++) { --- > for (int h=1; h > 0; h--) { > for (int i=1; i < length; i++) { 11a12,15 > } > } > { > {
Diff side-by-side
public class Sort1Loops1Problem { public class Sort1Loops1Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int h=2; h > 0; h--) { | for (int h=1; h > 0; h--) {
for (int i=0; i < length; i++) { | for (int i=1; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
> }
> }
> {
> {
} }
} }
return a; return a;
} }
} }
12.3 Sort1Loops1Problem203.java
Improvement Details:
Sort1Loops1Problem203 100 mult 0.0 + 0.55120564 = 0.55120564 ASTNodes: 73 GPNodes: 80 xoverApplied: false xovers: 0 mutationApplied: true mutations: 4
Diff
3c3 < for (int h=2; h > 0; h--) { --- > for (int h=1; h > 0; h--) {
Diff side-by-side
public class Sort1Loops1Problem { public class Sort1Loops1Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int h=2; h > 0; h--) { | for (int h=1; h > 0; h--) {
for (int i=0; i < length; i++) { for (int i=0; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
return a; return a;
} }
} }
12.4 Sort1Loops1Problem20583.java
Improvement Details:
Sort1Loops1Problem20583 100 mult 0.0 + 0.32702017 = 0.32702017 ASTNodes: 73 GPNodes: 80 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
3,5c3,5 < for (int h=2; h > 0; h--) { < for (int i=0; i < length; i++) { < for (int j=0; j < length - 1; j++) { --- > for (int h=1; h > 0; h--) { > for (int i=h; i < length; i++) { > for (int j=0; j < length - i; j++) {
Diff side-by-side
public class Sort1Loops1Problem { public class Sort1Loops1Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int h=2; h > 0; h--) { | for (int h=1; h > 0; h--) {
for (int i=0; i < length; i++) { | for (int i=h; i < length; i++) {
for (int j=0; j < length - 1; j++) { | for (int j=0; j < length - i; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
return a; return a;
} }
} }
12.5 Sort1Loops1Problem25484.java
Improvement Details:
Sort1Loops1Problem25484 100 mult 0.0 + 0.5506292 = 0.5506292 ASTNodes: 62 GPNodes: 70 xoverApplied: true xovers: 1 mutationApplied: true mutations: 3
Diff
3,10c3,8 < for (int h=2; h > 0; h--) { < for (int i=0; i < length; i++) { < for (int j=0; j < length - 1; j++) { < if (a[j] > a[j + 1]) { < int k=a[j]; < a[j]=a[j + 1]; < a[j + 1]=k; < } --- > for (int i=1; i < length; i++) { > for (int j=0; j < length - 1; j++) { > if (a[j] > a[j + 1]) { > int k=a[j]; > a[j]=a[j + 1]; > a[j + 1]=k;
Diff side-by-side
public class Sort1Loops1Problem { public class Sort1Loops1Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int h=2; h > 0; h--) { | for (int i=1; i < length; i++) {
for (int i=0; i < length; i++) { <
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} <
} }
} }
} }
return a; return a;
} }
} }
12.6 Sort1Loops1Problem30298.java
Improvement Details:
Sort1Loops1Problem30298 100 mult 0.0 + 0.5506292 = 0.5506292 ASTNodes: 62 GPNodes: 70 xoverApplied: true xovers: 1 mutationApplied: true mutations: 2
Diff
3,10c3,8 < for (int h=2; h > 0; h--) { < for (int i=0; i < length; i++) { < for (int j=0; j < length - 1; j++) { < if (a[j] > a[j + 1]) { < int k=a[j]; < a[j]=a[j + 1]; < a[j + 1]=k; < } --- > for (int i=1; i < length; i++) { > for (int j=0; j < length - 1; j++) { > if (a[j] > a[j + 1]) { > int k=a[j]; > a[j]=a[j + 1]; > a[j + 1]=k;
Diff side-by-side
public class Sort1Loops1Problem { public class Sort1Loops1Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int h=2; h > 0; h--) { | for (int i=1; i < length; i++) {
for (int i=0; i < length; i++) { <
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} <
} }
} }
} }
return a; return a;
} }
} }
12.7 Sort1Loops1Problem32245.java
Improvement Details:
Sort1Loops1Problem32245 100 mult 0.0 + 0.5506292 = 0.5506292 ASTNodes: 65 GPNodes: 73 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
3,10c3,8 < for (int h=2; h > 0; h--) { < for (int i=0; i < length; i++) { < for (int j=0; j < length - 1; j++) { < if (a[j] > a[j + 1]) { < int k=a[j]; < a[j]=a[j + 1]; < a[j + 1]=k; < } --- > for (int i=1; i < length; i++) { > for (int j=0; j < length - 1; j++) { > if (a[j] > a[j + 1]) { > int k=a[j]; > a[j]=a[j + 1]; > a[j + 1]=k; 14c12,18 < return a; --- > { > { > } > { > return a; > } > }
Diff side-by-side
public class Sort1Loops1Problem { public class Sort1Loops1Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int h=2; h > 0; h--) { | for (int i=1; i < length; i++) {
for (int i=0; i < length; i++) { <
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
> {
> {
} }
> {
return a; return a;
> }
> }
} }
} }
12.8 Sort1Loops1Problem32931.java
Improvement Details:
Sort1Loops1Problem32931 100 mult 0.0 + 0.32701987 = 0.32701987 ASTNodes: 78 GPNodes: 85 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
3,10c3,20 < for (int h=2; h > 0; h--) { < for (int i=0; i < length; i++) { < for (int j=0; j < length - 1; j++) { < if (a[j] > a[j + 1]) { < int k=a[j]; < a[j]=a[j + 1]; < a[j + 1]=k; < } --- > { > for (int i=0; i < 0; i--) { > } > } > { > { > { > } > } > } > { > { > } > for (int i=1; i < length; i++) for (int j=0; j < length - i; j++) { > if (a[j] > a[j + 1]) { > int k=a[j]; > a[j]=a[j + 1]; > a[j + 1]=k;
Diff side-by-side
public class Sort1Loops1Problem { public class Sort1Loops1Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int h=2; h > 0; h--) { | {
for (int i=0; i < length; i++) { | for (int i=0; i < 0; i--) {
for (int j=0; j < length - 1; j++) { | }
> }
> {
> {
> {
> }
> }
> }
> {
> {
> }
> for (int i=1; i < length; i++) for (int j=0; j <
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} <
} }
} }
} }
return a; return a;
} }
} }
12.9 Sort1Loops1Problem33583.java
Improvement Details:
Sort1Loops1Problem33583 100 mult 0.0 + 0.55069053 = 0.55069053 ASTNodes: 75 GPNodes: 82 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
3,4c3,4 < for (int h=2; h > 0; h--) { < for (int i=0; i < length; i++) { --- > for (int h=2; h > 1; h--) { > for (int i=0; i < length - 1; i++) {
Diff side-by-side
public class Sort1Loops1Problem { public class Sort1Loops1Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int h=2; h > 0; h--) { | for (int h=2; h > 1; h--) {
for (int i=0; i < length; i++) { | for (int i=0; i < length - 1; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
return a; return a;
} }
} }
12.10 Sort1Loops1Problem38776.java
Improvement Details:
Sort1Loops1Problem38776 100 mult 0.0 + 0.5506292 = 0.5506292 ASTNodes: 63 GPNodes: 71 xoverApplied: true xovers: 25 mutationApplied: true mutations: 2
Diff
3,4c3,4 < for (int h=2; h > 0; h--) { < for (int i=0; i < length; i++) { --- > { > for (int i=1; i < length; i++) {
Diff side-by-side
public class Sort1Loops1Problem { public class Sort1Loops1Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int h=2; h > 0; h--) { | {
for (int i=0; i < length; i++) { | for (int i=1; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
return a; return a;
} }
} }
12.11 Sort1Loops1Problem5465.java
Improvement Details:
Sort1Loops1Problem5465 100 mult 0.0 + 0.5506292 = 0.5506292 ASTNodes: 63 GPNodes: 71 xoverApplied: false xovers: 0 mutationApplied: true mutations: 2
Diff
3,4c3,4 < for (int h=2; h > 0; h--) { < for (int i=0; i < length; i++) { --- > { > for (int i=1; i < length; i++) {
Diff side-by-side
public class Sort1Loops1Problem { public class Sort1Loops1Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int h=2; h > 0; h--) { | {
for (int i=0; i < length; i++) { | for (int i=1; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
return a; return a;
} }
} }
12.12 Sort1Loops1Problem54791.java
Improvement Details:
Sort1Loops1Problem54791 100 mult 0.0 + 0.5506292 = 0.5506292 ASTNodes: 63 GPNodes: 71 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
3,10c3,8 < for (int h=2; h > 0; h--) { < for (int i=0; i < length; i++) { < for (int j=0; j < length - 1; j++) { < if (a[j] > a[j + 1]) { < int k=a[j]; < a[j]=a[j + 1]; < a[j + 1]=k; < } --- > for (int i=1; i < length; i++) { > for (int j=0; j < length - 1; j++) { > if (a[j] > a[j + 1]) { > int k=a[j]; > a[j]=a[j + 1]; > a[j + 1]=k; 14c12,14 < return a; --- > { > return a; > }
Diff side-by-side
public class Sort1Loops1Problem { public class Sort1Loops1Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int h=2; h > 0; h--) { | for (int i=1; i < length; i++) {
for (int i=0; i < length; i++) { <
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} | {
return a; return a;
> }
} }
} }
12.13 Sort1Loops1Problem9214.java
Improvement Details:
Sort1Loops1Problem9214 100 mult 0.0 + 0.5506268 = 0.5506268 ASTNodes: 123 GPNodes: 128 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1 Sort1Loops1Problem9214 100 mult 0.0 + 0.5506268 = 0.5506268 ASTNodes: 123 GPNodes: 128 xoverApplied: false xovers: 0 mutationApplied: true mutations: 1
Diff
4c4,13 < for (int i=0; i < length; i++) { --- > { > for (int j=h; j < length - 1; j++) { > if (a[j] > a[j + 1]) { > int k=a[j]; > a[j]=a[j + 1]; > a[j + 1]=k; > } > } > } > for (int i=h--; i < length; i++) {
Diff side-by-side
public class Sort1Loops1Problem { public class Sort1Loops1Problem {
public static Integer[] sort( Integer[] a, Integer length public static Integer[] sort( Integer[] a, Integer length
for (int h=2; h > 0; h--) { for (int h=2; h > 0; h--) {
for (int i=0; i < length; i++) { | {
> for (int j=h; j < length - 1; j++) {
> if (a[j] > a[j + 1]) {
> int k=a[j];
> a[j]=a[j + 1];
> a[j + 1]=k;
> }
> }
> }
> for (int i=h--; i < length; i++) {
for (int j=0; j < length - 1; j++) { for (int j=0; j < length - 1; j++) {
if (a[j] > a[j + 1]) { if (a[j] > a[j + 1]) {
int k=a[j]; int k=a[j];
a[j]=a[j + 1]; a[j]=a[j + 1];
a[j + 1]=k; a[j + 1]=k;
} }
} }
} }
} }
return a; return a;
} }
} }
13 Script to show improvements found
baseDir='/home/bck/GP' seedFiles=( $(find $baseDir/Exhaustive/Seed-*.java) ) # echo ${seedFiles[@]} compareFiles(){ # aFile=$2 expNum=$(echo $2 | awk -F$3 '{ print $2 }' | awk -F. '{ print $1}' ) # echo $2 $expNum echo -e "\n\nDiff\n\n" echo "#+begin_src diff" diff $1 <(sed "s/$expNum//g" $2) echo "#+end_src" echo -e "\n\nDiff side-by-side\n\n" echo "#+begin_src diff" diff -wy -W180 $1 <(sed "s/$expNum//g" $2) echo "#+end_src" # | grep -v Problem | grep -v '^---' | grep -v ^1c1 # meld $1 $2 } for seedFile in ${seedFiles[@]} do problemName=$( echo $seedFile | awk -F- '{ print $2 }' | awk -F.java '{ print $1 }' ) echo -e "\n\n\n* $problemName" echo "Original - $seedFile" echo "#+begin_src java -n" cat $seedFile echo "#+end_src" for aFile in $(ls $baseDir/optimisedFiles/$problemName*java) do # diffName=$(echo $aFile | awk -F\/ '{ print $NF }' ) diffName=$(echo $aFile | awk -F\/ '{ print $NF }' | awk -F\. '{ print $1 }' ) echo "** $diffName" echo -e "Improvement Details:\n\n" echo "#+begin_src" # grep -A1 /home/bck/GP/Exhaustive/optimisedList.txt grep -m1 "\ $diffName\ " /home/bck/GP/optimisedFiles/optimisedFiles/optimisedFilesList.txt | grep \ =\ | tr '\n' '\n\n' | sed 's/[0-9][0-9][0-9][0-9]\/[0-9][0-9]\/[0-9][0-9]\ [0-9][0-9]:[0-9][0-9]:[0-9][0-9]:[0-9][0-9][0-9]\ //g' echo "#+end_src" compareFiles $seedFile $aFile $problemName done done