Rust 在1.5n次比较中找到整数向量中的最大和次大整数

算法rithm

我预计@Greybeard发表了关键的 comments in their answer:

无论如何，如果你将每个元素与目前的第二大元素进行比较，我预计与最大值的比较将变得越来越不可能.

原因是，如果输入是随机的，那么:

• 上半年的最大值，可能是下半年最大的值之一.
• 上半年的第二大价值也是如此.

在极端情况下，假设最大的两个值是您开始的前两个值:

• 与最大的第一个和第二大的第二个进行比较，如果值低于第一个，则always将导致两次比较.
• 与第二个最大的第一个比较，如果值大于第二个，则与第二个最大的第二个比较将导致单次比较.

当然，你不会马上知道是最大的还是第二大的.平均而言，您在查看50%的元素后就会知道它们，因此您将在前半部分对每个元素进行2次比较，在后半部分对每个元素进行1次比较，总共进行1.5N次比较.

Rusting it up

我们应该在表格上签个名:

fn max_pairwise_product(values: &[i64]) -> Option<i64>;

首先，如果values是空的，就不会有任何类型的产品.

其次，注意使用&[i64]作为参数，而不是&Vec<i64>:它更通用.你可以从Vec<T>,VecDeque<T>,[T; N]得&[T]分...

Imperative

让我们首先进行必要的编码(Playground link):

fn max_pairwise_product(values: &[i64]) -> Option<i64> {
    //  `[T]::get` returns an `Option<&T>`.
    //  `Option<&T>::copied` returns an `Option<T>`, if `T` is `Copy.
    //  `?` short-circuits the operation when things don't work out.
    let first = values.get(0).copied()?;
    let second = values.get(1).copied()?;

    //  Can be expressed as `(first.max(second), first.min(second))` too.
    let (mut first, mut second) = if first > second {
        (first, second)
    } else {
        (second, first)
    };

    //  And from then, we scan the rest of the values using sub-slicing to
    //  express that we want to skip the first 2 values.
    //  The `&` in front of `v` is pattern-matching to make `v` a value,
    //  instead of a reference.
    for &v in &values[2..] {
        if v <= second {
            continue;
        }

        if v <= first {
            second = v;
            continue;
        }

        second = first;
        first = v;
    }

    Some(first * second)
}

Functional

然而，Ruust确实有更多的技巧，特别是模式匹配(更多)和用Iterator个方法替换循环可以产生相当不错的代码.

实际上，相同的算法可以表示为(Playground link):

fn max_pairwise_product(values: &[i64]) -> Option<i64> {
    //  The all-powerful `let .. else` form of pattern-matching, the "my way
    //  or the highway" style of matching for quickly getting out of here.
    let [first, second, tail @ ..] = values else { return None };

    let (first, second) = (first.max(second), first.min(second));

    let (first, second) = tail
        .iter()
        .copied()
        .fold((*first, *second), |(first, second), v| {
            if v <= second {
                (first, second)
            } else if v <= first {
                (first, v)
            } else {
                (v, first)
            }
        });

    Some(first * second)
}

这是使用切片上的模式匹配以可视的方式提取元素(尽管tail @ ..部分目前只在晚上)，以及强大的fold算法.