如何優化PHP中的「彩票」功能？

早些時候，我在Matlab中爲這種抽獎功能寫了一段代碼，只是爲了測試它是否可行。然而，我真的需要它在PHP中，所以我剛剛重寫了代碼，它似乎工作，但由於它涉及很多循環，我想確保我儘可能有效地做到這一點。如何優化PHP中的「彩票」功能？

的代碼做什麼：

你可以調用函數$lotto -> type($users,$difficulty)，它將返回兩個數字。以下是解釋，$users是在網站上註冊的用戶數量，即可能會購買機票的人數。 $difficulty是1到10之間的數字，其中5是正常的，1是容易的，10是硬的。這裏的困難意味着要匹配彩票上的所有號碼是多麼困難。

那麼函數返回的數字是什麼？那將是$n和$r。 $n是彩票上的號碼數量，$r是您可以從彩票中選擇的號碼數量。例如，在英國，全國彩票有49個號碼，如果您選擇了6個號碼，即E。$n = 49和$r = 6。

函數如何計算這兩個數字？在英國國家彩票中有13,983,816種不同的機票組合。如果我運行$lotto -> type(13983816,1)它將返回array(49,6)。基本上它試圖做到這一點，所以有與註冊用戶一樣多的門票組合。

TL;博士，這裏是代碼：

<?php 
class lotto { 
    public function type($users,$difficulty){ 
     $current_r = $r = 2; 
     $current_n = 0; 
     $difficulty = ($difficulty + 5)/10; // sliding scale from 1 - 10 
     $last_tickets_sold = 200; // tickets sold in last lotto 
     $last_users = 100; // how many users there were in the last lotto 
     $last_factor = $last_tickets_sold/$last_users; // tickets per user 
     $factor = $last_factor * $difficulty; 
     $users *= $factor; 
     while($r <= 10){ 
      $u = 0; 
      $n = $r; 
      while($u < $users && $n < 50){ 
       $u = $this -> nCr(++$n,$r); 
      } 
      if($r == 2){ 
       $current_n = $n; 
      } elseif(abs($this -> nCr($n,$r) - $users) < abs($this -> nCr($current_n,$current_r) - $users)){ 
       // this is a better match so update current n and r 
       $current_r = $r; 
       $current_n = $n; 
      } 
      $r++; 
     } 
     return array($current_n,$current_r); 
    } 
    private function nCr($n,$r){ 
     return $this -> factorial($n)/(
      $this -> factorial($r) * $this -> factorial($n - $r) 
     ); 
    } 
    private function factorial($x){ 
     $f = $x; 
     while(--$x){ 
      $f *= $x; 
     } 
     return $f; 
    } 
} 
$lotto = new lotto; 
print_r($lotto -> type(1000,5)); 
?>

來源

2012-07-26 Keir Simmons

一個小的優化是將以前的階乘結果存儲在一個數組中，因此您不必每次都進行長時間的計算。這將映射輸入=>輸出的映射。這應該大大減少階乘的處理時間。您還可以存儲最後一個已知值，因爲您有兩個始終增加的數字。 – sean 2012-07-26 19:01:13

我做了一個快速掃描，發現了一些可以進一步優化的地方。

組合
你的算法是一個蠻力一個和可以進一步優化

private function nCr($n,$r){ 
    return $this -> factorial($n)/(
     $this->factorial($r) * $this->factorial($n - $r) 
    ); 
}

到

function nCr($n,$r) { 
    $top = 1; 
    $sub = 1; 

    for($i = $r+1; $i <= $n; $i++) 
     $top *= $i; 

    $n -= $r; 
    for($i = 2; $i <= $n; $i++) 
     $sub *= $i; 

    return $top/$sub; 
}

太多組合運算
計算組合是昂貴的。

$u = 0; 
$n = $r; 
while($u < $users && $n < 50){ 
    $u = $this -> nCr(++$n,$r); 
}

到

$n = $r + 1; 
$u = nCr($n, $r); 

while ($u < $users && $n < 50) { 
    $n++; 
    $u *= $n; 
    $u /= ($n - $r); 
}

來源

2012-07-26 19:30:53 invisal

沒有機會檢查這些與OP代碼一起使用的輸出，但這是問題的唯一答案。 – sean 2012-07-26 19:57:34

可愛的，只是在基準測試之前和之後：原來的100倍〜=0.159秒 100X新代碼〜=0.0174秒顯着改善，非常感謝:)，我upvoted您的評論。 – 2012-07-26 23:44:03

一個直接的觀察是，你必須通過0誤差

$last_factor = $last_tickets_sold/$last_users;

一分的可能性，可以通過把一個簡單的if語句來解決在它周圍

$last_factor = ($last_users == 0) ? 0 : $last_tickets_sold/$last_users;

來源

2012-07-26 19:01:06 JConstantine

但'$ last_users = 100;'，一個靜態定義的值。如果這產生了一個由0錯誤分裂，這將是一個史詩般的PHP錯誤。 – nickb 2012-07-26 19:02:29

同意，但我假設（是的，我知道，假設是錯誤的），這些值將改變爲從數據庫拉動的動態值。但是，是的，鑑於目前的代碼是不可能的。只是一個觀察 – JConstantine 2012-07-26 19:04:11

你的假設是正確的，它將被從數據庫中拉出來，但是有可能0個用戶上次使用彩票，所以感謝這個建議。 – 2012-07-26 19:06:15

不管你的代碼的詳細檢查，你確定你的循環確實不需要繼續或休息？

來源

2012-07-26 19:05:22

絕對不是，它們只能達到n = 50和r = 10那麼高，我需要嘗試每種可能性來更好地匹配。 – 2012-07-26 19:12:37

階乘的範圍（）在算法中爲[0,50]，所以爲什麼不預先計算這個靜態？

private static $factorial=array(1); 

private static genFactorial($max) { 
    if(count(self::$factorial) > $max) return; 
    foreach (range(count(self::$factorial), $max) as $n) { 
     self::$factorial[$n] = $i*self::$factorial[$n-1]; 
    } 
}

現在添加一個self::genFactorial(50);到__construct()或type()和self::$factorial[$n]更換到$this -> factorial($n)引用。

這只是一個快速代碼轉儲;甚至沒有編譯檢查，所以原諒任何拼寫錯誤等，但這樣做是取決於一個數組元素獲取函數調用（其中包括一個while循環）。

來源

2012-07-26 23:05:54 TerryE

如何優化PHP中的「彩票」功能？

回答

相關問題