根據事件日期查找日期範圍的算法

我正在編寫一個PHP函數，該函數將使用一個排序表根據我擁有的日期戳記來查找應用程序應該到哪個DB分片。根據事件日期查找日期範圍的算法

的碎片的配置是這樣的（僞代碼）：第一列是我在尋找和第二是事件駐留在碎片事件的日期

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

爲。你可以看到，我想要的配置非常靈活 - 它可以採用任何日期範圍，無論大小如何，都可以映射到碎片。

我正在尋找基於給定日期進行查找的最快方法。

例如，如果我的日期是2009-05-02，那麼我之後的分片是shard3。如果日期是2007-08-01，那麼它是shard1。

實際PHP代碼的獎勵積分，因爲應用程序使用PHP。

謝謝。

來源

2009-08-17 Artem Russakovskii

我猜測你不希望在日期範圍洞，所以我建議你只需要指定一個結束日期爲每個分片，並明確命名一個默認分片 其中包含的所有內容都太新以至於無法放入其他分片之一。

// 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 
     );

這使得它容易得到的日期的權利，並根據日期找到一個碎片的代碼很簡單：

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; 
}

編輯：使用的靜態變量，這樣排序只是做一旦。

來源

2009-08-18 00:11:49

嗯，我不想整理和查找所有的時間，因爲這很貴。否則，我喜歡你的方法，因爲確實沒有漏洞。 – 2009-08-18 00:54:43

使用開始日期而不是結束日期將消除對'默認'的需要。 – 2009-08-18 03:23:51

使用開始日期將需要一個默認值來捕捉*第一個分片之前的任何內容*。 – 2009-08-18 04:01:56

由於您的分片可以嚴格排序，因此它似乎將它們存儲在二叉樹中，然後只需在該樹中運行二分搜索就可以獲得最快的結果。

來源

2009-08-17 23:37:01 Amber

<?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"; 

?>

輸出：

shard1 
shard3 
shard6

來源

2009-08-17 23:55:47 inerte

我明白了，但您的實現仍然受到未優化查找的影響。另外，例如，如果您決定更改碎片名稱或將長碎片範圍拆分爲2個較短的碎片範圍，則需要重寫整個函數。 – 2009-08-18 00:56:27

根據事件日期查找日期範圍的算法

回答

相關問題