第8题: 序列中的最大乘积

Problem 8: Largest Product in a Series

 收录于 欧拉计划
  约 1500 字 预计阅读 3 分钟 

题目

序列中的最大乘积

在下面的$1000$位数中，相邻四位数的最大乘积是$9\ast9\ast8\ast9=5832$。

从下面$1000$位数中，找到相邻的$13$位数的乘积的最大值。

$$ 73167176531330624919225119674426574742355349194934 \\ 96983520312774506326239578318016984801869478851843 \\ 85861560789112949495459501737958331952853208805511 \\ 12540698747158523863050715693290963295227443043557 \\ 66896648950445244523161731856403098711121722383113 \\ 62229893423380308135336276614282806444486645238749 \\ 30358907296290491560440772390713810515859307960866 \\ 70172427121883998797908792274921901699720888093776 \\ 65727333001053367881220235421809751254540594752243 \\ 52584907711670556013604839586446706324415722155397 \\ 53697817977846174064955149290862569321978468622482 \\ 83972241375657056057490261407972968652414535100474 \\ 82166370484403199890008895243450658541227588666881 \\ 16427171479924442928230863465674813919123162824586 \\ 17866458359124566529476545682848912883142607690042 \\ 24219022671055626321111109370544217506941658960408 \\ 07198403850962455444362981230987879927244284909188 \\ 84580156166097919133875499200524063689912560717606 \\ 05886116467109405077541002256983155200055935729725 \\ 71636269561882670428252483600823257530420752963450 \\ $$

Largest Product in a Series

The four adjacent digits in the $1000$-digit number that have the greatest product are $9\ast9\ast8\ast9=5832$.

$$ 73167176531330624919225119674426574742355349194934 \\ \vdots \\ 71636269561882670428252483600823257530420752963450 \\ $$

Find the thirteen adjacent digits in the $1000$-digit number that have the greatest product. What is the value of this product?

解题方法

使用滑动窗口算法来解最大乘积。时间复杂度为 $O(N)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

std::uint64_t Product1(const std::string_view& Num, std::size_t size) {
    std::uint64_t result = 0;
    std::uint64_t temp = 1;
    for (std::size_t i = 0; i + size <= Num.size(); ++i) {
        temp = 1;
        for (std::size_t j = 0; j < size; ++j) {
            temp *= Num[i + j] - '0';
        }
        if (temp > result) {
            result = temp;
        }
    }
    return result;
}

基于 现代C++ 的实现

滑动窗口可以考虑使用 现代C++ 中的范围库、算法库、并行支持库、模板元编程等内容实现。

各个版本

一、使用std::views::adjacent_transform和std::ranges::max

1
2
3
4
5

template<std::size_t SIZE>
std::uint64_t Product2(const std::string_view Num) {
    auto product = [](auto... window) -> std::uint64_t { return (std::uint64_t(window - '0') * ...); };
    return std::ranges::max(Num | std::views::adjacent_transform<SIZE>(product));
}

二、使用std::views::slide、std::views::transform和std::ranges::max

1
2
3
4
5
6
7
8
9

template<std::size_t SIZE>
std::uint64_t Product3(const std::string_view Num) {
    auto product = [](auto&& window) -> std::uint64_t {
        return [&window] <std::size_t... INDEX>(std::index_sequence<INDEX...>) -> std::uint64_t {
            return ((std::uint64_t(window[INDEX] - '0')) * ...);
        }(std::make_index_sequence<SIZE>{});
        };
    return std::ranges::max(Num | std::views::slide(SIZE) | std::views::transform(product));
}

三、使用并行std::for_each和std::views::slide

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

template<std::size_t SIZE>
std::uint64_t Product4(const std::string_view Num) {
    std::atomic<std::uint64_t> result = 0;
    const auto& windows = Num | std::views::slide(SIZE); // 生成滑块
    std::for_each(std::execution::par, std::begin(windows), std::end(windows), [&result](auto&& window) {
        std::uint64_t product = [&window]<std::size_t... INDEX>(std::index_sequence<INDEX...>) -> std::uint64_t {
            return ((std::uint64_t(window[INDEX] - '0')) * ...);
        }(std::make_index_sequence<SIZE>{});
        std::uint64_t old = result.load();
        while (true) {
            if (old >= product || result.compare_exchange_weak(old, product)) {
                break;
            }
        }
        }
    );
    return result.load();
}

三、使用并行std::for_each和std::views::adjacent

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

template<std::size_t SIZE>
std::uint64_t Product5(const std::string_view Num) {
    std::atomic<std::uint64_t> result = 0;
    const auto& windows = Num | std::views::adjacent<SIZE>; // 生成滑块
    std::for_each(std::execution::par, std::begin(windows), std::end(windows), [&result](auto&& window) {
        std::uint64_t product = [&]<std::size_t... INDEX>(std::index_sequence<INDEX...>) -> std::uint64_t {
            return ((std::uint64_t(std::get<INDEX>(window) - '0')) * ...);
        }(std::make_index_sequence<SIZE>{});
        std::uint64_t old = result.load();
        while (true) {
            if (old >= product || result.compare_exchange_weak(old, product)) {
                break;
            }
        }
        }
    );
    return result.load();
}

三、使用并行std::for_each、std::views::slide和std::reduce

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

std::uint64_t Product6(const std::string_view Num, std::size_t size) {
    std::atomic<std::uint64_t> result = 0;
    const auto& windows = Num | std::views::slide(size); // 生成滑块
    // 此处使用 par 创建多个线程同步处理数据
    // 此处调用的 function 不支持矢量化，因此不使用 unseq
    std::for_each(std::execution::par, std::begin(windows), std::end(windows), [&result](std::ranges::viewable_range auto&& window) {
        // 因为大量的调用 std::reduce，使用 par 会大量性能消耗在线程的创建和销毁上
        // 因为此处 reduce 调用的 function 不是简单的二元乘法运算，因此不使用 unseq
        // 注：MSVC 的 std::reduce 不支持 unseq
        // 注：GCC 中 std::uint64_t 和 1llu 类型不同
        std::uint64_t product = std::reduce(std::execution::seq, std::begin(window), std::end(window), std::uint64_t(1llu), []<class T1, class T2>(T1 f, T2 l) -> std::uint64_t {
            if constexpr (std::is_same_v<std::remove_cvref_t<T1>, std::uint64_t> && std::is_same_v<std::remove_cvref_t<T2>, std::uint64_t>) {
                return f * l;
            }
            else if constexpr (std::is_same_v<std::remove_cvref_t<T1>, char> && std::is_same_v<std::remove_cvref_t<T2>, char>) {
                return static_cast<std::uint64_t>(f - '0') * static_cast<std::uint64_t>(l - '0');
            }
            else if constexpr (std::is_same_v<std::remove_cvref_t<T1>, std::uint64_t> && std::is_same_v<std::remove_cvref_t<T2>, char>) {
                return f * static_cast<std::uint64_t>(l - '0');
            }
            else if constexpr (std::is_same_v<std::remove_cvref_t<T1>, char> && std::is_same_v<std::remove_cvref_t<T2>, std::uint64_t>) {
                return static_cast<std::uint64_t>(f - '0') * l;
            }
            else {
                throw std::runtime_error("The parameter is of unknown type.");
            }
        });
        std::uint64_t old = result.load();
        while (true) {
            if (old >= product || result.compare_exchange_weak(old, product)) {
                break;
            }
        }
        }
    );
    return result.load();
}

速度测试

针对不同长度的数据量进行测试，使用1'000字节长度（str_1k）和100'000'000字节长度（str_100m）的字符串进行测试。

在Visual Studio 2022最新版下测试结果如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

str_1k     Product1:      755116655247360        103us
str_1k     Product2:      755116655247360        122us    0.84426
str_1k     Product3:      755116655247360         60us    1.71667
str_1k     Product4:      755116655247360        313us    0.32907
str_1k     Product5:      755116655247360        324us    0.31790
str_1k     Product6:      755116655247360        182us    0.56593
str_100m   Product1:   431883715732439040   11152558us
str_100m   Product2:   431883715732439040   15882062us    0.70221
str_100m   Product3:   431883715732439040    8334643us    1.33810
str_100m   Product4:   431883715732439040     838828us   13.29541
str_100m   Product5:   431883715732439040    1502017us    7.42505
str_100m   Product6:   431883715732439040    1269302us    8.78637

由测试结果可知，在数据量较少时，仅Product3速度会超过纯循环的版本，当数据量提升到100'000'000字节时，并行版的函数会有速度提升。

注意
不同编译器拥有不同的标准库实现，可能存在差异。

正确答案

答案
23514624000

参考链接

更新于 2024-04-02 
CC BY-NC 4.0
阅读原始文档
欧拉计划第1-99题滑动窗口现代C++最大乘积
返回 | 主页
0%