1

我想知道比较一个数字的三个数值属性并确定最小值和最大值的最快和最有效的方法是什么。假设我有一个带有以下道具的对象

obj.a = 5;
obj.b = 13;
obj.c = 2;

现在我需要计算最小值（2）和最大值（13）；

我的一个选择是使用条件语句，因此有三个条件用于检查最大元素，三个条件用于检查最小元素。导致 6 个条件语句。我的另一个选择是将这些值推送到向量中，然后从排序的向量中检索极值. 有替代方法吗？有什么建议么 ？

4

5 回答 5

2

如果使用 C+11 没问题，你可以这样做：

auto result = std::minmax({a, b, c});

result.first将保持最小值，result.second最大值 - 这是一个现场演示。

于 2013-08-16T07:32:36.763 回答
1

不超过三个比较的解决方案：

struct Obj
{
    int a;
    int b;
    int c;
    std::pair<int,int> getMinMax() const
    {
        std::pair<int,int> minmax = a< b ? std::make_pair(a,b) : std::make_pair(b,a);
        if (c < minmax.first )
            minmax.first = c;
        else if (c > minmax.second)
            minmax.second = c;
        return minmax;
    }
};
于 2013-08-16T05:53:53.813 回答
1

为 2 个变量创建 Min() 函数：

int Min(int x, int y)
{
    return y ^ ((x ^ y) & -(x < y));
}

类似地，2个变量的最大值为：

int Max(int x, int y)
{
    return x ^ ((x ^ y) & -(x < y));
}

现在为您的 3 个变量调用此函数：

int max = Max(a,Max(b,c));
int min = Min(a,Min(b,c));

这些方法非常有效，可用于任意数量的变量比较。

它使用的概念是

  1. 一个数与自身的异或是 0

  2. 数字与 0 的异或是数字本身。

同样，这可用于 N 次数字比较的嵌套调用。

注意：您甚至可以替换x<y为x-y>>31（将 X 视为 32 位有符号整数）。

我非常确定它不能比 3 个数字更有效

于 2013-08-16T06:10:31.597 回答
0

我正在提供伪代码：

a[0] = obj.a
a[1] = obj.b
a[2] = obj.c

要获得最大：

index = int(obj.a < obj.b)
larger = a[index]

largest = a[(larger > obj.c) ? index : 2]

要获得最小的：

index = int (obj.a > obj.b)
smaller = a[index]

smallest = a[(smaller < obj.c) ? index : 2]

进行 2 + 2 次比较。

于 2013-08-16T06:11:20.767 回答
0

一旦你发现 a 是最小值，你就不必再考虑它的最大值了。因此，任何单独确定最小值和最大值的解决方案都是次优的。

订购 3 样东西有 6 种方式：abc acb bac bca cab cba。因此，任何解决方案都无法使用少于 6 个分支。

这个解决方案有 6 个分支，每个案例最多 3 个比较，所以我希望它是最优的：

if (obj.a < obj.b)
{
  if (obj.b < obj.c)
  {
     min = obj.a; max = obj.c;  // abc
  }
  else if (obj.c < obj.a)
  {
     min = obj.c; max = obj.b;  // cab
  }
  else
  {
     min = obj.a; max = obj.b;  // acb
  }
}
else
{
  if (obj.a < obj.c)
  {
     min = obj.b; max = obj.c;  // bac
  }
  else if (obj.c < obj.b)
  {
     min = obj.c; max = obj.a;  // cba
  }
  else
  {
     min = obj.b; max = obj.a;  // bca
  }
}

编辑：显然，这很慢。我想这与条件跳转有关。有条件的移动更好：

也许这个更好，虽然它仍然有一个分支：

if (obj.a < obj.b)
{
   min = std::min(obj.a, obj.c);
   max = std::max(obj.b, obj.c);
}
else
{
   min = std::min(obj.b, obj.c);
   max = std::max(obj.a, obj.c);
}

删除最后一个分支会将其变成其他答案之一：

  min = std::min(std::min(obj.a, obj.b), obj.c);
  max = std::max(std::max(obj.a, obj.b), obj.c);

底线：谁会想到“幼稚”的方法会比全部写出来更快！

于 2013-08-16T08:01:50.797 回答