使用PHP在数组中不循环获取最接近的值

正如作者指出的那样，您可能不需要太担心性能问题，但是您可以尝试一种二进制搜索的变体。这里没有办法跳过搜索，因为你不能切到ksort()。这是我想出来的一个草稿:

//$resene is your input ksort()-ed array, $long is the key which position and neighbours you're trying to find
$keys = array_keys($resene);
$min = reset($keys);
$s = key($keys);   // = 0
$max = end($keys);
$e = key($keys);   // = count($resene)
do {
    $guess = $s + (int)(($long - $min)/($max - $min)*($e - $s));
    if ($keys[$guess] > $long) {
        $e = $guess - 1;
        $max = $keys[$e];
        $min = $keys[++$s];
    } elseif ($keys[$guess] < $long) {
        $s = $guess + 1;
        $min = $keys[$s];
        $max = $keys[--$e];
    }
} while ($keys[$guess] != $long && $e != $s);
echo 'Me = '.$keys[$guess].'; prev = '.$keys[$guess - 1].'; next = '.$keys[$guess + 1];

我在一个包含从0到5,000,000的20,000个随机数的数组上运行了一些测试，并使用该数组的随机目标值，我在3-4个循环中获得了命中。当然，不要忘记检查prev/next是否存在。

如果您可以使用普通索引数组并对其使用普通sort()以避免与array_keys()混淆，那么它将更好地工作。我猜你试图在这里使用键只是为了获得一些速度，你没有任何有用的数组值?如果是这样，您应该切换到索引数组。

如果你不使用k/sort()，而是使用类似这样的东西来找到要插入新值的位置，你可以让它更好地工作。然后你可以使用array_splice()来插入它，并且你已经知道它的位置，因此，prev/next。

在查看了示例中的方法2之后，您想要做的事情变得更加清楚了。我很好奇我能在PHP中得到多少索引，所以这里有一个函数，它给出了和你的相同的结果:

function fast_nearest($array, $value, $exact=false) {
    if (isset($array[$value])) {
        // If exact match found, and searching for exact (not nearest), return result.
        return array($value => $array[$value], 'exact' => true);
    } elseif ($exact || empty($array)) {
        return false;
    }
    // else
    $keys = array_keys($array);
    $min = $keys[0];
    $s = 0;
    $max = end($keys);
    $e = key($keys);
    if ($s == $e) {
        // only one element, it's closest
        return array_merge($array, array('exact' => false));
    } elseif ($value < $min) {
        return array($min => $array[$min], 'exact' => false);
    } elseif ($value > $max) {
        return array($max => $array[$max], 'exact' => false);
    }
    $result = false;
    do {
        $guess = $s + (int)(($value - $min) / ($max - $min) * ($e - $s));
        if ($guess < $s) {
            // oops, off the scale; we found it
            $result = $keys[$s];
        } elseif ($guess > $e) {
            $result = $keys[$e];
        } elseif ($keys[$guess] > $value && $keys[$guess - 1] < $value) {
            // found range
            $result = (($value - $keys[$guess - 1]) < ($keys[$guess] - $value)
                ? $keys[$guess - 1]
                : $keys[$guess]);
        } elseif ($keys[$guess] < $value && $keys[$guess + 1] > $value) {
            $result = (($value - $keys[$guess]) < ($keys[$guess + 1] - $value)
                ? $keys[$guess]
                : $keys[$guess + 1]);
        } elseif ($keys[$guess] > $value) {
            // narrowing search area
            $e = $guess - 1;
            $max = $keys[$e];
        } elseif ($keys[$guess] < $value) {
            $s = $guess + 1;
            $min = $keys[$s];
        }
    } while ($e != $s && $result === false);
    if ($result === false) {
        throw new Exception("Math laws don't work in this universe.");
    }
    return array($result => $array[$result], 'exact' => false);
}

我在顶部编译了分散在函数中的大多数退出场景，并且我还将项目插入到数组中，因为它不会在函数外持续存在。您可以很容易地在找到的位置添加array_splice()。

我对两个函数(你的和我的)运行了速度测试，以比较从1到1,000,000,000的随机数数组(是的，两个函数都有相同的输入):

• 20000件:
  • fast_nearest() - 7.3 ms平均1000次运行
  • nearest() - 207 ms相同1000次运行的平均值
• 200000件:
  • fast_nearest() - 70 ms平均10次运行(抱歉，1000次等待时间太长了)
  • nearest() - 2,798 ms 10次运行的平均值
• 2000000件:
  • fast_nearest() - 937 ms 2次运行的平均值
  • nearest() - 22156 ms 2次运行的平均值

显然，两者都不能很好地处理巨大的数组，所以如果你必须操作这么多的数据-我建议使用类似数据库服务器的适当索引，PHP不是合适的工具。

此处:

$input = 142;
$offset = 0;
while(true){
  if(isset($foo[$input - $offset])){
    $found = array($input - $offset => $foo[$input - $offset]);
    break;
  }  
  if(isset($foo[$input + $offset])){
    $found = array($input - $offset => $foo[$input + $offset]);
    break;
  }      
  $offset++;
}

它应该比标准循环

数组到底有多大?为什么速度很重要?

NVM。你的问题是错误的。我刚刚在一个包含100K个元素的关联数组上对ksort()进行了计时测试。它需要0.07秒。而一个完整的foreach循环，需要0.01秒!