Graal Forums  

Go Back   Graal Forums > Development Forums > NPC Scripting > Code Gallery
FAQ Members List Calendar Search Today's Posts Mark Forums Read

Reply
 
Thread Tools Search this Thread Display Modes
  #1  
Old 08-17-2008, 04:04 AM
WhiteDragon WhiteDragon is offline
Banned
Join Date: Feb 2007
Posts: 1,002
WhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to behold
Boyer-Moore-Horspool, Quicksort, and Introsort

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
Graal Script Code:
//#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(TP) {
  
temp.last last_table(P);
  
player.chat temp.last;
  
temp.T.length();
  
temp.P.length();
  
temp.temp.m-1;
  
temp.temp.m-1;
  do {
    if (
P.charat(temp.j) == T.charat(temp.i)) {
      if (
temp.== 0) {
        return 
temp.i// Matched
      
} else {
        
temp.i--;
        
temp.j--;
      }
    } else {
      
player.chat temp.j SPC temp.i SPC P.charat(temp.jSPC T.charat(temp.i);
      
temp.temp.temp.min(temp.jtemp.last[getascii(T.charat(temp.i))]);
      
temp.temp.1;
      
player.chat @= temp.j SPC temp.i SPC P.charat(temp.jSPC T.charat(temp.i);
    }
  } while (
temp.<= 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=0temp.i<P.length()-1temp.i++)
    
temp.last[getascii(P.charat(temp.i))] = temp.i;
  return 
temp.last;

Quicksort
Graal Script Code:
//#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.lefttemp.right) {
  if (
temp.right temp.left) {
    
temp.pivotNewIndex qsort_partition(temp.array, temp.lefttemp.righttemp.left);
    
qsort(temp.array, temp.lefttemp.pivotNewIndex 1);
    
qsort(temp.array, temp.pivotNewIndex 1temp.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.lefttemp.righttemp.pivotIndex) {
  
temp.pivotValue temp.array[temp.pivotIndex];

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

Introsort
Graal Script Code:
//#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.temp.a;
  
introsort_loop(0this.a.size(), 2*floor_lg(this.a.size()));
  
insertionsort(0this.a.size());
  return 
this.a;
}

function 
introsort_loop(temp.lotemp.hitemp.depth_limit) {
  while (
temp.hi temp.lo this.threshold) {
    if (
temp.depth_limit == 0) {
      
heapsort(temp.lotemp.hi);
      return;
    }
    
temp.depth_limit--;
    
temp.partition(temp.lotemp.himedianof3(temp.lotemp.lo+((temp.hi temp.lo)/2)+1temp.hi-1));
    
introsort_loop(temp.ptemp.hitemp.depth_limit);
    
temp.hi temp.p;
  }
}

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

function 
medianof3(temp.lotemp.midtemp.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.lotemp.hi) {
  
temp.temp.hi temp.lo;
  for (
temp.temp.n/2temp.>= 1temp.i--) {
    
downheap(temp.itemp.ntemp.lo);
  }
  for (
temp.temp.ntemp.1temp.i--) {
    
exchange(temp.lotemp.lo temp.1);
    
downheap(1temp.i-1temp.lo);
  }
}

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

function 
insertionsort(temp.lotemp.hi) {
  for (
temp.temp.lotemp.temp.hitemp.i++) {
    
temp.temp.i;
    
temp.this.a[temp.i];
    while (
temp.!= temp.lo && temp.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.itemp.j) {
  
temp.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.718281828459temp.a)/log(2.7182818284592));

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.
Reply With Quote
  #2  
Old 08-23-2008, 07:27 PM
DrakilorP2P DrakilorP2P is offline
Registered User
DrakilorP2P's Avatar
Join Date: Apr 2006
Posts: 755
DrakilorP2P is just really niceDrakilorP2P is just really nice
This thread evidence that people want pretty screenshots rather than clever coding.
Reply With Quote
  #3  
Old 08-23-2008, 09:34 PM
Chompy Chompy is offline
¯\(º_o)/¯
Chompy's Avatar
Join Date: Sep 2006
Location: Norway
Posts: 2,815
Chompy is just really niceChompy is just really niceChompy is just really nice
Send a message via MSN to Chompy
Quote:
Originally Posted by DrakilorP2P View Post
This thread evidence that people want pretty screenshots rather than clever coding.
Yup, screenshots and/or examples :]
__________________
Reply With Quote
  #4  
Old 08-23-2008, 09:39 PM
LoneAngelIbesu LoneAngelIbesu is offline
master of infinite loops
LoneAngelIbesu's Avatar
Join Date: May 2007
Location: Toldeo, Ohio
Posts: 1,049
LoneAngelIbesu has a spectacular aura aboutLoneAngelIbesu has a spectacular aura about
Send a message via AIM to LoneAngelIbesu
Quote:
Originally Posted by DrakilorP2P View Post
This thread evidence that people want pretty screenshots rather than clever coding.
I can't help if this is esoteric.
__________________
"We are all in the gutter, but some of us are looking at the stars."
— Oscar Wilde, Lady Windermere's Fan
Reply With Quote
  #5  
Old 11-22-2008, 08:07 AM
Novo Novo is offline
[TServerDeveloper]
Join Date: Jun 2006
Posts: 448
Novo will become famous soon enough
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.
Reply With Quote
  #6  
Old 11-22-2008, 09:03 AM
Novo Novo is offline
[TServerDeveloper]
Join Date: Jun 2006
Posts: 448
Novo will become famous soon enough
Hope you don't mind, I did some edits to the quicksort! I added the ability to compare any object using a custom function.

Graal Script Code:
/**
  * 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_cmpsideAsideB ) {
  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()-1compare_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.lefttemp.right ) {
  if (
temp.right temp.left) {
    
temp.pivotNewIndex qsort_partition(temp.array, temp.lefttemp.righttemp.left );
    
qsort(temp.array, temp.lefttemp.pivotNewIndex );
    
qsort(temp.array, temp.pivotNewIndex 1temp.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.lefttemp.righttemp.pivotIndex ) {
  
temp.pivotValue temp.array[temp.pivotIndex];

  
temp.temp.array[temp.right];
  
temp.array[temp.right] = temp.array[temp.pivotIndex];
  
temp.array[temp.pivotIndex] = temp.s;
  
  
temp.storeIndex temp.left;
  for (
temp.temp.lefttemp.temp.righttemp.i++) {
    if ( 
cmptemp.array[temp.i], temp.pivotValue ) <= ) {
      
temp.temp.array[temp.storeIndex];
      
temp.array[temp.storeIndex] = temp.array[temp.i];
      
temp.array[temp.i] = temp.s;
      
temp.storeIndex++;
    }
  }
  
temp.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):

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

  
quicksortinitial_listtemp.compare_function ); 
Or decreasing order:

Graal Script Code:

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

  
quicksortinitial_listtemp.compare_function ); 
Or whatever way you wish to sort.
Reply With Quote
  #7  
Old 11-23-2008, 06:02 AM
WhiteDragon WhiteDragon is offline
Banned
Join Date: Feb 2007
Posts: 1,002
WhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to behold
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.
Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 01:14 PM.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright (C) 1998-2008 Linux cyberjoueurs All Rights Reserved.