时间戳

首页 > 解决方案 > 通过表达式查找最佳匹配

performance - 通过表达式查找最佳匹配

问题描述

背景

假设您有一个数字数组，并且您想找到最接近某个预定值的数字。

示例，没有特定的语言：

baseValue = 6
array = [1, 3, 5, 8, 9, 11, 13]
// 5 is the value closest to 6, and is the expected return value

我们可以通过跟踪当前的最佳匹配来解决这个问题，如下所示：

for value in array
    diff = abs(value - baseValue)
    if (diff < currentBestMatch)
        currentBestMatch = diff

// And at this point, currentBestMatch fits its name

但是这段代码是不完整的，因为currentBestMatch我们进入循环时没有初始化，所以比较diff < currentBestMatch会中断。

可能的解决方案

  1. currentBestValue例如，在循环之前实例化-1，并将 if 条件扩展为 if (diff < currentBestMatch OR currentBestMatch == -1)

  2. 实例化为currentBestValue一些可笑的高但任意的值，例如该类型的最大允许数量，以便第一次检查将始终给出更好的匹配

可能的问题

  1. 第一个解决方案感觉不对，因为现在我们必须执行currentBestMatch检查。好吧，从技术上讲不是，因为 if 条件应该在大多数语言的第一个条件上触发。但是，它仍然感觉像是一段不合时宜的代码。

  2. 第二种解决方案感觉有点不对劲，因为如果可笑的高值实际上低于最佳匹配怎么办？更不用说，为此目的存储可笑的高值的内存成本是多少？可能我们不会注意到这一点，但是如果我们继续这样编程呢？

问题

有没有更理智的方法来解决这个感觉更干净的问题？我知道这是一种随意的定义，但我想这里的大多数人都会明白我的意思。

标签： performanceoptimization

解决方案

而不是使用硬编码值-1或inf使用数组中的实际值。如果数组为空，则无论如何都必须处理这种情况（可能会抛出异常），因此访问数组中的第一个条目是安全的。

顺便说一句：而不是currentBestMatch = diff你可能的意思是currentBestMatch = value因为你想“找到最接近某个预定值的数字”而不是“差异”。

伪代码：

if array is empty
   throw exception
diff = abs(array[0] - baseValue)
currentBestMatch = array[0]
for value in array starting at the second entry
    diff = abs(value - baseValue)
    if (diff < currentBestMatch)
        currentBestMatch = value

这里有一个小的代码重复。你可以转移abs(... - ...)到它自己的功能。但这与使用argmin(array, x -> abs(x-baseValue)).

推荐阅读