Algorithmus zum Nachschlagen des Datumsbereichs basierend auf Ereignisdatum

Question

Ich schreibe eine PHP-Funktion, die eine Tabelle der Arten verwenden würde, um zu suchen, welcher DB-Shard die Anwendung zu gehen sollte, basierend auf dem Datumsstempel, den ich habe.

Die Scherbe Konfiguration ist so etwas wie diese (Pseudocode): die erste Spalte das Datum der Veranstaltung ist es ich suche und das zweite ist die Scherbe das Ereignis in residiert

pre-2008 -> shard1 
2008-2009 -> shard2 
2009_01-2009_06 -> shard3 
2009_07 -> shard4 
2009_08 -> shard5 
2009_09 and up -> shard6 

As. Sie können sehen, dass die Konfiguration, die ich möchte, ziemlich flexibel ist - sie kann jeden beliebigen Datumsbereich, egal wie klein oder groß, sein und einem Shard zuordnen.

Ich bin auf der Suche nach dem schnellsten Weg, um eine Suche nach einem bestimmten Datum zu tun.

Zum Beispiel, wenn mein Datum ist 2009-05-02, ist der Shard ich nach shard3 bin. Wenn das Datum 2007-08-01 ist, dann ist es shard1.

Bonuspunkte für tatsächlichen PHP-Code, wie die Anwendung in PHP ist.

Vielen Dank.

Answer 1

ich raten bin, dass Sie nicht Löcher in Datumsbereiche haben wollen, so schlage ich vor, dass Sie nur ein Enddatum angeben müssen für Jedes Shard, und explizit einen Default Shard , der alles enthält, was zu neu ist, um in einen der anderen Shards zu passen.

// configure shards 
$SHARDS = array(
     // <end date> => <shard number> 
     '2007-12-31' => 'shard1', // shard1 - up to end of 2007 
     '2008-12-31' => 'shard2', // shard2 - up to end of 2008 
     '2009-06-30' => 'shard3', // shard3 - up to end of June 09 
     '2009-07-31' => 'shard4', // shard4 - up to end of July 2009 
     '2009-08-31' => 'shard5', // shard4 - up to end of August 2009 
     'DEFAULT'  => 'shard6', // everything else in shard 6 
     ); 

Dies macht es einfach die Daten richtig zu machen, und der Code eine Scherbe für die Suche basierend auf Datum ist einfach:

function findShardByDate($date) { 
    static $default = false; 
    static $sorted = false; 
    if($sorted === false) { 
     // copy of global $SHARDS 
     $SHARDS = $GLOBALS['SHARDS']; 
     $default = $SHARDS['DEFAULT']; 
     unset($SHARDS['DEFAULT']); 
     // make sure $SHARDS is sorted 
     ksort($SHARDS); 
     $sorted = $SHARDS; 
     unset($SHARDS); 
    } 
    // find the first shard which would contain that date 
    foreach($sorted as $endDate => $shardName) 
     if($endDate >= $date) 
      return $shardName; 
    // no shard found - use the default shard 
    return $default; 
} 

Edit: Verwendet statische Variablen, so dass Sortierung nur erfolgt Einmal.

Answer 2

Da Ihre Shards streng geordnet werden können, scheint es, als würde man sie in einem Binärbaum speichern und dann einfach eine binäre Suche durch diesen Baum ausführen, um die schnellsten Ergebnisse zu erzielen.

Answer 3

<?php 

function get_shard($datetime) 
{ 
    $timestamp = strtotime($datetime); 

    $shards = array(array('start' => null, 'end' => '2007-12-31'), 
        array('start' => '2008-01-01', 'end' => '2008-12-31'), 
        array('start' => '2009-01-01', 'end' => '2009-06-30'), 
        array('start' => '2009-07-01', 'end' => '2009-07-31'), 
        array('start' => '2009-08-01', 'end' => '2009-08-31'), 
        array('start' => '2009-09-01', 'end' => null), 
        ); 
    foreach ($shards as $key => $range) { 
     $start = strtotime($range['start']); 
     $end = strtotime($range['end']); 
     if ($timestamp >= $start && $timestamp <= $end) { 
      return $key + 1; 
     } 
     if ($timestamp >= $start && $end === false) { 
      return $key + 1; 
     } 
    } 
} 


$datetime = '2007-08-01'; 
echo 'shard' . get_shard($datetime) . "\n"; 

$datetime = '2009-05-02'; 
echo 'shard' . get_shard($datetime) . "\n"; 

$datetime = '2010-01-01'; 
echo 'shard' . get_shard($datetime) . "\n"; 

?> 

Ausgänge:

shard1 
shard3 
shard6