Avoiding loops in a complex calculation with arrays

Question

I have two arrays of numbers, one containing a lot of numbers, one only a few. There are no duplicates within or between arrays:

$all = range(1, 50);
$few = array(7, 11, 19, 27, 29, 36, 40, 43);
$many = array_merge(array_diff($all, $few));

I now want to calculate the differences between each of the "few" numbers and all of the "many" that follow it but come before the next of the "few". For example, among $many, only 28 falls between 27 and 29 from $few, so I want to calculate the difference between 28 and 27. No other differences to 27 are calculated, because no other $many fall between 27 and 29. For 19 from $few I will calculate the differences to 20, 21, 22, 23, 24, 25 and 26, because they all lie between 19 and the next number from $few, which is 27.

To calculate the differences, I use loops. Here is a somewhat simplified code (which ignores the fact that there is no index [$i + 1] for the last number in $few):

$differences = array();
for($i = 0; $i < count($few); $i++) {
    foreach($many as $m) {
        if($m > $few[$i] && $m < $few[$i + 1]) {
            $differences[] = $m - $few[$i];
        }
    }
}

If I have huge arrays, the loops will take a long time to run. So:

Is there a better way to calculate the differences, without using loops?

---

The resulting $differences looks like this:

Array         $many    $few
(                 ↓    ↓
    [0] => 1  //  8 -  7 = 1
    [1] => 2  //  9 -  7
    [2] => 3  // 10 -  7
    [3] => 1  // 12 - 11
    [4] => 2
    [5] => 3
    [6] => 4
    [7] => 5
    [8] => 6
    [9] => 7
    [10] => 1
    [11] => 2
    [12] => 3
    [13] => 4
    [14] => 5
    [15] => 6
    [16] => 7
    [17] => 1
    [18] => 1
    [19] => 2
    [20] => 3
    [21] => 4
    [22] => 5
    [23] => 6
    [24] => 1
    [25] => 2
    [26] => 3
    [27] => 1
    [28] => 2
)

---

My basic reasoning is that as a human, I don't see two arrays that I compare:

... 16 17 18 | 20 21 22 23 24 25 26 | 28 29 30 31 ...
   exclude   |       include        |   exclude
            19                     (27)

But rather one number line that I go along from one number to the next, and when I meet one marked "few" I will calculate all the differences to each of the following numbers, until I meet another one marked "few":

... 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ...
... m  m  m  f  m  m  m  m  m  m  m  f  m  m  m  m  ...
             ↑  ↑ ...                ↑
         start  calculate            stop

Because it is sorted, I don't have to go over the whole $many-array number by number for every number from $few. So can we somehow take the fact into account that the arrays are ordered? Or maybe build one array that contains the markers ("f", "m") and the numbers as keys? E.g.:

$all = array("drop this", "m", "m", "m", "m", "m", "m", "f", ...);
unset($all[0]); // drops the first element with index 0

Answer 1

Apart from the two calls to sort(), all you need is a single loop through $many.

// Input data provided in the question    
$all = range(1, 50);
$few = array(7, 11, 19, 27, 29, 36, 40, 43);
$many = array_values(array_diff($all, $few));

// Display the values to see what we are doing
echo('$few = ['.implode(' ', $few)."]\n");
echo('$many = ['.implode(' ', $many)."]\n");


//
// The actual algorithm starts here


// Sort both $few and $many
// it works fast enough and it is required for the rest of the algorithm
sort($few);
sort($many);

// Be sure the last value of $few is larger than the last value of $many
// This is needed to avoid extra checking for the last element of $few inside the loop
if (end($few) < end($many)) {
    array_push($few, end($many) + 1);
}

// Extract the first two items from $few
$current = array_shift($few);
$next    = array_shift($few);

// This is the result
$differences = array();    

// Run only once through $many, check each item against $next
// subtract $current from it; advance when $next was reached
foreach ($many as $item) {
    // Skip the items smaller than the first element from $few
    if ($item < $current) {
        continue;
    }

    // If the next element from $few was reached then advance to the next interval
    while ($next < $item) {
        $current = $next;
        $next    = array_shift($few);
    }

    // Here $current < $item < $next
    // This echo() is for debug purposes 
    echo('$current = '.$current.'; $item = '.$item.'; $next = '.$next.'; difference='.($item - $current)."\n");

    // Store the difference
    $differences[] = $item - $current;
}