Creating a Banner Swapping Algorithm to Rotate Ads

Question

I'm working on building an ad banner rotation script based on impressions that displays ads evenly throughout the month. The calculations will be done each time the ad is requested to be displayed. So this will be done on the fly. The ads should appear to rotate through, one after another, and not just display one ad for 1000 impressions, then the other ad for 1000 impressions. It for the most part should display for 1 impression, then switch ads (unless of course one ad has a lot more impressions than the other to use up).

Let's say I have 5 ads and each has a different number of impressions that were purchased, what would be the formula/how do you serve up the ads? I'm looking to do this in PHP.

Ad #1: 1,000 purchased impressions

Ad #2: 12,000 purchased impressions

Ad #3: 3,000 purchased impressions

Ad #4: 20,000 purchased impressions

Ad #5: 10,000 purchased impressions

if there are multiple ads that bought 1000 impressions all for the same time frame, it should show one after another until the impressions are used. Though, I think it might be good that if a person bought 1000 impressions for a short time frame, I should account for that and show them at a faster rate. I'm open to suggestions.

Answer 1

I think you should use the best type of algorithm for the best JOB i'll only show you some few possibility on how to implement such

My current example would show using

• shuffle
• fisherYatesShuffle
• robinShuffle
• ratioShuffle

You can also implement

• Priory Based shuffle
• Time Base Shuffle
• Percentage
• Click Shuffle
• etc

Simple Prove of Concept

// Create Add Infroamtion
$ads = array();
$ads[] = new Ad(10, "A.jpg", 2);
$ads[] = new Ad(12, "B.gif", 3);
$ads[] = new Ad(30, "C.png", 7);
$ads[] = new Ad(20, "D.swf", 5);

// Add ads to banner
$banner = new Banner($ads);

// You can also add addional ads
$banner->add(new Ad(10, "E.swf"));

echo "<pre>";

//Lets Emulate first 100 rotations 
for($i = 0; $i < 1000; $i ++) {
    // Select Algorithm
    $banner->randomise("ratioShuffle");

    // Display Add
    echo $banner->getDisplay(), PHP_EOL;
}

Simple Shuffle Function that can be used

function fisherYatesShuffle(array &$items) {
    for($i = count($items) - 1; $i > 0; $i --) {
        $j = @mt_rand(0, $i);
        $tmp = $items[$i];
        $items[$i] = $items[$j];
        $items[$j] = $tmp;
    }
}

function robinShuffle(array &$items) {
    usort($items, function ($a, $b) {
        $a = $a->getDisplay();
        $b = $b->getDisplay();
        return $a == $b ? 0 : ($a < $b ? - 1 : 1);
    });
}

function ratioShuffle(array &$items) {
    static $called = false;
    if ($called === false) {
        $ads = array();
        foreach ( $items as &$ad ) {
            for($i = 0; $i < $ad->getRatio(); $i ++) {
                $ads[] = $ad;
            }
        }
        $called = true;
        $items = $ads;
    }
    shuffle($items);
}

Classes Used

class Ad implements JsonSerializable {
    private $impressions;
    private $media;
    private $ratio = 1;
    private $display = 0;

    function __construct($impressions, $media = null, $ratio = 1) {
        $this->impressions = $impressions;
        $this->media = $media;
        $this->ratio = $ratio;
    }

    function torch() {
        $this->impressions --;
        $this->display ++;
    }

    public function getImpression() {
        return $this->impressions;
    }

    public function getDisplay() {
        return $this->display;
    }

    public function getRatio() {
        return $this->ratio;
    }

    public function getMeadia() {
        return $this->media;
    }

    public function __toString() {
        return json_encode($this->jsonSerialize());
    }

    public function jsonSerialize() {
        return get_object_vars($this);
    }
}


class Banner implements Countable, JsonSerializable {
    private $totalImpressions;
    private $ads = array();

    function __construct(array $ads) {
        foreach ( $ads as $ad )
            $this->add($ad);
    }

    public function add(Ad $ad) {
        $this->ads[] = $ad;
        $this->totalImpressions += $ad->getImpression();
    }

    public function randomise($function = null) {
        if (is_callable($function, false, $callable_name)) {
            return $callable_name($this->ads);
        } else {
            return shuffle($this->ads);
        }
    }

    public function getDisplay() {
        foreach ( $this->ads as &$ad ) {
            if ($ad->getImpression() < 1) {
                unset($ad);
                continue;
            }
            $ad->torch();
            break;
        }
        return isset($ad) ? $ad : null;
    }

    public function jsonSerialize() {
        $array = $this->ads;
        foreach ( $array as &$ad ) {
            $ad = $ad->jsonSerialize();
        }
        return $array;
    }

    public function __toString() {
        return json_encode($this->jsonSerialize());
    }

    function count() {
        return count($this->ads);
    }
}

As you can see this is an example .... Just try and make your solution flexible

Answer 2

Personally, I'd work out what percentage of impressions each ad has received compared to how many are paid for, and use that as the chance that it won't show up. Something like this:

$show = Array();
foreach($ads as $id=>$ad) {
    $show[$id] = ceil((1-$ad['impressions']/$ad['paid'])*100);
}
$total = array_sum($show);
$rand = rand(1,$total);
$winner = -1;
do {$rand -= array_shift($show); $winner++;} while($rand && $show);
$ad_to_display = $ads[$winner];

For example, consider four ads, A, B, C and D. All of them have paid for 1,000 impressions, but so far A has been unlucky and gotten zero, while B and C both have had 500 impressions, and D has had 999.

This would mean $show has these values for the ads:

A: ceil((1-0/1000)*100) = 100
B: ceil((1-500/1000)*100) = 50
C: ceil((1-500/1000)*100) = 50
D: ceil((1-999/1000)*100) = 1

$total is therefore equal to 201.

$rand can be any number from 1 to 201 inclusive. Let's say 141.

In this case, we begin our loop:

• $rand -= 100, now it's 41. 41 is truthy and we have ads remaining.
• $rand -= 50, now it's -9. It has reached zero, so end the loop.

The $winner is 1, which is advert B.