Monthly Archive for June, 2014

PHP OOP & Algorithms I: An Introduction

quadAvoiding the Misinformed

Programmers often spend more time un-doing bad information than using good information. One of the comments that set me off recently was someone “explaining” to others on a blog why PHP was not an object oriented language. Then he continued to blather on about the difference between compiled and interpreted languages. Whether or not a language is compiled or not has nothing to do with whether or not it is an object oriented language. Having interfaces, classes and communication between objects are the key criteria of an OOP language, and certainly since PHP5 has been a full-fledged OOP language. (We PHPers should not feel singled out because I recently saw post where a Java programmer pronounced that neither Python nor Perl were OOP, and she was “informed” otherwise by irate Python programmers. Perl has been OOP since V5.) So here I am again wasting time grumbling about people who don’t know what they’re talking about.

Instead of frothing at the mouth over the misinformed, I decided to spent more time with the well-informed. To renew my acquaintance with algorithms I began reading Algorithms 4th Ed. (2011) by Sedgewick and Wayne. Quickly, I learned some very basic truths about algorithms that had been only vaguely floating around in my head. First and foremost are the following:

Bad programmers worry about the code.
Good programmers worry about data structures and their relationships.
Linus Torvalds (Creator of Linux)

Since we’ve been spending time on this blog acting like good programmers, that was reassuring. In this post, I’d like to look at two things that are important for developing algorithms: 1) What to count as a “cost” in developing algorithms, and 2) Identifying good and bad algorithmic models. First, though, play and download the example. Using two different algorithms, a logarithmic and a linear (both pretty good ones), I’ve added “dots” to loop iterations to visually demonstrate the difference between a logarithmic algorithm (binary search) and a linear algorithm (loop). The “expense” of the algorithm can be seen in the number of dots generated.
PlayDownload

The example is a pretty simple one. However, since this blog is about PHP Design Patterns, I added a little Factory Method. The two algorithm classes act like clients making requests through the factory for a big string array with over 1,000 first names. Figure 1 shows the file diagram:

Figure 1: File diagram for use of Factory Method by two algorithm clients.

Figure 1: File diagram for use of Factory Method by two algorithm clients.

In looking at the file diagram, you may be thinking, “Why didn’t you use a Strategy pattern coupled with that Factory Method?” I thought about it, but then decided you could do it yourself. (Why should I have all the fun?)

Lesson 1: Leave the Bag of Pennies

The first lesson I learned in Bank Robbery 101 was to leave the bag of pennies. They’re just not worth it. Speed is everything in a bank robbery, and so you pay attention to how to get the most with the least time. The same thing applies to analyzing algorithms. For example, an object (as compared to an integer, boolean or string) has an overhead of 16 bytes. I have actually seen posts intoning, “objects are expensive…” Just to be clear,

Objects are not expensive. Iterations are expensive, quadratic algorithms are expensive.

In evaluating an algorithm you need to see how many operations must be completed or the size and nature of the N. An N made of up strings is different than an N made up of Booleans or integers. A quadratic (N²) and cubic (N³) algorithm are among the worst. They’re gobbling up kilo- or megabytes, and so that 16 bytes seems pretty silly to worry about. So instead of seeing an algorithm weight expressed as N² + 84 bytes, you’ll just see it expressed as ~N². (When you see a ~ (tilde) in an algorithm, it denotes ‘approximately.’) Another way of understanding the ~ is to note, They left the bag of pennies.

Lesson 2: Watch out for Nested Loops; they’re Quadratic!

I’ve never liked nested loops, and while I admit that I’ve used them before, I just didn’t like them. They were hard to unwind and refactor, and they always seemed to put a hiccup in the run-time. Now I know why I don’t like them; they’re quadratic.

Quadratic algorithms have the following feature: When the N doubles, the running time increases fourfold.

An easy way to understand the problem with quadradics is to consider a simple matrix or table. Suppose you start with a table of 5 rows and 5 columns. You would create 5² cells—25 cells. Now if you double the number to 10, 10² cells = 100. That’s 4 x 25. Double that 10 to 20 and your have 20² or 400. A nested loop has that same quality as your N increases. If both your inner and outer loop N increases, you’re heading for a massive slowdown.

Algorithms, OOP and Design Patterns are Mutually Exclusive

An important fact to remember is that good algorithms do not guarantee good OOP. Likewise, good OOP does not mean good algorithms. Good algorithms make your code execute more efficiently and effectively. Good OOP makes your programs easier to reuse, update, share and change. Using them together is the ultimate goal of a great program.

Change File Permissions on Raspberry Pi: A Mini Post

raspiFilePermEasy as Pi

When I first found out that I had to change the file permissions to use the Memento implementation that stores data in JSON format, I had to change permissions on my Mac’s localhost, my Linux server and my Raspberry Pi sitting on my LAN. I had not done so before on my Raspberry P,i and I figured that some of those who have Raspberry Pi computers may not have either. I use the Raspbian OS, which is a version of the Debian Linux OS, and these instructions are based on that OS. If you have a different Linux OS or even Unix, the CLI commands in the Root Terminal should work for you as well. (Click below to see the directions for making the changes.)
Continue reading ‘Change File Permissions on Raspberry Pi: A Mini Post’

PHP Memento Design Pattern Part II: Store & Retrieve

mementoWith a Little Help from Our Friends

As you saw in Part I of the Memento Design Pattern post, the design itself is fairly simple; at least judging from the class diagram. Also, in the first example, you saw how a state could be preserved in a Caretaker array and recalled upon request. However, I wanted to use the Memento with a more practical implementation of remembering a previous state to which users could return. For instance, the capacity to remember a choice on a Web page after looking at a series of choices would be an ideal use of the Memento pattern. The idea is to build an encapsulated set of objects that encompasses the UI, and the previous post shows how that can be accomplished. The latest problem encountered using the Memento pattern with PHP is that PHP doesn’t have the necessary UI event handlers, and the UI event handlers in JavaScript, while able to pass data, must do so through a PHP file; not an object.

The result is that each time JavaScript passes a bit of data, it also re-instantiates a class in a file. When that happens, all of the stored states are reset to null. So while the Memento is great at storing data in an array (or scalar for that matter), getting that state back with another call via JavaScript (even if it’s encapsulated in a PHP object) nulls all of the stored states.

So, while JavaScript is OK for handling UI events and passing states to PHP, every state passed resets any saved states because the participants have to be re-instantiated. After trying out different methods, I eventually reached the conclusion that I was going to have to stash the Memento’s current state in a JSON (JavaScript Object Notation) file. PHP includes JSON methods, and while this does not exactly solve the problem of passing data without resetting the state, it can preserve the state stored in a Memento object. Take a look at the example and download the files to see all of the code employed:
PlayDownload

JSON and PHP

For those of you unfamiliar with JSON and PHP, you can find it here in the PHP Manual. As noted, to work with PHP and a Memento design pattern the way I wanted to implement it required that I have some way to provide a persistent record of a “saved state.” In a nutshell, JSON is a faster-loading version of XML with hooks into PHP where data can be exchanged. That is an oversimplification to be sure, but as far as I was concerned if a state could be saved and retrieved quickly when wanted, my requirements would be met. I did not want to involve MySQL, XML or simple text files (even though JSON files [ext .json] are text files). JSON was the fastest in saving and retrieving, and PHP has methods for parsing JSON data.

The Caretaker

If you have not done so already, read Part I of the Memento Design Pattern. That will bring you up to speed on the structure and participants of the Memento design pattern.

The Caretaker participant in the Memento pattern is the warehouse for the saved Memento objects passed through the Originator. Essentially, the Memento is passed to the Caretaker where it is stored until called for retrieval. However, a PHP object cannot be stored as a straight JSON file, and so once the Memento object is passed to the Caretaker (in this example), I passed the Memento value to a JSON file. The second Caretaker method returns the stored JSON value directly to the client rather than re-loading a Memento object and returning it. You can see how this all works in the Caretaker class code:

< ?php
class Caretaker
{
    private $storage;
    private $caretakerStore;
    private $caretakerStorage;
 
    public function addMemento (Memento $m)
    {
        $jsonData["hold"][0] = $m->getState();
        $this->caretakerStore="store.json";
        file_put_contents($this->caretakerStore,json_encode($jsonData,JSON_UNESCAPED_UNICODE));
    }
 
    public function getMemento()
    {
        $this->caretakerStorage = file_get_contents("store.json");
        $jsonData = json_decode($this->caretakerStorage,true);
        $this->storage= $jsonData["hold"][0];
        return $this->storage;
    }
}
?>

The two methods in the Caretaker are pretty straightforward getter/setter ones. The addMemento($m) method expects to receive a Memento object. (The type hint enforces it to.) However, instead of storing the entire Memento as was done in the example in Part I, the Caretaker uses the Memento’s getState() method to access the saved state. Then the state is stored in an associative array element named “hold.” ($jsonData[“hold”][0]). Written to a .json file the saved state might look like the following:

{"hold":["7"]}

The value “7” is the saved string that is used to recall the correct file (dp7.jpg) in the patterns folder. While this might appear to be breaking encapsulation, the value is returned in a Caretaker private property, $this->storage.

To get a better sense of the Caretaker in the context of this particular implementation take a look at Figure 2:

Figure 2: File diagram of Memento used for recalling Web image

Figure 2: File diagram of Memento used for recalling Web image

The PhpCatcher class is an attempt to encapsulate the HTML UI into an object and have methods available to set and retrieve Memento object values using the Caretaker as a warehouse. To set the Memento and send it to the Caretaker, the exact same object communications are used as in Part I. However, the Caretake extracts the value from the Memento and stores it in the .json file instead of in a PHP array that stays extant through UI interactions. So, to recall a Memento value, the PhpCatcher goes directly to the Caretaker’s getMemento() method. (Perhaps a more accurate name for the getter would be getMementoValue().) In any event, at the time of this posting, I was unable to find a way to store the Memento in a JSON object and retrieve it; so the PHPCatcher communicates directly with the Caretaker as a client.

You need to use PHP 5.4+ and you need to set your .json file permissions

  • The PHP built-in JSON methods and constants used require PHP 5.4. If you find it impossible to install 5.4, instead of using JSON, you can use a text file, an XML file or even a MySQL file for storing the Memento value.
  • File permissions are grouped into three categories:

    1. Owner
    2. Group
    3. Everyone

    Further, each permission has three levels:

    1. Read
    2. Write
    3. Execute

    You need to set your .json file so that everyone can read, write and execute the .json file. I set mine for ‘777’ so that all groups and the owner had total access. On your computer or LAN, there’s not a lot to worry about; however, if you are nervous about opening up your .json file to the world on your hosting service, you need to read up on permissions security to see if doing so will cause unwanted problems.

If you’re using a Raspberry Pi, you can find out how to change your permissions for this implementation here.

Continue reading ‘PHP Memento Design Pattern Part II: Store & Retrieve’