CODEWITHSUNDEEP
phpalgorithm
Zulfiqar Memon
Zulfiqar Memon

Reputation: 65

Prioritized Random Selection

I need to design an algorithm that displays ads on a website based on imprints. i record each imprint in DB. Cannot make use of mysql rand() limit 1 in my query as it will be uncontrolled query. i have to make sure that if an ad is selected its not only just an ad with lowest imprints but there is some randomness to it. Also New Ads get a biased selection some way.

In order to achieve this i have managed to write a function but somewhere I am not satisfied with it. Please go through it and let me know if it could done any better.

function getRandomAd($result){
while($row = mysql_fetch_assoc($result)){
     $rows[] = $row;
}
$filteredRow = array();
foreach($rows as $row){
    if($row['imprints'] == 0 ){
        $row['piority'] = 10;
        $filteredRow[] = $row;
    }
    else if($row['imprints'] >= 0 and $row['imprints'] <= 5){
        $row['piority'] = 8;
        $filteredRow[] = $row;
    }
    else if($row['imprints'] >= 5 and $row['imprints'] <= 15){
        $row['piority'] = 6;
        $filteredRow[] = $row;
    }
    else if($row['imprints'] >= 15 and $row['imprints'] <= 30){
        $row['piority'] = 4;
        $filteredRow[] = $row;
    }
    else if($row['imprints'] >= 30 and $row['imprints'] <= 60) {
        $row['piority'] = 2;
        $filteredRow[] = $row;
    }
    else{
        $row['piority'] = 0;
        $filteredRow[] = $row;
    }

    foreach($filteredRow as $row){
        if($row['piority'] == 10 or $row['piority'] == 8) $high[] = $row;
        if($row['piority'] == 6 or $row['piority'] == 4) $medium[] = $row;
        if($row['piority'] == 2 or $row['piority'] == 0) $low[] = $row;
    }

    $countHigh = count($high);
    $countMed = count($medium);
    $countLow = count($low);

    if($countHigh > $countLow and $countHigh > $countMed)$rowReturned = $high;
       if($countMed > $countLow and $countMed > $countHigh) $rowReturned = $medium; 
    if($countLow > $countMed and $countLow > $countHigh) $rowReturned = $low;

}
return $rowReturned[array_rand($rowReturned,1)];

}

Upvotes: 0

Views: 250

Answers (2)

user895378
user895378

Reputation:

Returning all the rows and using PHP to sort and determine which row to spit out is terribly inefficient. This would be better handled on the database end than in PHP.

Also, your current set of if statements overlap with the >= operators.

Finally, I know you didn't do this but just a general note: you should almost never use ORDER BY RAND() with MySQL because the performance is terrible. This is because when you use a function return value to order results MySQL can't use an index for the order operation.

Here's a better solution ...

  1. Generate a weighted random number in PHP that we can use as a condition for our query
  2. Write a query that will return only one result based on the weighted random number

So, lets generate a random integer weighted towards the lower end of the imprint spectrum:

$max    = 60;
$random = floor($max - mt_rand(mt_rand(1, $max), $max));

And write a query that uses the weighted random number to pick a single result from the table:

$query = '
  SELECT id, advert_txt
  FROM table
  WHERE imprints >= '.$random.'
  ORDER BY imprints ASC
  LIMIT 1
';

Note that you would normally want to escape a PHP variable in a query like this (or preferably use prepared statements with PDO), but since we know the variable is an integer in this case it's okay.

This solution will appropriately weight returned results based on their respective imprint counts while maintaining MySQL's ability to use indexes to select the record, which is of paramount importance if you have a large number of rows in the table.

UPDATE

I would add that you could tweak the random number generation to your own needs. With this particular solution you'll never get back a row with >= 60 imprints. The solution remains sound though, because it's trivial to tweak how you determine the condition for the query. For example, maybe you would first run a query to get the MAX(imprints) from the database and use that value for your $max when determining the random number.

And second, just to demonstrate the behavior of the random number generation specified above, if you run it 10,000 times using a $max = 10 you'll get results similar to this:

0:  2966
1:  1965
2:  1420
3:  1101
4:  820
5:  621
6:  457
7:  333
8:  210
9:  107

UPDATE 2

In response to your comment for further clarification ...

In my original update I'm trying to say that if you just hard-code in the max value as 60, the original code will never return a row where imprints >= 60. This means that if you just use that code on it's own, it will work fine for a while but eventually (assuming you increment the imprints column each time you display an advertisement) all your records will have been imprinted 60+ times and you won't get any results back.

So to avoid such an issue the entire process would be something like this:

  1. Query the table once to get the highest imprints column value to use for your maximum random value range like so: SELECT MAX(imprints) AS max FROM my_table;
  2. Use the max value you retrieved in step one in the $max variable when generating your random weighted number.
  3. Update the table by incrementing the imprints column up for the row you retrieved in step 2.

Upvotes: 6

Mick Hansen
Mick Hansen

Reputation: 2694

function getRandomAd($result) {
    $imprint_weights = array(
        array(
            'min' => 0,
            'max' => 0,
            'weight' => 10
        ),
        array(
            'min' => 1,
            'max' => 5,
            'weight' => 8
        ),
        array(
            'min' => 6,
            'max' => 15,
            'weight' => 6
        ),
        array(
            'min' => 16,
            'max' => 30,
            'weight' => 4
        ),
        array(
            'min' => 31,
            'max' => 60,
            'weight' => 2
        )
    );

    $weighted = array();
    foreach ($result as $row) {
        $imprints = $row['imprints'];
        $imprint_weight = 1;

        foreach ($imprint_weights as $match) {
            if ($imprints >= $match['min'] && $imprints <= $match['max']) {
                $imprint_weight = $match['weight'];
            }
        } 

        $weighted = array_merge($weighted, array_fill(0, $imprint_weight, $row));
    }

    return $weighted[array_rand($weighted)];
}

$data = array();
for ($x = 1; $x <= 100; $x++) {
    $data[] = array(
        'id' => $x,
        'imprints' => rand(0, 65)
    );
}

print_r(getRandomAd($data));

This provides an alternative way of doing what you want. The benifit here being that you can more easily change how an amount of imprints affect the weight of an ad, and also easily add more parameters (like age) to influence the selection of an ad.

Upvotes: 1

Related Questions