PDA

View Full Version : Boyer-Moore-Horspool, Quicksort, and Introsort


WhiteDragon
08-17-2008, 04:04 AM
Just some random algorithms I coded into GScript awhile ago.
I'm pretty sure they are never going to be used on Classic, so I'll just post them here.

Boyer-Moore-Horspool

//#CLIENTSIDE

/**
* Finds the first occurrence of a pattern P in search string
* T using the Boyer-Moore-Horspool string search algorithm
* (I didn't code the second table for a full Boyer-Moore).
*
* Returns -1 if no match.
*
*
* Average Case Complexity of O(mn).
* Worst Case of O(n**2) if m==n.
* m = pattern length
* n = search string length
*
*
* @param string The search string
* @param string The pattern
* @return int The position of the first occurrence of pattern
*/
function boyer_moore(T, P) {
temp.last = last_table(P);
player.chat = temp.last;
temp.n = T.length();
temp.m = P.length();
temp.i = temp.m-1;
temp.j = temp.m-1;
do {
if (P.charat(temp.j) == T.charat(temp.i)) {
if (temp.j == 0) {
return temp.i; // Matched
} else {
temp.i--;
temp.j--;
}
} else {
player.chat = temp.j SPC temp.i SPC P.charat(temp.j) SPC T.charat(temp.i);
temp.i = temp.i + temp.m - min(temp.j, 1 + temp.last[getascii(T.charat(temp.i))]);
temp.j = temp.m - 1;
player.chat @= temp.j SPC temp.i SPC P.charat(temp.j) SPC T.charat(temp.i);
}
} while (temp.i <= temp.n);
return -1; // P does not exist in T
}

/**
* Generates an array of the last locations
* of each character in a string P.
*
* @param string
* @return array
*/
function last_table(P) {
temp.last = new [255];
for (temp.i=0; temp.i<P.length()-1; temp.i++)
temp.last[getascii(P.charat(temp.i))] = temp.i;
return temp.last;
}


Quicksort

//#CLIENTSIDE

/**
* Adaptor method for quicksort.
*
* @param array The array to be sorted.
*/
function quicksort(array) {
qsort(array, 0, array.size()-1);
}

/**
* Sorts the array with the quicksort algorithm.
*
* Average Case Time Complexity of O(n log n).
* Worst Case Time Complexity of O(n**2).
* Average Case Space Complexity of O(log n).
* n = array size
*
* @param array The array to be sorted
* @param int The position of the left side of the array
* @param int The position of the right side of the array
*/
function qsort(temp.array, temp.left, temp.right) {
if (temp.right > temp.left) {
temp.pivotNewIndex = qsort_partition(temp.array, temp.left, temp.right, temp.left);
qsort(temp.array, temp.left, temp.pivotNewIndex - 1);
qsort(temp.array, temp.pivotNewIndex + 1, temp.right);
}
}

/**
* In-place parition algorithm. Paritions the portion of
* the array between indexs left and right, inclusively.
*
* @param array The array to be partitioned
* @param int The left bound
* @param int The right bound
* @param int The pivot index
*/
function qsort_partition(temp.array, temp.left, temp.right, temp.pivotIndex) {
temp.pivotValue = temp.array[temp.pivotIndex];

temp.s = temp.array[temp.right];
temp.array[temp.right] = temp.array[temp.pivotIndex];
temp.array[temp.pivotIndex] = temp.s;

temp.storeIndex = temp.left;
for (temp.i = temp.left; temp.i < temp.right; temp.i++) {
if (temp.array[temp.i] <= temp.pivotValue) {
temp.s = temp.array[temp.storeIndex];
temp.array[temp.storeIndex] = temp.array[temp.i];
temp.array[temp.i] = temp.s;
temp.storeIndex++;
}
}
temp.s = temp.array[temp.right];
temp.array[temp.right] = temp.array[temp.storeIndex];
temp.array[temp.storeIndex] = temp.s;
return temp.storeIndex;
}


Introsort

//#CLIENTSIDE
this.threshold = 16;

/**
* Sorts an algorithm with the introspective sort algorithm.
* (Begins with quicksort and switchs to heapsort when
* the recursion depth exceeds a level based on the
* logarithm of the number of elements being sorted.)
*
* Uses median-of-3 pivot selection algorithm
*
* Average Case Time Complexity comparable to quicksort on typical data sets
* Worst Case Time Complexity of O(n log n)
*
* @param array The array to be sorted.
*/


function introsort(temp.a) {
this.a = temp.a;
introsort_loop(0, this.a.size(), 2*floor_lg(this.a.size()));
insertionsort(0, this.a.size());
return this.a;
}

function introsort_loop(temp.lo, temp.hi, temp.depth_limit) {
while (temp.hi - temp.lo > this.threshold) {
if (temp.depth_limit == 0) {
heapsort(temp.lo, temp.hi);
return;
}
temp.depth_limit--;
temp.p = partition(temp.lo, temp.hi, medianof3(temp.lo, temp.lo+((temp.hi - temp.lo)/2)+1, temp.hi-1));
introsort_loop(temp.p, temp.hi, temp.depth_limit);
temp.hi = temp.p;
}
}

function partition(temp.lo, temp.hi, temp.x) {
temp.i = temp.lo;
temp.j = temp.hi;
while (true) {
while (this.a[temp.i] < temp.x)
temp.i++;
temp.j--;
while (temp.x < this.a[temp.j])
temp.j--;
if (temp.i > temp.j)
return temp.i;
exchange(temp.i, temp.j);
temp.i++;
}
}

function medianof3(temp.lo, temp.mid, temp.hi) {
if (this.a[temp.mid] < this.a[temp.lo]) {
if (this.a[temp.hi] < this.a[temp.mid])
return this.a[temp.mid];
else {
if (this.a[temp.hi] < this.a[temp.lo])
return this.a[temp.hi];
else
return this.a[temp.lo];
}
} else {
if (this.a[temp.hi] < this.a[temp.mid]) {
if (this.a[temp.hi] < this.a[temp.lo])
return this.a[temp.lo];
else
return this.a[temp.hi];
} else
return this.a[temp.mid];
}
}

function heapsort(temp.lo, temp.hi) {
temp.n = temp.hi - temp.lo;
for (temp.i = temp.n/2; temp.i >= 1; temp.i--) {
downheap(temp.i, temp.n, temp.lo);
}
for (temp.i = temp.n; temp.i > 1; temp.i--) {
exchange(temp.lo, temp.lo + temp.i - 1);
downheap(1, temp.i-1, temp.lo);
}
}

function downheap(temp.i, temp.n, temp.lo) {
temp.d = this.a[temp.lo + temp.i - 1];
while (temp.i <= temp.n/2) {
temp.child = 2*temp.i;
if (temp.child < temp.n && this.a[temp.lo+temp.child-1] < this.a[temp.lo+temp.child])
temp.child++;
if (!temp.d < this.a[temp.lo+temp.child-1])
break;
this.a[temp.lo+temp.i-1] = this.a[temp.lo+temp.child-1];
temp.i = temp.child;
}
this.a[temp.lo + temp.i - 1] = temp.d;
}

function insertionsort(temp.lo, temp.hi) {
for (temp.i = temp.lo; temp.i < temp.hi; temp.i++) {
temp.j = temp.i;
temp.t = this.a[temp.i];
while (temp.j != temp.lo && temp.t < this.a[temp.j-1]) {
this.a[temp.j] = this.a[temp.j-1];
temp.j--;
}
this.a[temp.j] = temp.t;
}
}

function exchange(temp.i, temp.j) {
temp.t = this.a[temp.i];
this.a[temp.i] = this.a[temp.j];
this.a[temp.j] = temp.t;
}

function floor_lg(temp.a) {
return int(log(2.718281828459, temp.a)/log(2.718281828459, 2));
}



The sortbyvalue function uses heap sort, but is considerable faster since it's native. You should only use these sorts if you know your data set is very large to make up for the difference.

I coded a Boyer-Moore-Horspool because it's preprocessing time is considerably less than a Boyer-Moore even though a Boyer-Moore can achieve O(n). A Boyer-Moore only reaches faster times when you start reaching text sizes near the lengths of books.

DrakilorP2P
08-23-2008, 07:27 PM
This thread evidence that people want pretty screenshots rather than clever coding.

Chompy
08-23-2008, 09:34 PM
This thread evidence that people want pretty screenshots rather than clever coding.

Yup, screenshots and/or examples :]

LoneAngelIbesu
08-23-2008, 09:39 PM
This thread evidence that people want pretty screenshots rather than clever coding.
I can't help if this is esoteric. :cry:

Novo
11-22-2008, 08:07 AM
These don't look ready for use.

You still have debug information in them (Such as player.chat @= "Stuff") as well as what I think is violating variable scope. (Such as using temp.a without having temp.a defined in the function).

Otherwise, it's good work. :)

Novo
11-22-2008, 09:03 AM
Hope you don't mind, I did some edits to the quicksort! I added the ability to compare any object using a custom function.


/**
* Compares two values and returns a value that represents an order.
*
* If A < B, output is negative
* If A == B, output is zero
* If A > B, output is positive
*
* @param object First element to compare
* @param object Second element to compare
*/
function default_cmp( sideA, sideB ) {
return (sideA - sideB);
}

/**
* Adaptor method for quicksort.
*
* @param array The array to be sorted.
* @param function The function that compares two elements
*/
function quicksort(array, compare_function ) {
this.cmp = ( temp.compare_function == null ? this.default_cmp : temp.compare_function );
qsort(array, 0, array.size()-1, compare_function);
}

/**
* Sorts the array with the quicksort algorithm.
*
* Average Case Time Complexity of O(n log n).
* Worst Case Time Complexity of O(n**2).
* Average Case Space Complexity of O(log n).
* n = array size
*
* @param array The array to be sorted
* @param int The position of the left side of the array
* @param int The position of the right side of the array
* @param function The function that compares two elements
*/
function qsort(temp.array, temp.left, temp.right ) {
if (temp.right > temp.left) {
temp.pivotNewIndex = qsort_partition(temp.array, temp.left, temp.right, temp.left );
qsort(temp.array, temp.left, temp.pivotNewIndex - 1 );
qsort(temp.array, temp.pivotNewIndex + 1, temp.right );
}
return temp.array;
}

/**
* In-place parition algorithm. Paritions the portion of
* the array between indexs left and right, inclusively.
*
* @param array The array to be partitioned
* @param int The left bound
* @param int The right bound
* @param int The pivot index
* @param function The function that compares two elements
*/
function qsort_partition(temp.array, temp.left, temp.right, temp.pivotIndex ) {
temp.pivotValue = temp.array[temp.pivotIndex];

temp.s = temp.array[temp.right];
temp.array[temp.right] = temp.array[temp.pivotIndex];
temp.array[temp.pivotIndex] = temp.s;

temp.storeIndex = temp.left;
for (temp.i = temp.left; temp.i < temp.right; temp.i++) {
if ( cmp( temp.array[temp.i], temp.pivotValue ) <= 0 ) {
temp.s = temp.array[temp.storeIndex];
temp.array[temp.storeIndex] = temp.array[temp.i];
temp.array[temp.i] = temp.s;
temp.storeIndex++;
}
}
temp.s = temp.array[temp.right];
temp.array[temp.right] = temp.array[temp.storeIndex];
temp.array[temp.storeIndex] = temp.s;
return temp.storeIndex;
}


This allows you to actually sort multi-dimensional array with specific indexes (or objects with values):


temp.compare_function = function(a,b){
return (a[0] - b[0]);
};

quicksort( initial_list, temp.compare_function );


Or decreasing order:



temp.compare_function = function(a,b){
return (b - a);
};

quicksort( initial_list, temp.compare_function );


Or whatever way you wish to sort.

WhiteDragon
11-23-2008, 06:02 AM
Ah, I didn't realize I left those in there, I guess I put on an older version. It works entirely though.

And personally I would have passed around the compare function, but good job. You added some extra @params in the functions though.