CODEWITHSUNDEEP
phpoptimizationcombinations
Keir Simmons
Keir Simmons

Reputation: 1684

How can I optimize this 'lottery' function in PHP?

Earlier I wrote a code in Matlab for this sort of lottery function, just to test if it was possible. However, I actually needed it in PHP so I've just rewritten the code and it does seem to work, but as it involves a lot of looping I want to make sure I'm doing it as efficiently as possible.

What the code does:

You can call the function $lotto -> type($users,$difficulty) and it will return two numbers. Here's the explanation, $users is the number of users registered on the website, i.e the people who will potentially buy a ticket. $difficulty is a number between 1 and 10, where 5 is normal, 1 is easy and 10 is hard. Difficulty here means how hard it is to match all numbers on a lottery ticket.

So what are the numbers that the function returns? That would be $n and $r. $n is the amount of numbers there will be on the lottery ticket, and $r is the amount of numbers you can choose from the lottery ticket. For example, in the UK a national lottery ticket has 49 numbers if which you choose 6. I.e $n = 49 and $r = 6.

How does the function calculate these two numbers? In the UK national lottery there are 13,983,816 different possible ticket combinations. If I were to run $lotto -> type(13983816,1) it would return array(49,6). Basically it tried to make it so there are as many combinations of tickets as there are registered users.

tl;dr, here's the code:

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

Upvotes: 0

Views: 1394

Answers (4)

TerryE
TerryE

Reputation: 10888

The range of factorial() in your algo is [0,50], so why not just precompute this statically?

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

Now add a self::genFactorial(50); to __construct() or to type() and replace references to $this -> factorial($n) by self::$factorial[$n].

This is just a quick code dump; not even compile checked so forgive any typos, etc. but what this does is to replace a function call (which includes a while loop) by an array element fetch.

Upvotes: 0

invisal
invisal

Reputation: 11181

I did a quick scan and spotted a few places that can be further optimized.

Combination
Your algorithm is a brute force one and can be further optimized

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

to

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

Too Much Combination Calculation
Calculate combination is expensive.

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

to

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

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

Upvotes: 2

user1350140
user1350140

Reputation:

Regardless detailed examination of your code, are you sure that your loops does not need continue or break?

Upvotes: 0

JConstantine
JConstantine

Reputation: 3931

An immediate observation is that you have the possibility of a divide by 0 error

$last_factor = $last_tickets_sold / $last_users;

Could be solved by putting a simple if statement around it

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

Upvotes: 1

Related Questions