cip labs

Some time ago, I thought about that it would nice to have a smart piece of code, that calculates the result of a given formula. The next step, I thought about, was to integrate customized functions into the code. So, I wrote a parser, that is able to do all this things. This article deals with this parser and how you can work with it. The code is really easy to understand and the parser is easy to use.

First considerations

At first you have to consider some classes, that are able to abstract all the structures you need.

class Morphem

A morphem is the atomic part of every language. In our case, a morphem represents the tokens of a formal language, for instance:

(, ), +, -, *, /, sin, cos, tan, sqrt, exp, ln, log10, -912, 12

The morphem class represents a morphem, after the lexer has detected it.

class Lexer

The lexer has the job to detect morphems in the formula. With some simple rules, the lexer detects every morphem from the left to the right:

• FVAL – function value like (sin, cos, log)
• DVAL – double value like (1.4, 3.1, 5, 7, 11.11)
• CVAL – character value like (+,(,),-)
• NOVAL – no value, tokens that are not defined
• FINISHED – the lexer finished with ‘\0′ in the string

This class returns the current morphem to the parser. The parser uses this morphem, to calculate the result of your formula with the rules of the grammar.

class Parser

An important part of a good working parser is a good grammar. In this case, I choose a case-sensitive grammar. A grammar is a formal construct, to define, how a language is structured. In this case, the language represents all valid formulas. The following grammar was used in the code:

E -> T | T + E | T - E
T -> F | F * T | F / T
F -> (E) | N | -N | sqrt(E) | sin(E) | cos(E) | tan(E) | exp(E) | ln(E) | log10(E)
N -> I | I .D
I  -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1I | 2I | 3I | 4I | 5I | 6I | 7I | 8I | 9I
D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0D | 1D | 2D | 3D | 4D | 5D | 6D | 7D | 8D | 9D

This grammar is realized in the parser class. The customized functions, that you can integrate into the parser comes in at F. Here are laying your functions.

HowTo work with

Here you can see a simple example, that should match all cases of application.

First example

require 'Parser.class.php';
$parser = new Parser('sin(4)+cos(4)');
$result = $parser->run();
echo 'result is: ' , $result , PHP_EOL;
//outputs
result is: -1.4104461161715

As you can see in the example above, it is really easy to use the parser. You just have to type in the formula that you want to parse and nothing more.

The parser knows some functions by default:

• sqrt(x) square root of x
• exp(x) – e^x
• sin(x) – sinus of x
• tan(x) – tangens of x
• cos(x) – cosinus of x
• log10(x) – logarithm base 10 of x
• log(x) – logarithm naturalis of x

So, it isn’t a problem for the parser to calculate:

(3*sin(5*cos(3))+1+ln(sin(3)))/sqrt(2)

source: wolframalpha.com

which is (output from the parser): 1.3842259196509

Extending functionality

Sure, I built in some functions, that are important for mathematical calculations, but maybe you want some more functions, to serve your needs. That is no problem:

require_once 'Parser.class.php';

function divide2($x){
return $x = $x / 2;
}

function plusRandom($x){
return $x + rand(0,10);
}

$parser = new Parser('div2(sin(pr(1)))');
$parser->addFunction('div2', 'divide2');
$parser->addFunction('pr', 'plusRandom');
echo $parser->run();
//outputs the sinus from a number from a random number in the scope of 1-11 divided by 2

Note: Every function must have one argument (not more and not less).

Symbol table

The symbol table includes all functions that you had added or where built-in. I kept this structure static, so that a new parser object has access to it. Furthermore the parser needs this structure static, because in some cases we are starting a new parser recursively. The table is an array of the lexer class and you can access it with:

Lexer::$_userFunctions[$name_in_formula] = $real_function_name;

Using the calculator

May you want to calculate a series of results for one formula, to draw a graph in a coordinate system or to simply calculate a series of results from a formula with a variable. Then you should use the Calculator.

$calc = new Calculator();
$calc->options('{x}', 0, 10, 0.5);
$calc->addFunction('div2','divide2');
print_r($calc->calculate('sin({x})+cos({x})');

The calculator runs the formula with the variable {x} starts with 0 and runs up to 10 with the step rate of 0.5. That means, the calculator runs for {x} = 0, {x} = 0.5, {x} = 1.0, {x} = 1.5 …. {x} = 10.0. The keys of the result array are the current step and the values are the result of the calculation.

Wishlist

On my wishlist for this further development of this project:

• n ^ m
• n!
• n % m
• functions with more then one parameter

Get it!

You can download the files on the project page. There I will create a little documentation of the code for some hacking fun. Maybe you found it interesting to work with this little tool. So, please let me know and write a comment or a mail. I would really like to get some feedback and wishes, that I can add to the code.

goto: download

goto: project page

Some month ago, I came out with an article about Benfords Law. This article deals with the summation and product formula based implementation in C. The algorithm is indeed cool for small statistical games, but not nice to use, when you have a set of numbers.

So, I developed a small class, that serves this need. Furthermore, this class is able to calculate the geometrical, harmonical and quadratical averages.

After including (require, include) this class, you can create a new object with

$benford = new Benford(array(1341,82,141,215), 10);

The first parameter is the array with the values to calculate. The second parameter is the basis of the number system. This parameter is 10 by default. (10 means a normal number system from 0..9). You can add more values with:

$benford->addValue(array(9,128,412));

or simply:

$benford->addValue(3222);

After that, you have two options:

You can perform a run through the given set of numbers and get back the values of the Benford calculation. The second option is to use an average function. When calling an average function, the run()-function will be also called internally.

Get back an array with the Benford calculation:

$benford = new Benford(array(232, 211, 410, 301, 508, 192));

$result = $benford->run();

This returns an array with all the Benford results from the given data. Below you can see the code to perform the average functions.

$benford = new Benford(array(232, 211, 410, 301, 508, 192)); 

$result_harm = $benford->getHarmonicalAverage();

$result_geom = $benford->getGeometricalAverage();

$result_quad = $benford->getQuadrateAverage();

The script is very easy to use. Have fun with it!

Download the source file.

A few weeks ago, I wrote an article about an implementation of a DFA (deterministic finite automaton) in PHP. Today, I present a implementation for an automaton, that is not deterministic. It means, that the automaton have no, one or more than one edges (for an element from the input alphabet) to an other state. Before I start to give you a launch into how the NFA in PHP works, I give you a short introduction into the theory of nondeterministic finite automata.

To demonstrate an easy example, I use a NFA, that accepts a word, which includes the substring ‘abc’. I used this example also in a previous article (about DFAs). You can compare the following automaton with the DFA that accepts the same words and you would come to the conclusion, that the NFA is easier to build. Thats the truth, but on the other hand, in most (not all) cases the NFA needs more time to execute all simultanous calculations for a token from the alphabet.

An automaton needs (for formal description) an input alphabet. For that example, the alphabet is specified as:

for this example:
Σ = {a,b,c}

A few sentences ago i mentioned, that the NFA needs more time to execute all simultanous calculations. But why? Well, let us choose the input word ‘ccababca’. (For further demonstrations I will use s1, s2, s3 and s4 as names for the states [blue circle] from the left to the right) We start the simulation with the first two tokens ‘cc’. The NFA remains in s1 (state 1). After that the NFA simulates for the token ‘a’. In s1 with input ‘a’ the NFA can go to s2 and can also stay in s1 (self-loop). Here we have the main problem! The NFA simulates all possible calculations and that is the problem, that the NFA has. After token ‘a’ comes token ‘b’ and for that token, the NFA simulates s1 and s3.

The PHP implementation of the NFA works with the transition table of every state. Outward from the starting state(s), the algorithm is looking for a transition from the current state to another – the successor state. After the input word was read, the NFA checks whether it is currently in a final state or not. The formalization of a final state is defined with a thicker border line (as you can see in the sketch above the text). In the PHP implementation it is just a boolean value. You can also choose more than one starting states with:

$nfa = new NFA('test_nfa');
//adding new states
//declare starting states
$nfa->setStartingStates(array('s0','s1'));

The function, explained below, is very important to build NFA’s – but not neccessary. In the code example below, we don’t need this function, therefore it has an own example above.

The code example shows the code fragment, that has the equal functionality as the automaton in the sketch.

require 'NFA.class.php';

$nfa = new NFA('test_nfa');

$s1 = new NFA_State('s1');
$s1->setTransition('b', 's1');
$s1->setTransition('c', 's1');
$s1->setTransition('a', 's2');
$s1->setTransition('a', 's1');
$nfa->setState($s1);

$s2 = new NFA_State('s2');
$s2->setTransition('b', 's3');
$nfa->setState($s2);

$s3 = new NFA_State('s3');
$s3->setTransition('c', 's4');
$nfa->setState($s3); 

$s4 = new NFA_State('s4');
$s4->setTransition('c', 's4');
$s4->setTransition('b', 's4');
$s4->setTransition('a', 's4');
$s4->setFinal(true);
$nfa->setState($s4);

$nfa->setStartingState('s1');

if($nfa->run('accbbababcababa'))
  echo "NFA accepts the input word!";
else
  echo "NFA doesn't accept the input word!";

As you can see in this example, the NFA equals a pattern matcher. With a regular expression parser you are able to build small NFA’s for every part of this expressions. After that you can concatenate this automatons to an automaton, that accepts your complete expression.

You can download the source files here. (NFA.class.php, NFA_State.class.php and test.php)

An important area of the theoretical computer science deals with finite automata and languages. We use a finite automaton to detect words of regular languages. The types of grammars that create a language are defined in the CHOMSKY-hierachy (Noam Chomsky). The table below shows the CHOMSKY-hierachy:

To represent a regular grammar (type 3) you can use for instance a finite automaton. Here we are using a DFA (deterministic finite automaton) to display a regular grammar. A DFA consists of states and the automaton can reach a new state with a edge to another state (states are a kind of nodes or vertexes). Every state has a successor state for all tokens of the input alphabet. This input alphabet is specified:

for this example:

Σ = {a,b,c}

The DFA in the example below accepts all words that contain the sub string ‘abc’:

The circle represents a state and the edge represents the input of a token from the input word. The state, which is marked bold, is called the final state. If all tokens of the input word were inputted into the automaton (no token was left) and the automaton is currently in a final state, then the word was accepted from the DFA.

A formal definition of a DFA:

M = (Z, Σ, δ, s0, E)

• Z… a finite set of states
• Σ… the input symbols (alphabet)
• δ… transition function (δ: Q x Σ → Q)
• s0… start state (s0 ∈ Q)
• E… a finite set of final states (E ⊆ Q)

The implementation in PHP based on the transition function / transition table of the DFA. The run()-method uses this table to calculate the successor state of every token in every state.
After all tokens are inputted, the run()-method checks, whether the current state is a final state or not. Running run() with true as the second argument, then the function will return the path through the automaton. Using this method with false as second parameter, the return value is boolean (true for success | false for “word isn’t in that language”).

Below you can see the DFA, that accepts only words with an ‘abc’ sub string (from the example), as PHP code:

$dfa = new DFA('test_dfa');

$z0 = new DFA_State('z0');
$z0->setTransition('b', 'z0');
$z0->setTransition('c', 'z0');
$z0->setTransition('a', 'z1');
$dfa->setState($z0);

$z1 = new DFA_State('z1');
$z1->setTransition('b', 'z2');
$z1->setTransition('a', 'z1');
$z1->setTransition('c', 'z0');
$dfa->setState($z1);

$z2 = new DFA_State('z2');
$z2->setTransition('c', 'zE');
$z2->setTransition('b', 'z0');
$z2->setTransition('a', 'z1');
$dfa->setState($z2); 

$zE = new DFA_State('zE');
$zE->setTransition('c', 'zE');
$zE->setTransition('b', 'zE');
$zE->setTransition('a', 'zE');

//to set zE as a final state
$zE->setFinal(true);
$dfa->setState($zE);

$dfa->setStartingState('z0');

$result = $dfa->run('accbbababcababa', true);

goto: download (DFA.class.php, DFA_State.php & test.php)

This short article i have focused on a special field of PHP optimization. It deals with the php.ini.

The php.ini file is the configuration file of PHP. It contains directives and settings, that affect the execution of the PHP script. The possible modifcations, that you can do to increase the speed of execution, are very special. You have to decide which of the settings, that are listed below, seems wise to you and your application. This article is a part of the web-application performance series.

realpath_cache_size & realpath_cache_ttl

PHP uses a realpath-cache to cache the path of include/required-files. This cache was introduced in PHP 5.10 and brought a high improvement of speed into PHP. The default value should be 16K, which is a really good ratio.

register_globals

The default value since PHP 4.2.0 is set to Off, nevertheless you should convince yourself, that this value isn’t  set to On. On the one hand, register_globals are well known as a big security issue and on the other hand PHP creates all variables in $_GET, $_POST, $_COOKIE, $_REQUEST, $_SERVER and $_SESSION in register_globals variables, too. This costs a unnecessary amount of time!

always_populate_raw_post_data

Is always_populate_raw_post_data set to On, PHP fills $HTTP_RAW_POST_DATA with raw data, that comes in with POST. Turn this directive to Off,  if you’re not planning something special with it. It saves time and memory.

register_long_arrays

This directive copies all data into the outdated $HTTP_*_VARS. You can access this data for instance with $_GET. You should turn register_long_arrays to Off to save time and memory.

expose_php

To tell the webserver which version of PHP is installed, PHP sends an information string to the webserver. Set this directive to Off, to avoid an unnecessary string copy. In addition to that, it is safer to tell just the necessary information and not more.

register_argc_argv

If you are using your PHP scripts with a webserver, then you don’t need argc (number of command line arguments) and argv (array that contains the command line arguments). Is register_argc_argv set to On, then PHP tries to parse and copy this variables into the symbol table of the script. This takes unnecessary time. Turn it to Off to save time.

asp_tags

The asp_tags directive points out, that the PHP detects also ASP tags like <% and %>. It’s not best practice to use ASP tags in PHP scripts. If you don’t use these tags, you should turn Off the asp_tags directive to save time.

This article deals with some PHP code optimizations. The list of tipps & tricks  is not complete at all and i will try to add more tests. I did this tests on windows and linux environments to make safe that the results are rough valid. It’s really important for a good PHP developer that he or she is aware of some performance aspects of the code. The following tipps are a best practice example of coding smart PHP code. This article is a part of the web-application performance series.

Echo vs. print and concatenation

The comparison of the two output options is the oldest of the PHP-scene. It’s wrong to assert that echo ist faster than print because of the procedural overhead that the print instruction produces. These two instructions are both builtin-constructions of the PHP-language and not, as often assumed, print is a function and echo a language-construct. The only difference versus echo and print is, that echo has no return value but print returns always 1 (see: manual). The next Problem is the often unknown difference between outputing a couple of substrings with echo and concatenate substrings to a longer string. The first operation runs with the commata operator and the second one with the point operator. It’s the normal case to use echo with the point-operator, but it’s not best practice.

$str1 = “Test1“;
$str2 = “Test2“;

echo “Hello world, this is “ . $str1 . “  & “ . $str2 . "!";

If you have long sub strings, then your concatenation will take a very long time. Below you can see the best practice example:

$str1 = “Test1“;

$str2 = “Test2“;

echo “Hello world, this is “ , $str1 , “  & “ , $str2,"!";

Quotes

The myth of optimizing quotes is often not welcome in the PHP-community, but the benchmark-tests shows us, that single quotes are a bit faster than double quotes. The reason is, that the parser is looking for variables which could possibly be in there. And this process takes more time, than the simple text parsing. You should use double quotes only in the case, that you want to put variables in the string.

Search strings

We compared strstr() and strpos() with each other. The task is to find a substring in a string. Below you can see the two scenarios:

$sub = '@';

$str = 'mailme@example.com';

//the first way

if(strstr($str, $sub) !== FALSE) echo 'found';

else echo 'not found';

//the second way

if(strpos($str, $sub) !== FALSE) echo 'found';

else echo 'not found';

After testing these two ways in a loop, i noticed that strpos() works faster and uses less memory than strstr().

Comparison of the starting characters

To compare the first n token of two strings, you have 2 options. You can use strncmp() with is the smarter one or you can use substr(). The result should be clear. With just one PHP function call the script performs faster. The best practice scenario is strncmp():

$str1 = 'Teststring1;

$str2 = 'Test_string1';

$len = 4; //compare the first 4 tokens

if(strncmp($str1, $str2, $len) === 0) return true;

else return false;

if(substr($str1,0,$len) == substr($str2,0,$len)) return true;

else return false;

The result of the test shows that strncmp() is faster than the substr() alternative. The advantage of using strncmp() inceases with the length of the string. Another scenario could be, to use strpos(…) like strncmp() to compare the starting characters. I did this test and the result points out that strncmp() was faster than strpos() (but not significant).

Counting operations (count(), sizeof() und strlen())

If you want to know the number of elements in an array to work with it, you can use the sizeof() (or count()) method to get it. It’s often used, but not best practice , to implement these methods in the condition area of loops. It would be better to get the number of elements before the loop starts. Otherwise you count the elements in every single iteration. Note, that count() is faster than sizeof(). The reason is, that sizeof() is just a synonym of count().

//wrong way

for($i = 0; $i < count($arr); $i++){

//magic

}

//right way

$size = count($arr);

for($i = 0; $i < $size; $i++){ //magic }

Read loops and modify loops

Often, you have to modify data in complex structures , such an array. Here you can use the foreach()-construction of PHP. Beware, that the performance of this code depends on the operation that you want to perform. After testing a set of operations (reading, modifying, unset) i noticed, that read-operations perform better with foreach(). The modification of an array works better with the for-loop. The reason is, that PHP does more hash-lookups, if you use it with foreach() and $key => $value. Note, that this loop performs faster if you get $value by reference.

//best practice for reading

foreach($arr as  &$value){

//magic with $value

}

To modify an array you should use something like this.

//best practice for modification

$keys = array_keys($arr);

$c = count($keys);

for($i = 0; $i < $c; $i++){

//magic with $arr[$keys[$i]]

}

Testing array index

To find out whether a array index exists or not you can use the in_array() function or the isset() function.  The in_array() function expects two parameters. The first parameter is the $needle (the index to find) and the second one is $haystack (array). PHP searches into $haystack for $needle. The isset() function ( just expects the variable) simply searches in the symbol table whether this index is set or not.

in_array('test', $array);
isset($array['test']);

I found out that isset() is faster than in_array(). Do not think, that this improvement isn’t significant. The speed improvement increases proportionally with the size of the array.

File handling

You have more than one option to perform file handling in PHP. A simple read from a file can be performed by file() and file_get_contents(). Be aware that the first one returns just an array with all rows. You have to implode this array with a glue (e.g. a whitespace) to use it as a string. The second function returns exactly this string. In most cases you need the content as a string. Use file_get_contents() to do this work. It is more than 200% faster (depends on length). If you need the rows to do your task, then it would be faster to use the file() function.

Replacing strings

If you want to replace strings in PHP you can use str_replace() and preg_replace(). For simple patterns you should use str_replace(). This function is much faster than preg_replace() because it works stupid and simple. But beware,that preg_replace() is much faster, if you have a complex pattern. One call to preg_replace() is smarter than 2 or more calls to str_replace().

Constants & configuration

Defining global constants is a mighty method for large web applications to bring some flexibility into it. To realize this, PHP implements a method called define(). Since PHP supports OOP you can define constants in classes. This method is not only better structured but also faster than the define() alternative. It’s more comfortable to build a configuration class, that contains all constants.

//old way

define('DB_HOST', 'localhost');

define('DB_USER', 'mysql');

define('DB_PW', '**************');

define('DB_DB', 'application');

//other way

class DB{

const HOST = 'localhost';

const USER = 'mysql';

const PW = '**************';

const DB = 'application';

}

Statistical probability (LazyEnd)

Sometimes you have to do some decisions about the program flow of your application. Here you would have a significant increase on performance if you let the parser perform the small functions, before it performs the expensive functions.

if(expensive_function() || small_function()){

//magic

}

//is significant slower than

if(small_function() || expensive_function()){

//magic

}

But why? The parser performs from the left to the right. When the function on the left returns true, then the complete condition becomes true. The parser don’t execute the second function, because it is not necessary. This works for logical AND too. Put the small function or the fastest expression on the left site. In the case of the logical AND becomes the complete condition wrong, if one expression is wrong.

Another statistical optimization aspect is to consider well about the structure of if-else and switch instructions. You should keep the conditions, that are most likely, on top of you if/else or switch construct, to avoid work and save time.

If vs. switch vs. ternary operations

The general opinion about If vs. Switch is, that the If/else construct have a better implementation and therefore it performs faster. I tried to get light into the dark with browsing the code and the internals of PHP. It’s right, that the If/else implementation looks smarter and so i can confirm the general opinion. But there is a construct that works faster than If/else and it’s called ternary operations. Below i listed an example of the simple usage of a tenary operation (a smarter handling of If/else):

return ($condition)? $if_value : $else_value;

Increment operations

To increment an integer variable (e.g. during a loop iteration) you have a few options. For that, PHP provides the pre- and post-increment operator. Here we put the light on the performance of this operators. The fastest method is to use the pre-increment ++$i, because the first step is the increment and after that PHP returns the new value. This is done in approx. 1 cycle. The second-fastest is the post-increment $i++. Here, PHP uses another procedure to handle this. And the third-fastest is the normal assignment, because PHP can add, divide, etc. and with a variable or a number. That makes this operation trickier and even slower for the execution.

goto: project page

goto: download version 1.0.0

For a long time I’m really intrested in performance aspects of content management systems and smarter blogging systems and that’s the reason for the decision to test some of the popular systems on a workbench and to get some technical information about these systems. The test was quite simple. I installed the packages on my sandbox server and added a function (cip-bench()) to the installation. Then I run the index page with the default template and configuration. The data I got from the test was limited on the raw index page after the installation. I picked up 5 aspects for the test. The first one was the memory usage of the system, the execution time, executed database queries, how many database tables exist and the last parameter shows how many files are required. It is interesting to see how different some CMS solve their tasks. I was suprised of some results for example 399 database queries of contenido.

To sum up this test I was impressed by chyrp. It’s delivered with an elegant backend and I think it has got a lot of potential to become more popular and famous. The memory usage of wordpress seems to be improved in contrast to previous versions.

blog

cms

Nearly every web-application needs a professional framework that provides functionality, scalability and useful utilities for creating and extending  good code. At cip-labs I use an inhouse framework for creating web projects. While working on several projects, I extend this lightweight framework with useful features. Now, it’s just in development stage and some features are not ready to post it on the blog, but time after time I will release some parts of the framework to the public.

The first on the blog and latest part in the framework itself is the floraPHP string library. The library contains useful functions (procedural style) to do string manipulation in PHP. PHP delivers some built-in functions, but for intensive string handling it’s not enough.

With this library you can e.g. analyze datatypes of word sof a given string, calcute average sentence and word length, check whether $needle is a word in $haystack, use a more flexible sub string function and so on.

goto: floraPHP string library project page

goto: floraPHP project page

Today, we want to introduce you to trim-me.com. Trim-me is a web-service that shortens your long links to the minimum. At the moment TM is just in a beta-state, but we work on a final version that contains any statistic functions and support for the Internet Explorer.

You can use trim-me to cut your links for twitter, facebook, icq or other services.

Visit: trim-me.com