algorithm - 在集合中查找最小值/最大值时，使用一种类型的最小值/最大值

Question

最初，我基本上写了一篇文章，结尾有一个问题，所以我要把它塞进下面：哪个更好（这里真的很挑剔）？
（一）

int min = someArray[0][0];
for (int i = 0; i < someArray.length; i++)
    for (int j = 0; j < someArray[i].length; j++)
        min = Math.min(min, someArray[i][j]);

-或者-
（二）

int min = int.MAX_VALUE;
for (int i = 0; i < someArray.length; i++)
     for (int j = 0; j < someArray[i].length; j++)
         min = Math.min(min, someArray[i][j]);

我认为b更快，通过将min初始化为常量而不是使用索引器来保存一两条指令。它也感觉不那么多余-没有比它本身更多余…
作为一种算法，这是一种较好/有效的er。
编辑：假设数组不为空。
编辑2：修正了几个粗心的错误。

Answer 1

这两种算法都是正确的（当然，假设数组是非空的）。我认为版本A工作更一般，因为对于某些类型（字符串，特别是），可能没有明确定义的最大值。
这些算法等价的原因与一个很酷的数学对象asemilattice有关为了激发半格，有几个很酷的max性质恰好成立：
max是等幂的，所以对同一个值应用它两次会返回原始值：max（x，x）=x
max是可交换的，所以对它的参数应用它的顺序无关紧要：max（x，y）=max（y，x）
max是相联的，所以当取最大值为三或更多的值时，对元素如何分组并不重要：max（max（x，y），z）＝max（x，max（y，z））。
这些法律也适用于最低限度，以及许多其他结构。例如，如果有树结构，“最小上界”运算符也满足这些约束。类似地，如果您有一个集合和集合并集或交集，您会发现这些约束也适用。
如果有一组元素（例如，整数、字符串等）和一些在它们上面定义的具有上述三个属性（幂等性、交换性和结合性）的二元运算符，那么就找到了一个称为半格的结构。然后，二进制运算符被称为meet运算符（有时根据上下文称为join运算符）。
半格之所以有用，是因为如果您有一个从半格中提取的元素（有限）集合，并且想要计算它们的相交，那么您可以使用这样的循环：

Element e = data[0];
for (i in data[1 .. n])
    e = meet(e, data[i])

这样做的原因是因为meet算子是可交换的和关联的，所以我们可以在元素之间以任何我们想要的顺序应用meet。当我们按顺序遍历数组元素时，一次应用一个元素，因此产生的值与我们首先对数组元素进行无序排列或按相反顺序迭代时的值相同。在您的示例中，meet运算符是“max”或“min”，“由于它们满足上述满足算子的定律，上述代码将正确计算最大值或最小值。
为了解决你最初的问题，我们需要更多的术语。您对是否将初始值的初始猜测初始化为最大可能整数更好或更安全，感到好奇。之所以有效，是因为我们拥有

min(int.MAX_VALUE, x) = min(x, int.MAX_VALUE) = x

换句话说，如果计算int.MAX_VALUE和任何其他值的交集，就会得到第二个值用数学术语来说，这是因为int.MAX_VALUE是满足半格的顶元素。更正式地说，满足半格的顶元素是满足的元素（表示为）
满足（，x）=满足（x，）=x
如果使用max而不是min，那么顶部元素将是int.MIN_VALUE，因为

max(int.MIN_VALUE, x) = max(x, int.MIN_VALUE) = x

因为将meet运算符应用于和任何其他元素都会生成该其他元素，所以如果有一个具有定义良好的顶部元素的meet半格，则可以重写上述代码来计算所有元素的meet

Element e = Element.TOP;
for (i in data[0 .. n])
    e = meet(e, data[i])

这是因为在第一次迭代之后，e被设置为meet(e, data[0]) = meet(Element.TOP, data[0]) = data[0]并且迭代照常进行。因此，在最初的问题中，使用两个循环中的哪一个并不重要；只要定义了至少一个元素，它们就会产生相同的值。
也就是说，并不是所有的半格都有顶元素例如，考虑所有字符串的集合，其中meet运算符定义为

meet(x, y) = x if x lexicographically precedes y
           = y otherwise

例如，meet("a", "ab") = "a"，meet("dog, "cat") = "cat"等。在这种情况下，没有满足属性meet（s，x）=meet（x，s）=x的字符串，因此半格没有顶元素。在这种情况下，您可能无法使用代码的第二个版本，因为没有可以将初始值初始化为的顶级元素。
然而，有一个非常可爱的技巧，你可以用来假装这一点，这实际上最终得到了一些实际应用给定一个没有顶元素的半格，通过引入一个新元素，并任意定义meet（，x）=meet（x，）=x，就可以创建一个有顶元素的新半格。换句话说，这个元素是经过精心设计而成的顶元素，否则没有任何意义。
在代码中，可以通过编写

bool found = false;
Element e;

for (i in data[0 .. n]) {
    if (!found) {
        found = true;
        e = i;
    } else {
        e = meet(e, i);
    }
}

这段代码的工作原理是让一个外部布尔值found跟踪我们是否已经看到了第一个元素。如果没有，那么我们假设元素e是这个新的顶级元素。计算这个顶部元素和数组元素的交集生成数组元素，因此我们可以将元素e设置为等于该数组元素。
希望这有帮助！抱歉，如果这太理论化了…我只是碰巧喜欢数学。：-）