Here I discuss a nifty little algorithm which I developed to choose an item from a list of possible items, when only the relative weights of the items are known. The number of items need not be known, so this algorithm is suitable for choosing among a list of items while iterating over those items, for example a list of rows returned from a streaming database query. Only one item is required to be in memory at a time.

Let’s discuss the problem domain. Let’s say you have an arbitrary-length list of items, where each item contains some data (it doesn’t matter what the data is), paired with a rotation weight (probability). For any iteration of this algorithm, any given item’s probability of being selected by the algorithm is equal to that item’s rotation weight (probability) divided by the total rotation weight of all items in the list. The list must be iterated from beginning to end before the final choice is known.

I refer to the term “rotation” because this algorithm can be used to perform load balancing against an arbitrary-length list of servers, where some servers are given larger weights based on their performance in relation to the other servers. In other words, an eight-core system with 32G RAM would have roughly twice the request handling capacity as a four-core system with 16G RAM, therefore the larger server’s weight would be roughly twice that of the smaller server.

Without further ado, here is the code.

<?php
$items = array(
    (object)array('data'=>0, 'weight'=>5),
    (object)array('data'=>1, 'weight'=>8),
    (object)array('data'=>2, 'weight'=>20),
    (object)array('data'=>3, 'weight'=>50),
    (object)array('data'=>4, 'weight'=>10),
    (object)array('data'=>5, 'weight'=>7),
);

$stats = array();

for ($pass = 1; $pass <= 1000; $pass++) {

    // Begin weighted rotation algorithm.
    $item = null;
    $totalWeight = 0.0;
    foreach ($items as $obj) {
        $totalWeight += $obj->weight;
        if (($item === null) || (($totalWeight*((double)mt_rand(0, PHP_INT_MAX)/(double)PHP_INT_MAX)) <= $obj->weight)) {
            $item = $obj;
        }
    }
    // End weighted rotation algorithm.

    if (isset($stats[$item->data])) {
        $stats[$item->data]++;
    } else {
        $stats[$item->data] = 1;
    }
}

ksort($stats, SORT_NUMERIC);

print_r($stats);

Copy the above code and paste it into a file named randomWeightedRotation_lowMemoryUsage.php, then run it. You should see something resembling the following.

$ php randomWeightedRotation_lowMemoryUsage.php 
Array
(
    [0] => 30
    [1] => 58
    [2] => 199
    [3] => 541
    [4] => 96
    [5] => 76
)

The sample code is written in PHP, but is incredibly simple, so should be a snap for any competent developer to re-implement in virtually any language.