循环遍历 1000 个值的最佳方式

Question

我需要找到 x 的值，其中两个结果（将 x 考虑在内）的方差最接近 0。问题是，唯一的方法是循环遍历所有可能的值X。该等式使用货币，所以我必须以 1 分的增量检查。

这可能会更容易：

$previous_var = null;
$high_amount = 50;

for ($i = 0.01; $i <= $high_amount; $i += 0.01) {
    $val1 = find_out_1($i);
    $val2 = find_out_2();

    $var = variance($val1, $val2);

    if ($previous_var == null) {
        $previous_var = $var;
    }

    // If this variance is larger, it means the previous one was the closest to 
    // 0 as the variance has now started increasing
    if ($var > $previous_var) {
        $l_s -= 0.01;
        break;
    }
}

$optimal_monetary_value = $i;

我觉得有一个数学公式可以使 "cycling through every cent" 更优化？它适用于较小的值，但如果您开始使用 1000 作为 $high_amount，则计算需要相当多的时间。

Answer 1

根据您代码中的注释，听起来您想要类似于二分搜索的东西，但又有点不同：

function calculate_variance($i) {
  $val1 = find_out_1($i);
  $val2 = find_out_2();

  return variance($val1, $val2);
}

function search($lo, $loVar, $hi, $hiVar) {
  // find the midpoint between the hi and lo values
  $mid = round($lo + ($hi - $lo) / 2, 2);
  if ($mid == $hi || $mid == $lo) {
    // we have converged, so pick the better value and be done
    return ($hiVar > $loVar) ? $lo : $hi;
  }
  $midVar = calculate_variance($mid);
  if ($midVar >= $loVar) {
    // the optimal point must be in the lower interval
    return search($lo, $loVar, $mid, $midVar);
  } elseif ($midVar >= $hiVar) {
    // the optimal point must be in the higher interval
    return search($mid, $midVar, $hi, $hiVar);
  } else {
    // we don't know where the optimal point is for sure, so check
    // the lower interval first
    $loBest = search($lo, $loVar, $mid, $midVar);
    if ($loBest == $mid) {
      // we can't be sure this is the best answer, so check the hi
      // interval to be sure
      return search($mid, $midVar, $hi, $hiVar);
    } else {
      // we know this is the best answer
      return $loBest;
    }
  }
}

$optimal_monetary_value = search(0.01, calculate_variance(0.01), 50.0, calculate_variance(50.0));

这假设方差在远离最佳点时单调增加。换句话说，如果最优值是O，那么对于所有X < Y < O，calculate_variance(X) >= calculate_variance(Y) >= calculate_variance(O)（和所有>和<翻转一样）。您代码中的注释以及您编写它的方式使它看起来像是真的。如果这不是真的，那么你真的不能比你现在做的更好了。

请注意，这不如对分搜索好。有一些病态输入会使它花费线性时间而不是对数时间（例如，如果所有值的方差都相同）。如果您可以将 calculate_variance(X) >= calculate_variance(Y) >= calculate_variance(O) 的要求改进为 calculate_variance(X) > calculate_variance(Y) > calculate_variance(O)，则可以通过检查 $mid 的方差与 $mid + 0.01 并使用它来决定检查哪个间隔。

此外，您在用货币进行数学计算时可能要小心。您可能想要使用整数（即以美分而不是美元计算所有数学）或使用精确的数字。

Answer 2

如果您对 objective 函数的行为一无所知，那么除了尝试所有可能的值之外别无他法。

相反，如果你能保证最小值是唯一的，那么黄金分割法会很快收敛。这是斐波那契搜索的一个变体，已知它是最优的（需要最少的函数评估次数）。

您的函数可能具有需要其他算法的不同属性。

Answer 3

为什么不实施二进制搜索？

<?php
$high_amount    = 50;
// computed val2 is placed outside the loop
// no need te recalculate it each time
$val2           = find_out_2();
$previous_var   = variance(find_out_1(0.01), $val2);

$start              = 0;
$end                = $high_amount * 100;
$closest_variance   = NULL;
while ($start <= $end) {
    $section    = intval(($start + $end)/2);
    $cursor     = $section / 100;
    $val1       = find_out_1($cursor);
    $variance   = variance($val1, $val2);

    if ($variance <= $previous_var) {
        $start = $section;
    }
    else {
        $closest_variance   = $cursor;
        $end                = $section;
    }
}

if (!is_null($closest_variance)) {
    $closest_variance -= 0.01;
}

循环遍历 1000 个值的最佳方式

Optimal way of cycling through 1000's of values

php

math

mathematical-optimization