WonderSorting

WonderSorting

WonderSorting is a simple sorting algorithm inspired by the old joke:

"What goes: Click-click. Did I get it? Click-click. Did I get it?"

"Stevie Wonder trying to solve Rubik's cube."

The following Java class WonderSortingAlgorithm implements the joke as a number sorting algorithm. It changes the order of numbers randomly and then checks whether they are in perfect order. If not, it tries again and again until finally giving up after reaching the iteration count limit. Yep, it is exactly as stupid and inefficient as it seems, but it works! At least for a very small amount of numbers, say 5...

import java.util.*;

public class WonderSortingAlgorithm
{
  private Random random = new Random();
  private int maxTries = 1000;

  public void setMaxTries(int newMaxTries)
  {
    this.maxTries = newMaxTries;
  }

  public int sort(ArrayList<Double> numbers)
  {
    for(int i=0;i<maxTries;++i)
    {
      clickClick(numbers);
      if(didIGetIt(numbers))
        return i;
    }
    // Sorting failed
    return -1;
  }

  // Make a random change	 
  private void clickClick(ArrayList<Double> numbers)
  {
    int first = random.nextInt(numbers.size());
    int second = random.nextInt(numbers.size());
    Double tmp = numbers.get(first);
    numbers.set(first,numbers.get(second));
    numbers.set(second,tmp);
  }

  // Check the order
  private boolean didIGetIt(ArrayList<Double> numbers)
  {
    for(int i=1;i<numbers.size();++i)
    {
      double a = numbers.get(i-1).doubleValue();
      double b = numbers.get(i).doubleValue();
      if(a>b)
        return false;
    }
    return true;
  }
}

Although totally useless as a sorting algorithm, it is a perfect example for demonstrating algorithm module integration into the Cloud'N'Sci.fi Algorithms-as-a-Service marketplace. WonderSorting has all the elements that should be taken into account when designing commercial algorithm modules:

  • well-specified input (random ordered numbers)
  • well-specified output (ordered numbers)
  • well-specified functionality (sorting)
  • general-purpose (can be integrated into various solutions)
  • configurable (maximum number of tries)
  • heavy computation (makes sense to execute remotely)
  • failure possibility (limited execution time)
  • many different ways to implement (healthy competition)
  • performance options (increasing maxTries improves performance)

Integrating WonderSorting into Cloud'N'Sci.fi

Inside the Cloud'N'Sci.fi system, algorithm modules are managed and executed by the so called 'Scilego Server' ("Scilego" = "Science Lego" = "Algorithm Module"). Each integrated algorithm module must satisfy a set of simple rules specified in the algorithm module developer guide.

The following Java class wraps the WonderSortingAlgorithm into an executable algorithm module which is compatible with the integration rules. As you can see, integration work is very straightforward and does not require any changes to the core algorithm. Choose your favorite programming language and decide your own input/output file formats. As long as you obey the rules, your algorithm module is compatible with Cloud'N'Sci.fi.

Download complete Java source code for the WonderSortingAlgorithm example

import java.io.*;
import java.util.*;

public class WonderSortingAlgorithmModule
{
 public static void main(String[] args)
 { 
  try
  {
   // Rules 6 & 15: Working directory is 'bin' 
   // so the default configuration is in '../conf' 
   File defaultConfDir = new File("..","conf");
   WonderSortingAlgorithmModule module = 
     new WonderSortingAlgorithmModule(defaultConfDir);
   module.handleRequests();
  } 
  catch(Exception e)
  {
   // If case of any error, log the stack trace and fail fast.
   e.printStackTrace();
  }
 }

 private File defaultConfDir;
 private static final String configFileName = "wonder.conf";
 private static final String DEFAULT_LINE_SEPARATOR = "\r\n";
 private String NL = DEFAULT_LINE_SEPARATOR;
 private boolean verbose = false;

 public WonderSortingAlgorithmModule(File defaultConfDir)
 {
  this.defaultConfDir = defaultConfDir;
 }

 public void handleRequests() throws IOException
 {
  // Rule 16: Notify Scilego when ready to receive requests
  System.out.println(System.currentTimeMillis()+"\tREADY");

  // Rule 17: Read requests from standard input
  BufferedReader requestInput = 
    new BufferedReader(new InputStreamReader(System.in));
  String line;
  while((line=requestInput.readLine())!=null)
  {
   String tokens[] = line.split("\t");
   if(tokens.length!=5)
   {
    System.err.println("Invalid request: <"+line+">");
    continue;
   }
   String requestId = tokens[0];
   File inputDir = new File(tokens[1]);
   File outputDir = new File(tokens[2]);
   File configDir = new File(tokens[3]);
   String params = tokens[4];
   performRequest(requestId,inputDir,outputDir,configDir,params);
  }
 }

 private void performRequest(String requestId, File inputDir, 
   File outputDir, File configDir, String params)
 {
  // Rule 18: Notify Scilego when request execution starts
  notifyScilego("STARTED",requestId);

  // Verbose output may be enabled for testing
  verbose = params.equalsIgnoreCase("verbose");

  // Rule 25: Each request must be handled independently.
  // Easiest to achieve by creating and configuring an 
  // algorithm instance for each request, but usage of 
  // more resource efficient techniques is strongly 
  // encouraged to minimize computational overhead.
  WonderSortingAlgorithm sortingAlgorithm = 
    new WonderSortingAlgorithm();

  try
  {
   // Rule 19: Read config and notify Scilego when initialized
   configure(configDir,sortingAlgorithm);
   notifyScilego("INITIALIZED",requestId);

   // Rule 20: Read input data and start processing it
   File inputFiles[] = inputDir.listFiles();
   for(File inputFile: inputFiles)
   {
    ArrayList<Double> numbers = readInputData(inputFile); 
    int iterations = sortingAlgorithm.sort(numbers);
    if(iterations<0)
    {
     // Rule 24: Notify Scilego if the request fails 
     notifyScilego("FAILED",requestId);
     return;
    }
    writeLog("Sorting completed after "+iterations+" iterations");
    // Rule 21: Write results into the output directory
    File outputFile = new File(outputDir,inputFile.getName());
    writeOutputData(numbers,outputFile);
   }

   // Rule 23: Notify Scilego when request has been completed
   notifyScilego("COMPLETED",requestId);   
  } 
  catch(Exception e)
  {
   // Rule 22: Log any errors by writing to stderr
   e.printStackTrace();
   // Rule 24: Notify Scilego if the request fails 
   notifyScilego("FAILED",requestId);
  }  
 }

 private void configure(File configDir, 
   WonderSortingAlgorithm sortingAlgorithm) 
   throws FileNotFoundException, IOException
 {
  // Look for a request-specific configuration file first.
  File configFile = new File(configDir,configFileName);
  if(configFile.exists())
  {
   writeLog("Using request-specific configuration file");
  }
  else
  {
   // If not found, look for a default configuration file.
   configFile = new File(defaultConfDir,configFileName);
   if(configFile.exists())
   {
    writeLog("Using default configuration file");
   }
   else
   {
    writeLog("Using hard-coded configuration");
    return;
   }
  }
  Properties properties = new Properties();
  properties.load(new FileReader(configFile));
  String maxTriesValue = properties.getProperty("max-tries");
  String lineSeparator = properties.getProperty("line-separator");
  if(maxTriesValue!=null)
  {   
   int maxTries = Integer.parseInt(maxTriesValue);
   writeLog("Setting maximum number of tries: "+maxTries);
   sortingAlgorithm.setMaxTries(maxTries);
  }
  if(lineSeparator!=null)
  {
   writeLog("Setting line separator: "+lineSeparator);
   if(lineSeparator.equalsIgnoreCase("unix"))
    NL = "\n";
   else if(lineSeparator.equalsIgnoreCase("windows"))
    NL = "\r\n";
   else
    NL = DEFAULT_LINE_SEPARATOR;
  }   
  else
  {
   // Remember to reset to default to obey Rule 25.
   NL = DEFAULT_LINE_SEPARATOR;
  }
 }

 private ArrayList<Double> readInputData(File inputFile) 
   throws IOException
 {
  writeLog("Processing file "+inputFile.getName());

  // Assuming a text file with a single number on each line
  ArrayList<Double> numbers = new ArrayList<Double>();
  BufferedReader reader = 
    new BufferedReader(new FileReader(inputFile));
  String line;
  while((line=reader.readLine())!=null)
  {
   numbers.add(Double.parseDouble(line));
  }
  reader.close();
  return numbers;
 }


 private void writeOutputData(ArrayList<Double> numbers, 
   File outputFile) throws FileNotFoundException
 {
  writeLog("Saving file "+outputFile.getName());

  PrintStream out = new PrintStream(
    new BufferedOutputStream(new FileOutputStream(outputFile)));
  for(Double num: numbers)
  {
   out.print(num.toString()+NL); 
  }
  out.close();
 }

 private void notifyScilego(String status,String requestId)
 {
  long timestamp = System.currentTimeMillis();
  System.out.println(timestamp+"\t"+status+"\t"+requestId);
  System.out.flush();
 }

 private void writeLog(String string)
 {
  if(verbose)
  {
   // Rule 22: Log useful information by writing to stderr
   System.err.println(string);
  }
 }
}

Links


This "algorithm" was created only to demonstrate integration of new algorithm modules into the Cloud'N'Sci.fi marketplace. Please take it as a fully functional demo for the Algorithms-as-a-Service concept, not as a serious attempt to solve the number sorting problem.