PHP OOP & Algorithms II: What to Use

algorithm2 What Are the Guidelines?

Like just about everything else in computing, there’s a certain amount of empirical testing. More importantly, however, are the general principles derived by both empirical and mathematical calculations. In the first post on algorithms and OOP, you saw an example that showed how many operations were necessary to find “Waldo,” a name near the end of an array of over 1,000 elements. One used a straight up loop and the other a binary search algorithm. Both were pretty quick; in fact it was hard to tell the difference in speed, and without seeing the little dots, you would not have seen the number of iterations required in each algorithm. You also saw that quadratic algorithms grew at rates that can quickly reach a point where processing comes to a crawl.

A Table Guide

Table 1 is derived from the 4th Edition of Algorithms (2011, p. 187) by Robert Sedgewick and Kevin Wayne. I’ve summarized it further. (Examples in the book are all in Java.) It is a rough but useful guide, and I have found it handy for a quick look-up.

Table 1: Algorithm Order of Growth

Name	Order of Growth	Description	Example
constant	1	statement	2 + 7
logarithmic	log N	divide in half	binary search
linear	N	loop	find max
linearithmic	N log N	divide & conquer	mergesort
quadratic	N²	double loop	check all pairs
cubic	N³	triple loop	check all triples
exponential	2^N	exhaustive search	check all subsets

Fortunately, most of the time our algorithms are pretty simple statements, single loops or recursive calls. All of the models in green are algorithms we should try and stick with. You should avoid the reds ones if possible.

What About Recursive Algorithms?

Those who love to profess a little knowledge like to say that recursion is slower than a loop. As indicated, we really don’t want to end up paying attention to small costs. Recursion is important, and using recursive algorithms is cost effective, especially since the difference in running time is negligible.

We often use recursive implementations of methods because they can lead to compact, elegant code that is easier to understand than a corresponding implementation that does not use recursion.
~Robert Sedgewick and Kevin Wayne

(A recursive example of a logarithmic algorithm is not included here, but you can find a recursive binary search in the post on binary searches.) What we need to pay attention to are the order-of-growth issues. For example, quadratic algorithms on the lower end of the scale are not really that bad, but when the N increases at a squaring rate, it’s easy to run into problems. So if you avoid quadratic algorithms, you’ll be better off when the N increases. On the other hand, whether you’re using a recursive method for a binary search, you’ll not see that much of a difference as the N increases compared to non-recursive methods.

A Strategy Design Pattern Handles Algorithms

This blog has lots of posts detailing the Strategy design patterns; so if you’re not familiar with a PHP implementation of the Strategy pattern, you might want to take a quick look at the code. To get started, play the example and download the code.

In the last post on algorithms, the program used a Factory Method pattern to produce an array, and in this post, the same pattern is used and two additional array products have been added. However, instead of having the algorithm classes be more or less on their own, all of the algorithm classes have been organized into a Strategy design pattern. Figure 1 is a file diagram of the objects in the application:

Figure 1: Object groupings with Strategy and Factory Method patterns

If Figure 1 looks a bit daunting, it is only three object groupings. The HTML and PHP Client make a request for one of seven algorithm implementations through a Strategy pattern. The concrete strategy implementations all get their data from a “data factory.” Figure 2 provides an easier (and more accurate) way to understand what’s going on.

Figure 2: Overview of the main purposes of the objects.

So instead of having a complex task, you only have three groupings of classes and interfaces: Those making a request (Clients), those executing operations on data (Algorithms) organized as a Strategy pattern and the data itself organized with a Factory Method (Data.)

Figure 2 shows a simplified version of what the program does. The Context class considerably eases the requesting process. The HTML UI passes the name of the requested concrete strategy to the Client, and the Client uses the name as a parameter in a Context method. The Client is not bound to any of the concrete strategies because the strategy classes are handled by a Context object and method. (Click continue to see the PHP implementations of the algorithms.)

The Algorithm Code: Strategy Implementations

The seven categories of algorithms are implemented in the seven concrete implementations of the IStrategy interface. Table 1 shows the order of growth of each, and you can see an example in the classes bearing the algorithm names. The only exception is the exponential because I didn’t want to lock up your computer or my server. However, some problems do require an exponential algorithms, and I want to briefly look at an example further on. (E(c) = 1/2 * (2(pow,c) – 1)

The IStrategy interface must consider the minimal number of parameters required for the algorithm that requires the most. In this case, since the examples use search algorithms, the minimum for a cubic search are three arrays and three keys; so the interface will need a total of six parameters. Code hinting will help remind the developer where the array parameters go and where the general variable parameters go:

^?View Code PHP


interface IStrategy 
{
    function searchAlgorithm(array $array1,array $array2,array $array3,$var1, $var2, $var3);
}
?>

Constant: The Constant class is quite simple, but it has to use the entire IStrategy interface; so it’s implementation includes a lot of dummy variables and arrays. A constant executes a fixed number of operation to finish its job, and PHP programming most operations are in content time.

^?View Code PHP


class Constant implements IStrategy
{  
  private $var1;
  public function __construct() 
  {
    $dummyArray1=array();
    $dummyArray2=array();
    $dummyArray3=array();
    $dummyVar2=0;
    $dummyVar3=0;
    //Constant algorithm
    $this->var1 ="Order of growth = " . 1;
 
    $this->searchAlgorithm($dummyArray1, $dummyArray2,$dummyArray3,$this->var1,$dummyVar2,$dummyVar3);
  }
 
  //Show value
  function searchAlgorithm(array $array1,array $array2,array $array3,$someVar, $var2, $var3)
  {
    //Another constant algorithm
    echo $someVar;
  }
}
?>

For the most part, we write constant algorithms to make up more complex algorithms.

Logarithmic: The growth rate for logarithmic algorithms is close to constant time growth rate. To give you an idea, consider the log value of N with values of 100, 200 and 300. Compare that with the quadratic order of N growth for the same values:

    100 log 4.6 quadratic 10000
    200 log 5.3 quadratic 40000
    300 log 5.7 quadratic 90000

As you can see, the order of growth for logarithmic algorithms is close to that of constants. The implementation uses a simple binary search algorithm:

^?View Code PHP


//Binary Search
class Logarithmic implements IStrategy
{  
  private $arrayFactory;
  public function __construct() 
  {
    $dummyArray2=array();
    $dummyArray3=array();
    $dummyVar=0;
    $this->arrayFactory = new NameFactory();
    $this->arrayFactory->factoryMethod(new FirstNameProduct());
    $target=$this->arrayFactory->factoryMethod(new FirstNameProduct());
      $ans = $this->searchAlgorithm($target,$dummyArray2,$dummyArray3,"Waldo",$dummyVar,$dummyVar);
      if($ans != -1)
      {
          $this->output="The name " . $target[$ans] . " has been found with a logarithmic algorithm!";
      }
      else
      {
          $this->output = "Search name not found.";
      }
      echo $this->output; 
  }
 
  //Basic binary search
  function searchAlgorithm(array $array1,array $array2,array $array3,$key, $var2, $var3)
  {
      $lo = 0;
      $hi = count($array1)-1;
      while($lo <= $hi)
      {
          $mid = $lo + ($hi - $lo) / 2;
          if ($key < $array1[$mid])
          {
            $hi = $mid -1;
          }
          else if ($key > $array1[$mid])
          {
            $lo = $mid + 1;
          }
          else return $mid;
      }
      return -1;     
  }
}
?>

You can see how the details of the algorithm works in this post explaining binary searches.

Linear: My favorite loop structure is the foreach loop. I like it because it can iterate through any object, arrays in particular, and pull out its properties as elements. The linear algorithm is pretty speedy itself and its order of growth linear—as N increases; so too do the number of iterations. That’s not bad, and even though it involves a lot more iterations than a logarithmic algorithm (as seen in the previous post of algorithms)) it does not grow exponentially. The best part of linear algorithms is that they’re simple to implement:

^?View Code PHP


class Linear implements IStrategy
{  
  private $arrayFactory;
  private $firstName;
  public function __construct() 
  {
    $dummyArray2=array();
    $dummyArray3=array();
    $dummyVar=0;
    $this->arrayFactory = new NameFactory();
    $this->firstName=$this->arrayFactory->factoryMethod(new FirstNameProduct());
      $ans = $this->searchAlgorithm($this->firstName,$dummyArray2,$dummyArray3,"Waldo",$dummyVar,$dummyVar);
      if($ans != -1)
      {
          $this->output="The name " . $ans . " has been found with a linear algorithm!";
      }
      else
      {
          $this->output = "Search name not found.";
      }
      echo $this->output; 
  }
 
  //Linear search (Simple loop)
  function searchAlgorithm(array $array1,array $array2,array $array3,$key, $var2, $var3)
  {
    foreach($array1 as $guy)
    {
      if($guy == $key)
      {
        return $guy;
      }
    }
    return -1;
  }
}
?>

Don’t confuse linear algorithms with sequential programming. Linear algorithms can be used in either type of program structure, and since OOP is favored for development efficiency and effectiveness, it makes more sense to use linear algorithms in OOP.

Linearithmic: For me, linearithmic algorithms are saviors from the slippery slope of quadratic ones. Essentially, a linearithmic algorithm is one that combines a linear with a logarithmic algorithm; hence the growth notation of N log N. If you’re familiar with either the merge sort or the quick sort algorithms, you know something about how the linearithmic algorithm is implemented. However, if you try and find a linearithmic search algorithms, you’re likely to come up short. However, since we know both linear and logarithmic algorithms, putting the two together should not be too difficult as you can see in the following listing:

^?View Code PHP


class Linearithmic implements IStrategy
{  
  private $arrayFactory;
  private $firstName;
  private $surName;
  private $output=array();
  private $notFound;
 
  public function __construct() 
  {
    $dummyArray=array();
    $dummyVar=0;
 
    $this->arrayFactory = new NameFactory();
    $this->firstName=$this->arrayFactory->factoryMethod(new FirstNameProduct());
    $this->surName=$this->arrayFactory->factoryMethod(new SurNameProduct());
 
      $this->output = $this->searchAlgorithm($this->firstName, $this->surName,$dummyArray,"Waldo","Watson",$dummyVar);
      if($this->output != -1)
      {
          $this->output=$this->output;
          echo $this->output[0] . " ". $this->output[1] . " found with a linearithmic algorithm!";
      }
      else
      {
          $this->notFound = "Search name not found.";
      }
      echo $this->notFound; 
  }
 
  //Linearithmic = Linear + Logarithmic (Loop + binary search) N log N
  function searchAlgorithm(array $outer,array $inner,array $array3, $keyOut, $keyIn, $var3)
  {
    //Loop = linear
    foreach($outer as $first)
    {
      if($first==$keyOut)
      {
        //Binary search = logarithmic
        $lo = 0;
        $hi = count($inner)-1;
        while($lo <= $hi)
        {
          $mid = $lo + ($hi - $lo) / 2;
          if ($keyIn < $inner[$mid])
          {
            $hi = $mid -1;
          }
          else if ($keyIn > $inner[$mid])
          {
            $lo = $mid + 1;
          }
          else
          {
            $found=array($first,$inner[$mid]);
            return $found;
          }
        }
      }
    }
    return -1;
  }
}
?>

In this particular example, the search did not examine the inner loop (a binary search) until the key from the outer loop had been found. In this implementation, it clearly separates the two operations—linear and logarithmic. By adding another conditional to the while loop in the binary search, the binary search would have been run for each iteration of the linear search until the first name had been located and then the binary search until the last name was found. If you would like to see a better example of a worse case scenario, feel free to make those changes.

Quadratic: In running the quadratic example, you probably didn’t see any difference between its speed and that of the linearithmic algorithm. The FirstNameProduct contains 1220 elements and the SurnameProduct contains 300; so you might be thinking, it’s not so bad. The example algorithm is nothing but a double loop; so it’s also not too difficult to implement. Why not just use quadratic algorithms until you get to a point where there’s a noticeable slowdown? Take a look at the code, and you’ll see how easy a quadratic is to build.

^?View Code PHP


class Quadratic implements IStrategy
{  
  private $arrayFactory;
  private $firstName;
  private $surName;
  private $output=array();
  private $notFound;
  public function __construct() 
  {
    $dummyArray=array();
    $dummyVar=0;
 
    $this->arrayFactory = new NameFactory();
    $this->firstName=$this->arrayFactory->factoryMethod(new FirstNameProduct());
    $this->surName=$this->arrayFactory->factoryMethod(new SurNameProduct());
 
      $this->output = $this->searchAlgorithm($this->firstName, $this->surName,$dummyArray,"Waldo","Watson",$dummyVar);
      if($this->output != -1)
      {
          $this->output=$this->output;
          echo $this->output[0] . " ". $this->output[1] . " located with quadratic algorithm!";
      }
      else
      {
          $this->notFound = "Search name not found.";
      }
      echo $this->notFound; 
  }
 
  //Quadratic--Double Loop
  function searchAlgorithm(array $outer,array $inner,array $array3, $keyOut, $keyIn, $var3)
  {
    foreach($outer as $first)
    {
      foreach($inner as $last)
      {
        if($first == $keyOut && $last == $keyIn) 
        {
          $twoNames=array($first,$last);
          return $twoNames;
        }
      }
    }
    return -1;
  }
}
?>

The problem isn’t so much that quadratic algorithms are bad per se, but rather as your N grows, they begin to deteriorate in performance. Why would this be a problem for a PHP programmer? Easy, if you’re using data from a MySQL database. Suppose you have written a program for a client who wants to market to a potential audience of five million, and one of your algorithm classes looks at gender and income that you use to separate out men and women at different income brackets. Out of 5 million, you are able to get 250,000 and you notice your quadratic has slowed down a bit. What’s going to happen if that N doubles from 250,000 to a half million? The order of growth is N²; and so you’re heading to the point where your algorithm will lose effective processing. Had you used a linearithmic algorithm, you would not have to worry about rate of growth of N related to the algorithm because N log N growth is a lot less.

True, the linearithmic algorithms are a bit more challenging to create, but the time you spend working with them is rewarded later as you do not have to tell one of your customers that the software failed because her business plan succeeded and too many of her clients signed into the database!

Cubic: If you ran the cubic example, you may have thought that it didn’t work because it takes so long (compared to the other algorithms) to process and display. The prototype cubic algorithm is a triple loop, and that is what I used. Adding an array of 300 cities in the world with populations of one million or more, it is an example of a triple nested loop and cubic algorithm par excellence. It is slow to begin with and deteriorates as the N increases. It takes longer to find Waldo Watson in a city.

^?View Code PHP


class Cubic implements IStrategy
{  
  private $arrayFactory;
  private $firstName;
  private $surName;
  private $cityName;
  private $output=array();
  private $notFound;
  public function __construct() 
  {
    $this->arrayFactory = new NameFactory();
    $this->firstName=$this->arrayFactory->factoryMethod(new FirstNameProduct());
    $this->surName=$this->arrayFactory->factoryMethod(new SurNameProduct());
    $this->cityName=$this->arrayFactory->factoryMethod(new CityProduct());
 
      $this->output = $this->searchAlgorithm($this->firstName, $this->surName,$this->cityName,"Waldo","Watson","Warsaw");
      if($this->output != -1)
      {
          $this->output=$this->output;
          echo $this->output[0] . " ". $this->output[1] . " from " . $this->output[2] . " finally has been found with a cubic algorithm!";
      }
      else
      {
          $this->notFound = "
Search cube not found.";
      }
      echo $this->notFound; 
  }
 
  //Cubic--Triple Loop
  function searchAlgorithm(array $outer,array $inner,array $places, $keyOut, $keyIn, $city)
  {
    foreach($outer as $first)
    {
      foreach($inner as $last)
      {
        foreach($places as $town)
        {
          if($first == $keyOut && $last == $keyIn && $town == $city) 
          {
            $threeStrings=array($first,$last,$city);
            return $threeStrings;
          }
        }
      }
    }
    return -1;
  }
}
?>

I don’t have an alternative to the cubic algorithm handy, but until you do find one, avoid the cubic algorithm wherever possible.

Exponential: As you saw, I did not provide a code example of an exponential algorithm–it might lock up your computer and server. That does not mean that they should never be used. Rather, it means that unless you have a lot of processing power (or linked computers), you might want to think twice before using one.

Ironically, one use of an exponential algorithm is to lock out robotic attackers attempting to gain access with a random collection of username/password combinations. The time-block algorithm, expressed as,

E(c) = 1/2 * (2(pow,c) – 1)

has an intentionally high order of growth. After about four attempts the lock out time starts to climb to a level that even the most dedicated robot is going to give up and go home. By the 15th attempt, the lockout has increased to over 4.5 hours. It grows exponentially with each attempt. Quickly after 15 failures, the lock-out increases to days, weeks, months and years.

Research into DNA double helixes and processing large-screen high definition graphics are further examples of where exponential algorithms can be found and used. However, for the scope and depth of this blog, they are beyond the pale.

Clients and Context

While this post has been about algorithms, I would be remiss if I failed to say something about the clients (the HTML program and Client class) as well as the Strategy pattern’s Context class.

The HTML is very simple and it’s main job is to pass the name of the concrete strategy class to the PHP Client.

^?View Code HTML




    

Order of Growth Strategies


    Search Family of Algorithms (and wannabes...)
    Select a search algorithm
    
         Constant

         Logarithmic

         Linear

         Linearithmic

         Quadratic

         Cubic

         Exponential
        
    
    feedback

As you can see, the Client has very little work to do in order to pass on the request to the strategy Context class:

^?View Code PHP


error_reporting(E_ALL | E_STRICT);
ini_set("display_errors", 1);
function __autoload($class_name) 
{
    include $class_name . '.php';
}
class Client
{
    private $searchMode;
    private $strategy;
    //constructor function
    public function __construct()
    {
        $this->strategy=$_POST['strategy'];
        $this->searchMode=new Context();
        $this->searchMode->contextInterface(new $this->strategy());
    } 
}
$worker=new Client();
?>

^?View Code PHP


class Context
{
    private $strategyNow;
 
    public function contextInterface(IStrategy $strategy)
    {
        $this->strategyNow=$strategy;
    }
}
?>

According to the Gang of Four, the Context:

is configured with a ConcreteStrategy object
maintains a reference to a Strategy object
may define an interface that lets Strategy access its data (optional)

This context is configured with the implemented IStrategy requested from the HTML UI, and it maintains a referent to IStrategy through the contextInterface(IStrategy $strategy) method. Given the task at hand, there is no reason to define an interface that lets IStrategy access its data in the Context. So we have a Client that is unbound to the concrete implementations of IStrategy, thanks to the Context class. All strategies are handled through the Context. Changes to the strategies will not affect how they are requested from the clients.

Keep it Light

As computers get faster and bigger, we can allow ourselves to pay less attention to algorithms because even quadratic ones can do pretty well. In that respect, we’re just asking for trouble. Those of you who run Raspberry Pis are in a better position to think about algorithms since you have a single core and your computer cannot muscle through a bad algorithm. Typical multi-core computers require extremely bad algorithms before we notice there’s a problem. So, while computers are getting bigger, better and faster, a good algorithm is still a thing of both beauty and necessity. So instead of waiting until your rig cries “Uncle!” give algorithms the attention they need and deserve.

PHP OOP & Algorithms II: What to Use

Search Family of Algorithms (and wannabes...)

0 Responses to “PHP OOP & Algorithms II: What to Use”

Leave a Reply

Recent Posts

Recent Comments

Categories

Meta

Translator

PHP.net News