一千萬個為什麽

搜索

在查找集合中的最小值/最大值時使用類型的最小值/最大值

最初,我最後基本上寫了一篇帶有問題的文章,所以我要把它塞進去:哪個更好(這裏真的很挑剔)?

一個)

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]);

-要麽-

B)

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 初始化為常量值而不是使用索引器來保存一兩條指令。它也感覺不那麽多余 - 沒有將 someArray [0] [0] 與自己進行比較......

As an algorithm, which is better/valid-er.

編輯:假設數組不為null而不是空。
EDIT2:修正了一些粗心的錯誤。

最佳答案

這兩種算法都是正確的(當然,假設數組是非空的)。我認為版本A更常用,因為對於某些類型(特別是字符串),可能沒有明確定義的最大值。

這些算法是等效的原因與一個名為 semilattice 的酷數學對象有關。為了激發半格,有幾個很酷的屬性恰好成立:

  1. max是冪等,因此將其應用於相同的值兩次會返回原始值:max(x,x)= x
  2. max是可交換的,因此將它應用於其參數的順序無關緊要:max(x,y)= max(y,x)
  3. max是 associative ,因此當獲取最多三個或更多值時,如何對元素進行分組並不重要:max(max(x,y),z)= max(x ,max(y,z))

這些法律也適用於最低限度,以及許多其他結構。例如,如果您有樹結構,則“最小上限”運算符也滿足這些約束。類似地,如果你有一組集合並設置了union或intersection,你會發現這些約束同樣存在。

如果你有一組元素(例如,整數,字符串等)和一些二元運算符,它們具有以上三個屬性(冪等性,交換性和關聯性),那麽你找到了一個名為的結構半格。然後,二元運算符稱為 meet運算符(或者有時是 join運算符,具體取決於上下文)。

半格是有用的原因是,如果你有一個(有限的)從半格中繪制的元素集合並想要計算它們的相遇,你可以通過使用這樣的循環來實現:

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

這樣做的原因是因為滿足運算符是可交換的和關聯的,我們可以按照我們想要的任何順序在元素之間應用滿足。因此,當我們遍歷數組的元素時,一次應用它一個元素,因此產生的值與我們首先對數組元素進行混洗,或以相反的順序叠代等相同。在您的情況下,滿足運算符是“ max“或”min“,並且由於它們滿足上述滿足運算符的規律,因此上述代碼將正確計算最大值或最小值。

為了解決您的初始問題,我們需要更多術語。您對將最小值的初始猜測初始化為最大可能整數是否更好或更安全感到好奇。這有效的原因是我們有涼爽的屬性

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

In other words, if you compute the meet of int.MAX_VALUE and any other value, you get the second value back. In mathematical terms, this is because int.MAX_VALUE is the top element of the meet semilattice. More formally, a top element for a meet semilattice is an element (denoted &top;) satisfying

meet(&top;, x) = meet(x, &top;) = x

如果你使用max而不是min,那麽top元素將是 int.MIN_VALUE ,因為

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

Because applying the meet operator to &top; and any other element produces that other element, if you have a meet semilattice with a well-defined top element, you can rewrite the above code to compute the meet of all the elements as

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(x, y) = x if x lexicographically precedes y
           = y otherwise

例如, meet(“a”,“ab”)=“a”meet(“dog”,cat“)=”cat“等。 case,沒有滿足屬性meet(s,x)= meet(x,s)= x的字符串s,所以半格沒有top元素。在這種情況下,你不可能使用第二個版本的代碼,因為沒有頂級元素可以初始化初始值。

However, there is a very cute technique you can use to fake this, which actually does end up getting used a bit in practice. Given a semilattice with no top element, you can create a new semilattice that does have a top element by introducing a new element &top; and arbitrarily defining that meet(&top;, x) = meet(x, &top;) = x. In other words, this element is specially crafted to be a top element and has no significance otherwise.

在代碼中,您可以通過編寫隱式地引入這樣的元素

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 設置為等於該數組元素。

希望這可以幫助!對不起,如果這太理論化......我碰巧喜歡數學。 :-)

轉載註明原文: 在查找集合中的最小值/最大值時使用類型的最小值/最大值