计算范围之间的值

Question

我有两个数组，一个是值，另一个是范围：$ranges = array(10,15,30);$values = array(1,4,12,15,27,32);我想计算每个范围之间的值的数量，例如：$output = array(    "<10" => 2, // number of values < 10    "10-15" => 1, // number of values >= 10 && < 15    "15-30" => 2, // number of values >= 15 && < 30    ">=30" => 1, // number of values > 30);显然，ranges并且values是动态的，不能硬编码if-conditions。到目前为止我所做的工作：$output = array();foreach ( $values as $val ) {    foreach ( $ranges as $k => $range ) {        if ( $k == 0 ) { // first range            $max = $range;            $label = '<' . $max;            if ( $val < $max ) {                $output[$label] += 1;            }        } else if ( $k == count($ranges) - 1 ) { // last range            $min = $ranges[$k-1];            $max = $range;            $label = $min . '-' . $max;            if ( $val >= $min && $val < $max ) {                $output[$label] += 1;            }            $min = $range;            $label = '>=' . $min;            if ( $val >= $min ) {                $output[$label] += 1;            }        } else {            $min = $ranges[$k-1];            $max = $range;            $label = $min . '-' . $max;            if ( $val >= $min && $val < $max ) {                $output[$label] += 1;            }        }    }}print_r($output);这似乎很昂贵，我真的不确定。有没有更简单的方法来实现我正在寻找的东西？

Answer 1

您可以通过在 $ranges 数组的开头和结尾添加限制值来简化逻辑，然后只需成对处理整个数组。

<?php

$ranges = [10,15,30];

$values = [1,4,12,15,27,32];

\array_push($ranges, null); // append null to array

\array_unshift($ranges, null); // prepend null to array

$output = [];

$count = \count($ranges);

for ($i = 0; $i < $count - 1; $i++) {

    $output[] = ['start' => $ranges[$i], 'end' => $ranges[$i+1], 'count' => 0];

}

foreach ($values as $value) {

    foreach ($output as $key => $range) {

        if (

             ($range['start'] === null || $range['start'] <= $value) &&

             ($range['end'] === null || $range['end'] > $value)

        ) {

            $output[$key]['count']++;

            break;

        }

    }

}

var_dump($output);

Answer 2

$ranges首先使用数组中的键（使用）创建一个归零数组array_fill_keys()，再加上一个用于“超过”最后一个条目的值。

循环遍历每个值并根据范围检查它，如果找到它，它只会将相应的计数加 1 并停止查找。如果在完成循环后，该值大于最后一个范围，则将 1 添加到“over”条目。

$ranges = array(10,15,30);

$values = array(1,4,12,15,27,32);

$rangeCount = array_fill_keys($ranges, 0);

$rangeCount[ "over" ] = 0;

foreach ( $values as $value )   {

    foreach ( $ranges as $range )   {

        if ( $value < $range )  {

            $rangeCount [ $range ]++;

            break;

        }

    }

    if ( $value >= $range )  {

        $rangeCount[ "over" ]++;

    }

}

print_r($rangeCount);

这使...

Array

(

    [10] => 2

    [15] => 1

    [30] => 2

    [over] => 1

)

只是为了添加一个只做一个循环的优化版本。但假设这些值是按升序排列的。每次它通过“当前”范围时，它都会移动到下一个输出计数器，最后一部分甚至不会循环超过最大值，它会从总计数中减去当前计数并中断...

$currentRange = 0;

$numberValues = count($values);

$numberRanges = count($ranges);

$rangeCount = array_fill(0, $numberRanges, 0);

$rangeCount[ "over" ] = 0;

foreach ( $values as $count => $value )   {

    if ( $value >= $ranges[$currentRange] )   {

        $currentRange++;

        if ( $currentRange >= $numberRanges )    {

            $rangeCount[ "over" ] = $numberValues - $count;

            break;

        }

    }

    $rangeCount[$currentRange]++;

}

print_r($rangeCount);

Answer 3

以下解决方案首先按升序/非降序对范围进行排序。

然后，我们创建一个range_map它是所有可能范围的集合$ranges。

然后，我们遍历所有值$values并进行二进制搜索以$ranges获得特定值所属的确切范围索引。在下面的代码中，精确索引存储在$low.

然后，我们只需通过取范围键$range_map并将其计数器加 1 来收集计数。

这比嵌套循环更快，因为嵌套循环的时间复杂度O(m*n)是m大小$ranges和n大小$values，而当前解决方案的时间复杂度O(m logm) + O(n logm)是m大小$ranges和n大小$values。

片段：

<?php

$ranges = array(10,15,30);

$values = array(1,4,12,15,27,32);

sort($ranges);

$range_map = [];

$ptr = 0;

foreach($ranges as $index => $value){

    if($index === 0) $range_map[$ptr++] =  "<" . $value;

    if($index > 0) $range_map[$ptr++] = $ranges[$index - 1] . "-" . $value;

    if($index === count($ranges) - 1) $range_map[$ptr++] = ">=" . $value;

}

$result = [];

foreach($values as $value){

    $low = 0; $high = count($ranges) - 1;

    while($low <= $high){

        $mid = $low + intval(($high - $low) / 2);

        if($value === $ranges[ $mid ]){

            $low = $mid + 1;

            break;

        }else if($value < $ranges[ $mid ]){

            $high = $mid - 1; 

        }else{

            $low = $mid + 1;

        }

    }

    if(!isset($result[$range_map[$low]])) $result[$range_map[$low]] = 0; // get the range key from range_map

    $result[$range_map[$low]]++; // increment the value for that range

}

print_r($result);

演示： https ://3v4l.org/JcYBv

Answer 4

假设您有预先排序的范围和值。

<?php

$ranges = array(10,15,30);

$values = array(1,4,12,15,27,32);

$lower = null;

$i = 0;

$upper = $ranges[$i];

foreach($values as $item) {

    if(!is_null($upper) && $item >= $upper) {

        $lower = $upper;

        $upper = $ranges[++$i] ?? null;

    }

    $result["$lower<$upper"][] = $item;

}

var_export(array_map('count', $result));

输出：

array (

    '<10' => 2,

    '10<15' => 1,

    '15<30' => 2,

    '30<' => 1,

  )