24. April 2017 20:56

das intervall problem... und funktionale programmierung mit php 5.3

von robert 30. Aug 2009 18:04 (vor 2794 Tagen) ~ comments (0)

vor langer zeit haben wir eine anwendung zur zeiterfassung geschrieben. ein teilproblem war die berechnung von zuschlägen auf grundlage eines umfangreichen tarifpapiers. die zuschläge für wochenendarbeit, nachtarbeit, etc. sollten sich möglichst konfigurieren lassen. beispielsweise in der form startstunde-endstunde priorität beschreibung

0-4 6 nachts
5-10 4 früh
22-24 6 nachts
12-23 9 sonntag

die priorität ist wichtig, weil sich die zeitintervalle überschneiden können. in diesem fall wird der höherwertige aufschlag berechnet, also wer sonntags 22-23 uhr arbeitet bekommt sonntagszuschlag und nicht nachtzuschlag.

ich finde dieses problem recht interessant. es hatte mir damals einiges kopfzerbrechen bereitet. mit den neuen sprachfeatures von php 5.3, den anonymen funktionen und closures, wollte ich mir das problem nochmal neu anschauen und testen inwieweit sich der code damit straffen läßt.

beginnen wir mit den eingabedaten:

$zeiten_def=<<<EDEF
3-8
9-23
EDEF;

$tarif_def=<<<EDEF
0-4 6 nachts
5-10 4 früh
12-13 3 mittags
6-7 8 blubb
14-15 8 blibb
18-22 4 spät
22-24 6 nachts
12-23 9 sonntag
EDEF;

function parse_input($in, $extended=false){
    return array_map(function($line) use($extended){
        $l = preg_split("/[-\s]+/", trim($line), 4);
        $zeiten = array('start'=>$l[0], 'end'=>$l[1]);
        if($extended){
            $zeiten['prio']=$l[2];
            $zeiten['descr']=$l[3];
        }
        return $zeiten;
    }, explode("\n", $in));
}

function p_ival($i){
    $p = ($i['prio']) ? 
        " kategorie {$i['prio']} ({$i['descr']})" : '' ;
    return sprintf("%02d - %02d%s",
        $i['start'], $i['end'], $p);
}

$tarife=parse_input($tarif_def, true);
$zeiten=parse_input($zeiten_def);

usort($tarife, function($a, $b){
    if($a['prio'] > $b['prio']) return -1;
    if($a['prio'] < $b['prio']) return 1;
    return 0;
});

aus den eingabedaten werden listen mit intervallen erzeugt. ein intervall ist ein hash mit den schlüsseln start, end und optional prio und descr. beim einlesen kommt schon ein closure zum einsatz: die array_map funktion nutzt eine anonyme funktion, die zugriff auf den übergeordneten funktionsparameter erhält (use $extended). davon abhängig erzeugt sie die optionalen intervallschlüssel. das ist nice. früher hätte man z.b. einen ähnlichen effekt mit einer globalen variable erzielen können (häßlich).

$tarife wir anschliessend nach priorität sortiert. für den lösungsweg gilt: wer zuerst kommt, malt zuerst. daher diese vorsortierung.

die funktion p_ival() ist eine hilfsfunktion, mit der wir einen intervall anzeigen können.

mit einer generischen lösung wird die arbeitszeit mit den tarifintervallen verglichen. eine vergleichsfunktion gibt die treffer und die nichttreffenden teile zurück. die funktion match_interval() erledigt diese arbeit. sie ist etwas länglich geraten, muss sie doch alle möglichkeiten einzeln testen und die ergebnismengen zusammenstellen. vllt. hat jmd ne idee, wie das kürzer zu machen ist.

function match_interval($needle, $haystack){
    print "TEST ".p_ival($needle)."  VS ".p_ival($haystack)."\n";
    $matched=array(); $unmatched=array();
    // kein match. 
    // ende der nadel vor beginn des heu bzw. 
    // anfang der nadel hinterm heu
    if(($needle['end'] <= $haystack['start']) ||
        ($needle['start'] >= $haystack['end'])){
        $unmatched[]=$needle;
    // nadel direkt im heu
    }elseif(($needle['start']>=$haystack['start']) && 
        ($needle['end'] <= $haystack['end'])){
        $matched[]=$needle;
    // nadel ist größer als das heu
    }elseif(($haystack['start']>$needle['start']) && 
        ($haystack['end'] < $needle['end'])){
        $matched[]=$haystack;
        $unmatched[]=array("start"=>$needle['start'],
            "end"=>$haystack['start']);
        $unmatched[]=array("start"=>$haystack['end'],
            "end"=>$needle['end']);
    // teil der nadel is im heu!
    // ist es der hintere?
    }elseif($needle['end']<=$haystack['end']){
        $matched[]=array("start"=>$haystack['start'],
            "end"=>$needle['end']);
        $unmatched[]=array("start"=>$needle['start'],
            "end"=>$haystack['start']);
    // oder der vordere?
    }else{
        $matched[]=array("start"=>$needle['start'],
            "end"=>$haystack['end']);
        $unmatched[]=array("start"=>$haystack['end'],
            "end"=>$needle['end']);
    }
    // jetzt noch unsere informationen an die
    // fundstelle hängen
    $matched = array_map(function($f) use($haystack){
        $f['prio']=$haystack['prio'];
        $f['descr']=$haystack['descr'];
        return $f;
    }, $matched);
    return array($matched, $unmatched);
}

beim vergleich der intervalle sind also 4 fälle denkbar:

  1. der intervall passt nicht. er wird vollständig als rest zurückgegeben
  2. der intervall passt vollständig in den (gleich großen oder größeren). es wird kein rest zurückgegeben
  3. der intervall passt teilweise (vorne oder hinten). es wird genau ein restintervall zurückgegeben.
  4. der intervall ist größer als der „heu“ intervall. er wird durch das heu gesplittet. es werden 2 reste zurückgegeben.

so, jetzt kommen wir an die stelle, wo der spaß richtig losgeht. wir starten (im einfachsten fall) mit einem intervall (der arbeitszeit) und prüfen es gegen die tarifzeiten. bei jeder prüfung erhalten wir eine neue liste von intervallen, die nicht passen. diese intervalle müssen mit dem rest der liste verglichen werden, während die treffer lediglich gesammelt werden. hier meine erste version:

function match_all_intervals($n, $hay){
    $h = array_shift($hay);
    if(!$h) return array(array(), $n);
    $matched=array();
    $un=array();
    foreach($n as $test){
        list($m, $u) = match_interval($test, $h);
        $matched = array_merge($matched, $m);
        list($m2, $un2)=match_all_intervals($u, $hay);
        $matched=array_merge($matched, $m2);
        $un=array_merge($un, $un2);
    }
    return array($matched, $un);
} 

function p_result($r){
    print "\n\nERGEBNIS zuschlagspflichtige Zeiten:\n";
    print join("\n", array_map("p_ival", $r[0]));
    print "\n   normale zeiten:\n";
    print join("\n", array_map("p_ival", $r[1]));
    print "\n";
}

$r = match_all_intervals_r($zeiten, $tarife);
p_result($r);

diese funktion enthält eine rekursion: list($m2, $un2)=match_all_intervals($u, $hay); der neue rest wird gegen den rest des heuhaufens $hay getestet. die ergebnisse kann man sich mit der p_result() funktion ausgeben lassen.

die foreach schleife kann man auch noch durch eine rekursion ersetzen. das wäre version nummer 2:

function match_all_intervals_r($ns, $hay){
    $mat=array();
    $umat=array();

    $h = array_shift($hay);
    if(!$h) return array(array(), $ns);

    $n = array_shift($ns);
    if(!$n) return array(array(), array());

    list($m, $u) = match_interval($n, $h);
    $mat = array_merge($mat, $m);

    list($m, $u)=match_all_intervals_r($u, $hay);

    $mat=array_merge($mat, $m);
    $umat=$u;

    // hier gehen wir mit den nachbarintervallen ($ns) 
    // original $hay auf den weiter voran
    array_unshift($hay, $h);
    list($m, $u) = match_all_intervals_r($ns, $hay);
    $mat=array_merge($mat, $m);
    $umat = array_merge($umat, $u);

    return array($mat, $umat);
}

$r = match_all_intervals_r($zeiten, $tarife);
p_result($r);

irgendwie ist die funktion garnicht kürzer geworden. ich habe noch etwas mit array_reduce() herumgespielt und bin noch auf diese variante gekommen.

$r = array_reduce($tarife, function($acc, $z){
    $m = $acc['m'];
    $u = array();
    array_map(function($i) use($z, &$m, &$u){
            list($m2, $u2) = match_interval($i, $z);
            $m=array_merge($m, $m2);
            $u=array_merge($u, $u2);
        }, 
        $acc['u']);
    return array('m'=>$m, 'u'=>$u);
}, array("m"=>array(), 'u'=>$zeiten));

p_result(array($r2['m'], $r2['u']));

hmm. 10 zeilen. das ist dann die kürzeste variante. hier kommt eine etwas modfizierte datenstruktur zum einsatz. statt eines arrays [0=>liste_der_treffer, 1=>liste_der_reste] heisst es hier ['m'=>liste_der_treffer, 'u'=>liste_der_reste]

tja. das wars dann schon. evtl. lässt sich das problem noch knackiger lösen. ich bin mir sogar sicher, dass das geht. der geneigte leser möge vorschläge bringen :)


Kommentare

Kommentar
Dein Name *
Deine E-Mail-Adresse * (nur für die Redaktion, wird nicht veröffentlicht!)
Deine Internetseite
Bitte geben Sie den Text auf diesem Bild ein.
captcha image
Angaben für weitere Kommentare merken?
 

About
alotta-log is your friendly blogserver. multiuser - multiblog - php/my/xorc based.

currently this is a beta version. stay tuned.
Impressum
Disclaimer
"this site looks best if you come over here and look at my monitor."
 
Themen
Unser T-Shirt
neueste eintraege in diesem blog
mixtape

1 DJ T / Robot Riot - Electric Press Remix

2 Bucci Bag / More Lemonade - Sparkling Version

3 Soto / Hootenanny - Original Mix

4 Joe Galdo / Keef - Original Mix

5 Myagi / Subversion - Price Cuts Remix

6 DJ Fixx / Electric - Original Mix

7 DJ Fixx / Push Em Up - Original Mix

8 Klaus / Big Man - Original Mix

9 Jesse Saunders / Everybody - Slapin Breaks Remix

10 Soto / Manic - Soto Remix

11 Chikinki / Like It Or Leave It

www.flickr.com
Administration

rss/xml xorc based

alotta-less, 2009