Home > Archive > 2010 > December

Algorithmic Advent: 03 – Addressing a multi-dimensional array index by string

This function might come in handy when loading settings from a configuration file.

/**
 * Sets a field of a multi-dimensional array by specifying the key in a
 * flat string format
 *
 * Usage example:
 *
 *   $demo = array();
 *   arraySetByFlatKey($demo, 'this.is.a.test', 'Hello World!');
 *   arraySetByFlatKey($demo, 'this.is.a.monster', 'Brwaaa!');
 *
 * Sets:
 *
 *   $demo['this']['is']['a']['test'] = 'Hello World!';
 *   $demo['this']['is']['a']['monster'] = 'Brwaaa!';
 *
 * @param array $a Array to set the index of
 * @param string $key Flat key representation
 * @param mixed $value Value to set the index to
 */
function arraySetByFlatKey(array &$a, $key, $value, $delimiter = '.')
{
    $keyParts = explode($delimiter, $key);
    $leaveKey = array_pop($keyParts);

    $parent = &$a;

    foreach ($keyParts as $part) {
        if (!isset($parent[$part])) {
            $parent[$part] = array();
        }

        $parent = &$parent[$part];
    }

    $parent[$leaveKey] = $value;
}

Dec 3 2010 • by Marc Ermshaus • type=post language=en php algorithmicadvent • 0 comments

Algorithmic Advent: 02 – Longest intersection of two strings

Hint: If no support for varying character lengths is needed (e. g. when not working with UTF-8), the mb_* function calls should be replaced with their non-multibyte pendants. Especially mb_strpos is very inefficient when used in loops.

/**
 * Returns the longest intersection of two strings
 *
 * Usage example:
 *
 *   $a = 'This is a wonderful test string.';
 *   $b = 'This is another wonderful string.';
 *   var_dump(getLongestIntersection($a, $b)); // string(11) " wonderful "
 * 
 * @param string $haystack First string
 * @param string $needle Second string
 * @return string Longest intersection of both strings
 */
function getLongestIntersection($haystack, $needle)
{
    // Length of needle string
    $nLen      = mb_strlen($needle);

    // Starting point (in needle) of longest matching substring
    $maxAnchor = 0;

    // Length of (so far) longest matching substring
    $maxLen    = 0;

    // Starting point (in needle) of current substring to test
    $sAnchor   = 0;

    // Length of current substring to test
    $sLen      = 0;

    // Do checks until either substring anchor runs out of needle string or
    // until there is no room left for a longer match
    while ($sAnchor < $nLen
        && $sAnchor + $sLen <= $nLen
    ) {
        // Increase substring length
        $sLen++;

        if (mb_strpos($haystack,
                      mb_substr($needle, $sAnchor, $sLen)) !== false
        ) {
            /* Substring found. A new match is always the longest match */

            $maxLen    = $sLen;
            $maxAnchor = $sAnchor;
        } else {
            /* Substring not found */

            // Shift anchor one position to the right
            $sAnchor++;

            // Don't bother looking for substrings shorter than current best
            // match. This makes sure that a new match is always the longest
            // match up to this point
            $sLen--;
        }
    }

    return mb_substr($needle, $maxAnchor, $maxLen);
}

Dec 2 2010 • by Marc Ermshaus • language=en php type=link algorithmicadvent • 0 comments

Algorithmic Advent: 01 – Weighted picks

This is the first entry of a small advent calendar series featuring PHP snippets. Hopefully one or two of them will be useful to anyone.

Today, we start with a function to pick a random entry from a weighted array.

/**
 * Picks an element from a weighted array
 *
 * @param  array $map "Element to weight factor" mappings (<mixed> => <int>)
 * @return mixed|null Picked element or null if empty array
 */
function pick(array $map)
{
    $sum  = array_sum($map);
    $rand = mt_rand(0, $sum - 1);
    $k    = 0;
    $pick = null;

    foreach ($map as $element => $weight) {
        $k += $weight;
        if ($rand < $k) {
            $pick = $element;
            break;
        }
    }

    return $pick;
}

This example will return „c“ in 60 % of the time, „b“ in 30 % and „a“ in 10 %.

$weights = array(
     'a' => 10,
     'b' => 30,
     'c' => 60,
);

for ($i = 0; $i < 50; $i++) {
    echo pick($weights) . ", ";
}

This example simulates the rolling of two 6-sided dice (2d6).

$twoDice = array(
     '2' => 1,
     '3' => 2,
     '4' => 3,
     '5' => 4,
     '6' => 5,
     '7' => 6,
     '8' => 5,
     '9' => 4,
    '10' => 3,
    '11' => 2,
    '12' => 1
);

$results = array();

for ($i = 0; $i < 100; $i++) {
    $pick =  pick($twoDice);
    $results[$pick] .= '*';
}

ksort($results);

foreach ($results as $pick => $amount) {
    echo $pick . ': ' . $amount . '<br />';
}

Dec 1 2010 • by Marc Ermshaus • language=en php type=link algorithmicadvent • 0 comments

Scalar type hints in upcoming PHP version?

Sebastian Bergmann writes that PHP 5.3.99 (which might be released as PHP 5.4) will introduce type hinting for scalar data types (e. g. function f(int $i, string $s) {}).

There is one thing to note: It seems like there are no plans to check or enforce the new type hints in the interpreter, so this feature might be purely syntactical. I am not sure whether this makes a lot of sense to me.

Nov 25 2010 • by Marc Ermshaus • language=en php type=link • 0 comments

Seiteninterne Links und Ausgaben-Escaping: Bitte abstrahieren Sie!

Es gibt einige qualitative Aspekte der PHP-Entwicklung, die in einem Projekt egal welcher Größe eingehalten werden sollten. Dazu zählen syntaktische oder handwerkliche Grundlagen wie E_STRICT-kompatibler Code, der Verzicht auf Short-Tags, die Unterstützung von UTF-8 und das korrekte Behandeln von Magic Quotes. Doch auch auf Ebene des eigentlichen Anwendungsdesigns gibt es etliche simple Kniffe, die unbedingt beachtet werden sollten, weil sie den Umgang mit der Codebasis ungemein erleichtern. Das ist besonders für kleine Projekte interessant, die auf handelsüblichem Webspace laufen sollen, der keine großartigen serverseitigen Konfigurationsmöglichkeiten bietet.

Jedes Projekt sollte zwei Dinge in eigenen Funktionen oder Methoden umsetzen: den Zusammenbau von internen Links und das Escaping von Ausgaben. In beiden Fällen ist die Begründung ähnlich. Wenn interne Verlinkungen hardgecodet werden, ist es kaum möglich, das URL-Schema anzupassen, falls Zugriff auf mod_rewrite oder ähnliche serverseitige Technologien besteht. Wenn als Escape-Funktion überall im Code htmlspecialchars oder htmlentities eingesetzt wird, ist es nicht ohne Veränderung vieler Dateien möglich, das Ausgabe-Encoding des Projekts in einer Weise anzupassen, die einen Wechsel zwischen diesen beiden Funktionen erfordern würde (etwa von ISO-8859-1 zu UTF-8).

Folgende zwei Funktionen sollten in jedem Projekt in irgendeiner Weise implementiert sein:

function url(array $params) {}
function escape($s) {}

Nov 22 2010 • by Marc Ermshaus • type=post language=de php • 0 comments

PHP Snippet: Get all permutations

<?php

/**
 * Returns all possible permutations of $values containing $n elements using a
 * "draw and place back" algorithm
 *
 * The resulting array will always have pow(count($values), $n) entries.
 *
 * For
 *   $values = array('a', 'b') and $n = 2,
 * the result will contain:
 *   [aa, ab, ba, bb]
 *
 * @param array $values Vector to generate permutations of
 * @param int $n Elements per permutation
 * @return array Possible permutations
 */
function getPermutations(array $values, $n)
{
    $rec = function (array $values, &$ret, $n, array $cur = array()) use (&$rec)
    {
        if ($n > 0) {
            foreach ($values as $v) {
                $newCur = $cur;
                $newCur[] = $v;
                $rec($values, $ret, $n - 1, $newCur);
            }
        } else {
            $ret[] = $cur;
        }
    };

    $ret = array();
    $rec($values, $ret, $n);

    return $ret;
}



$values = range('a', 'd');
$n = 2;

$ret = getPermutations($values, $n);

foreach ($ret as $r) {
    foreach ($r as $d) {
        echo $d;
    }
    echo '<br>';
}

Nov 18 2010 • by Marc Ermshaus • type=post language=en php • 0 comments

PHP Template Attribute Language

PHPTAL is a template language that might actually be worth using. From the website:

To be short, PHPTAL is a XML/XHTML template library for PHP.

While most web developpers continue to use ASP/JSP/PHP tags as the core language of their templates, the Zope community came with a refreshing idea named TAL. The idea was to move presentation actions inside XHTML attributes instead of using plain tags or elements.

Nov 17 2010 • by Marc Ermshaus • language=en php type=link • 0 comments

php.de Mitmachquiz: Gästebuch und Kontaktformular

Im php.de-Forum gab es vor einiger Zeit unter der Bezeichnung „Mitmachquiz“ den Versuch, speziell Programmieranfängern eine Gelegenheit zu bieten, in Eigenregie ein vorgegebenes Mini-Projekt umzusetzen. Die Idee dahinter war, im Stile von Code Reviews durch das öffentliche Diskutieren der verschiedenen Lösungen einerseits eine Art „optimaler“ Vorgehensweise für ein oft nachgefragtes Themengebiet herauszuarbeiten und andererseits häufig auftretende Fehler zu erkennen und zu korrigieren. Dies sollte den teilnehmenden Nutzern zu besserem Code verhelfen und für die Zukunft eine Ressource schaffen, auf die andere Nutzer verwiesen werden können.

Die beiden bisher durchgeführten Mitmach-Projekte sind

Leider hielt sich die Resonanz insgesamt, aber gerade die Resonanz unter Programmieranfängern in Grenzen, sodass die eingereichten Lösungen fast ausnahmslos von fortgeschritteneren Programmierern stammen und entsprechend wenig Anlass zur Diskussion bieten, was natürlich nicht im Sinne des Grundgedankens ist.

Hauptsächlich mit der Absicht, die Aktion zu unterstützen, habe ich bei beiden Projekten mitgemacht und jeweils eine Variante eingereicht. Für das Gästebuch existiert ein eigener Diskussionsthread, die Abgabe zum Kontaktformular ist Teil des zugehörigen Hauptthreads. Der Quellcode liegt in beiden Fällen als Repository bei Bitbucket vor (genauere Angaben in den verlinkten Forenposts).

Beide Projekte sind keine Meisterwerke und in vielerlei Hinsicht ausbaufähig, könnten aber dennoch für den ein oder anderen Anfänger einen Blick wert sein. Gleiches gilt natürlich für die beiden Hauptthreads zu den gestellten Projektaufgaben und für die Lösungen der anderen Teilnehmer.

Beim Kontaktformular-Projekt habe ich zusätzlich versucht, eine ausführlichere Dokumentation zum Code zu schreiben. Sie liegt als vorkompiliertes PDF-Dokument vor, ist aber auch in Quellcode-Form (LaTeX) im Repository enthalten. Inhalt und Quellcode können unter der CC-BY-SA-Lizenz frei weiterverwendet werden. Die aktuelle Version richtet sich vor allem an interessierte Anfänger, die über ein solides Grundlagenwissen verfügen und nun in die theoretischeren Aspekte der Projektumsetzung einsteigen möchten.

Es ist insgesamt schade – wenn auch nicht sonderlich überraschend –, dass die Aktion relativ schlecht angenommen wurde. Derlei Angebote sind definitiv unterstützenswert.

Nov 12 2010 • by Marc Ermshaus • type=post language=de php • 0 comments

Developers Shame Day: You've Come a Long Way, Baby

Für heute, den 3. November, hat Cem Derin den Developers Shame Day (oder wie ich sage: DSDS ohne Superstar) angesetzt. An diesem Tag bekommen PHP-Programmierer die Gelegenheit, ein besonders gruseliges Stückchen Code aus der Quarantäne zu holen, um es zum gegenseitigen Amüsement und gewissermaßen als Warnung für kommende Generationen öffentlich im Internet vorzustellen. Klingt verlockend, oder?

Ich frage mich noch immer, was er mit diesem Aufruf zu implizieren versucht.

Kunstpause.

Na ja, jedenfalls hat diese völlig absurde und abwegige Idee in einem vernunft-verspottenden Ausbruch kollektiv-masochistischer Natur dennoch allgemeinen Anklang gefunden, sodass am heutigen Tage allerorts die Codebäume Stilblüten tragen dürften. Ist das schön.

Ich persönlich, der ich nach meiner QBasic-Zeit selbstredend nie wieder auch nur eine einzige Zeile schlechten Code verfasst habe, musste -- in aller Bescheidenheit -- die zurückliegenden Commits von mehreren Tagen durchgehen, um Kandidaten zu finden, die sich in dieses wogende novemberliche Blütenmeer hätten einreihen können. Vorstellen möchte ich allerdings keinen Code von vorgestern, sondern Teile einer Klasse, die laut Repository im Jahre 2005, laut Gefühl irgendwann in den späten 1930ern entstanden ist.

Die Aufgabe dieser Klasse mit dem vielsagenden Namen CParser besteht (natürlich) nicht im Parsen von C-Code, sondern im Umwandeln einer stark BBCode-lastigen Auszeichnunssprache in feinsäuberliches HTML-Markup. Das genaue Vorgehen der Klasse möchte ich dabei zum gegenwärtigen Zeitpunkt als den 700/0-Algorithmus beschreiben, wie in 700 Zeilen Code, gefühlte 0 Zeilen Kommentar.

Den schmutzigeren Details der Implementation kann ich allerdings einen kurzen Lichtblick in Form eines Eingabe/Ausgabe-Beispiels voranstellen.

Eingabe:

[h1]Hallo Welt[/h1]

Hier ist ein Absatz.[fn]

[fnt]Das hier ist eine Fußnote.[/fnt]

Hier ist noch ein [url=http://example.org]Absatz[/url].

Ausgabe:

<h1>Hallo Welt</h1>

<p>Hier ist ein Absatz.<a class="footnote" href="#fn0-1" title="Zu Fu&szlig;note 1 springen"><span class="hide">[</span>1<span class="hide">]</span></a></p>

<p>Hier ist noch ein <a href="http://example.org" title="Zur Seite &quot;http://example.org&quot; wechseln">Absatz</a>.</p>

<div class="footnotes">
  <ul>

    <li><a name="fn0-1" class="footnote" id="fn0-1"><span class="hide">[</span>1<span class="hide">]</span></a> Das hier ist eine Fußnote.</li>
  </ul>
</div>

Na, dagegen sehen die WordPresseseses dieser Welt doch alt aus, das haben wir schon viel schlechter gesehen. Die Parser-Klasse fügt selbsttätig <p>-Tags hinzu und verfügt über einen vorzüglichen Fußnoten-Mechanismus, der es gestattet, die Fußnotenposition [fn] an einer anderen Stelle als den tatsächlichen Fußnotentext [fnt] in den Code zu schreiben. Ich für meinen Teil bin von meinem früheren Selbst schwer beeindruckt.

Noch schwerer beeindruckt wäre ich jedoch von ebenjenem früheren Selbst, wenn die Geschichte auch für diejenigen Eingaben funktionieren würde, für die sie dann nämlich in der Tat nicht mehr funktioniert. Das sind leider so ziemlich alle. Folgen die Eingaben nicht einer genau ausbalancierten Reihenfolge oder ist die BBCode-Struktur gar fehlerhaft, läuft irgendwo in den 700 unkommentierten Codezeilen etwas schief und die erzeugte HTML-Ausgabe wird witzig und kunstvoll anzusehen, aber leider nicht richtig.

Daraus lassen sich drei wesentliche Versäumnisse ableiten.

  1. Es wurde versäumt, irgendeine Art von Fehlerbehandlung zu schreiben. Der Code enthält schlicht und ergreifend keine Logik dazu. Es gibt keine Exceptions, es gibt keine Rückgaben von Fehlerwerten. Sobald ein unerwarteter Zustand auftritt, passiert ein klar definiertes Irgendwas.
  2. Es wurde zudem versäumt, den Code sinnvoll zu strukturieren. Die Klasse CParser ist im Grunde ein God object, das nichts weiter tut, als prinzipiell prozeduralen Programmierstil in einem Objekt zu verpacken. Dieses Objekt dient dann strenggenommen nur als Namespace, nicht aber als Teil einer OOP-Hierarchie. Features wie die Fußnoten-Logik wurden nachträglich in den bestehenden Code gehackt und sind entsprechend schwach integriert und blähen die vorhandenen Methoden mit Spezialfällen auf, statt sich irgendeiner definierten Schnittstelle unterzuordnen.
  3. All das macht die Klasse nahezu untestbar, da einzelne Funktionen nicht losgelöst vom Ganzen betrachtet werden können. Einige Methoden sind zudem mit einer Länge von 80 oder sogar 130 Zeilen voller if-Konstrukte ein klarer Indikator dafür, wo Funktionalität in weitere Klassen abstrahiert werden müsste.

Diese drei, mit den bereits erwähnten fehlenden Kommentaren vier, Punkte sind ein sicherer Weg, jeden Code auf Designebene vor die Wand zu fahren, sobald ein gewisser Grad an Komplexität erreicht wird. Die eingesetzten Algorithmen können dabei noch so gut und fehlerfrei sein, irgendwann bricht das Code-Gebilde gewissermaßen unter seinem eigenen Gewicht zusammen, weil die Übersicht verloren geht und weil auftretende Bugs nur noch sehr schwer überhaupt zu lokalisieren, geschweige denn zu beheben sind.

Zur Verdeutlichung des Elends zeige ich beispielhaft die ParseEx-Methode, die den äußeren Wrapper des Markup-Parsers darstellt, in der Originalversion von 1930. Der restliche Code sieht ungefähr genauso aus.

/*
*/
function ParseEx($s) {
    $this->PrepareString($s);
    $ret = "";
    $i = 0;

    if ($s == "") return;

    $this->GetNextTag($s, $i, $j, $tag);

    // Add <p> if source contains no tags or does not start with outline tag
    if ((!($j == 0)) || ($j === FALSE) )$ret .= "\n\n<p>";
    else if ((!($j === FALSE)) && (array_search($this->GetTagName($tag), $this->m_outline_tags) === FALSE))
      $ret .= "\n\n<p>";

    while (!($j === FALSE)) {
        $tag_content = "";
        $has_content = FALSE;
        $previous_text = trim($this->FormatString(substr($s, $i, $j - $i)));
        $ret .= $this->FormatString(substr($s, $i, $j - $i));
        if ($this->GetIsTag($tag)) {
            if (!($this->GetIsClosingTag($tag))) {

                /*
                    Opening Tag
                */

                if (!(array_search($this->GetTagName($tag), $this->m_outline_tags) === FALSE)) {

                    // Add </p> if opening outline tag does not follow closing outline tag
                    if ((!($j == 0)) && ((array_search($previous_tag_name, $this->m_outline_tags) === FALSE)||(!($previous_text == ""))))
                    {
                        $ret = trim($ret);
                        $ret .= "</p>\n\n";
                    }

                    $tag_content = $this->GetTagContent($s, $j, $tag);
                    $has_content = TRUE;
                    $this->DebugAdd("Tag Content: $tag_content\n");
                }
                elseif ($this->GetTagName($tag) == "fnt") {
                    $tag_content = $this->GetTagContent($s, $j, $tag);
                    $has_content = TRUE;
                    $this->DebugAdd("Tag Content: $tag_content\n");
                }
                elseif (array_search($this->GetTagName($tag), $this->m_single_tags) === FALSE) {
                    $this->AddToStack($tag);
                }

                $ret .= $this->AddCode($tag, TRUE, $tag_content);

                if (($has_content) && (!($this->GetTagName($tag) == "fnt"))) {
                    /* Add Paragraph: Closing outline tag but not fnt */

                    // Get next tag
                    $this->GetNextTag($s, $j, $tag_pos, $next_tag, FALSE);

                    $next_tag_name = $this->GetTagName($next_tag);

                    if (!($tag_pos === FALSE))
                    {
                        $str_between = substr($s, $j, $tag_pos - $j);
                        $str_trimmed = ltrim($str_between);

                        if (  (!($str_trimmed == "")) || (array_search($next_tag_name, $this->m_outline_tags) === FALSE) )
                        {
                            $ret .= "\n\n<p>";
                            $j += strlen($str_between) - strlen($str_trimmed);
                        }

                    }
                    else
                    {
                        $str_trimmed = trim(substr($s, $j));
                        if (!($str_trimmed=="")) $ret .= "\n\n<p>";
                    }
                }

            } else {
                /*
                    Closing Tag (with closing tag behaviour)
                */

                $ret .= $this->AddCode($tag, FALSE);
                $this->RemoveFromStack($tag);
            }
            $previous_tag_name = $this->GetTagName($tag);
        }
        else
          $ret .= $this->FormatString($tag);

        if (!$has_content)
          $i = $j + strlen($tag);
        else
          $i = $j;

        $this->GetNextTag($s, $i, $j, $tag);
    }

    // Restlichen Text anfügen und unter Umständen den letzten Absatz schließen

    $str_end = substr($s, $i);
    if ((!($str_end == "")) && ($this->GetIsOutlineTag($previous_tag_name)))
    {
        $i = 0;
        while ((($str_end[$i] == "\n") || ($str_end[$i] == "\r")) && ($i < strlen($str_end)) )
          $i++;
        $str_end = substr($str_end, $i);
    }

    if (!trim(($str_end == "")))
    {
        $ret .= $this->FormatString($str_end);
        $ret = trim($ret);
        $ret .= "</p>\n\n";
    }
    else if (!$this->GetIsOutlineTag($previous_tag_name))
    {
        $ret = trim($ret);
        $ret .= "</p>\n\n";
    }

    /*
        BAD SOLUTION FOR PARAGRAPH PROBLEM
    */
    $ret = $this->SolveParagraphs($ret);

    return $ret;
}

Alles klar, oder?

Ein auf diese Weise organisch gewachsener Code widersetzt sich in aller Regel sehr erfolgreich dem Versuch des Zurechtstutzens und wuchert munter in alle Richtungen weiter. Da hilft meist nur noch die radikale Variante, den entsprechenden Programmteil völlig neu und hoffentlich durchdachter zu konzipieren.

Einige Hinweise dazu:

  • Eine Methode sollte eine klar definierte Funktion erfüllen. Sie sollte zu einer eindeutigen Eingabe eine eindeutige Ausgabe erzeugen und so wenige Seiteneffekte (etwa das Manipulieren von Instanzvariablen) wie möglich verursachen.
  • Jeder mehrfach vorkommende Code sollte als Methode ausgelagert werden. Don't repeat yourself. Dazu gab es im Software-Entwickler Blog kürzlich einen Artikel.
  • Gleichartige Funktionalität sollte in zusätzliche Klassen ausgelagert werden. Der Beispielcode oben sollte etwa einen Aufruf wie $tag->getName() enthalten statt $this->GetTagName($tag).
  • Kommentare und vor allem auch frühzeitig konzipierte Tests helfen dabei, den Umfang einer Methode oder Klasse nicht aus dem Ruder laufen zu lassen, weil sie den Programmierer zur Reflexion über den geschriebenen Code zwingen.

So, ich werde den Code jetzt in eine Lochkarte stanzen und ans Nixdorf-Museum schicken oder alternativ in den nächsten Ententeich werfen.

Nov 3 2010 • by Marc Ermshaus • type=post language=de php • 0 comments

Installing the Zend Framework into the document root

The Zend Framework's default directory layout assumes that you are able to place all of your library and application code outside of the web server's document root directory. In shared hosting environments, this is often impossible because the document root is the topmost directory you have access to.

Lorenzo Alberton explains how to setup the framework under these conditions.

Nov 1 2010 • by Marc Ermshaus • language=en php type=link • 0 comments

Info

Tag cloud

  • en (296)
  • link (257)
  • post (46)
  • php (44)
  • photography (27)
  • music (26)
  • art (25)
  • algorithmicadvent (24)
  • video (22)
  • programming (18)
  • lifeimprovement (14)
  • de (12)
  • youtube (9)
  • thecloud (9)
  • humour (7)
  • flickr (6)
  • lists (6)
  • webdesign (5)
  • psychology (5)
  • free (5)

Archive

/blog/archive