Created 02/06/2020 at 04:34PM

参考leetcode第121题,大值需要在小值之后。

首先初始化一个足够长的数组

用python初始化一个长度为10^4的数组好了

import random

data = [random.randint(0, 100000) for _ in range(10000)]
print(data)

求数组中元素最大的差值是多少

最简单的暴力算法

很容易想到一个暴力算法,时间复杂度为O(n^2),如下:

def diff_violence(data: list) -> int:
    max_val = 0
    list_size = len(data)
    for i in range(list_size):
        for j in range(i + 1, list_size):
            dif = data[j] - data[i]
            if max_val < dif:
                max_val = dif
    return max_val

执行时间:11.581s(在i5笔记本上运行)

优化

动态规划

首先求出每两个相邻元素之间的差值,设为dif,第i个元素与第i-1个元素的差值为dif[i]。设第i个元素与前面元素的最大差值为dp[i],则有dp[i] = max(0, dp[i-1] + dif[i]),转化为代码如下:

def diff_dp_v1(data: list) -> int:
    max_val = 0
    list_size = len(data)

    dif = [0 for _ in range(list_size)]
    for i in range(1, list_size):
        dif[i] = data[i] - data[i - 1]

    dp = [0 for _ in range(list_size)]
    for i in range(1, list_size):
        dp[i] = max(0, dp[i-1] + dif[i])
        max_val = max(max_val, dp[i])

    return max_val

同时处理同一数组,暴力方法用时6.380s,动态规划方法用时0.025s,加速255倍(在i5笔记本上运行)

动态规划改进

优化掉dif和dp数组

def diff_dp_v2(data: list) -> int:
    max_val = 0
    list_size = len(data)

    before = 0
    for i in range(1, list_size):
        before = max(0, before + data[i] - data[i - 1])
        max_val = max(max_val, before)

    return max_val

为了测试改进之后的效果,将数组扩大至2^6,改进前用时1.847s,改进后用时1.084s。

多线程

要用多线程技术来解决这个问题就需要把各个计算模块独立出来,笔者想到的解决方法基于如下思想:

如果将一个数组分为A、B两个部分,那么最后结果可能有两个来源:

  1. A、B分别求值的最大值
  2. B的最大值减去A的最小值

所以,重新改写代码使其可以多线程运行:

from concurrent.futures import ProcessPoolExecutor
from functools import partial
from multiprocessing import cpu_count


def diff_core(data: list):
    max_dif = 0
    list_size = len(data)

    before = 0
    min_val = 1*10**10 + 1
    max_val = -1
    for i in range(list_size):
        if i == 0:
            if data[i] > max_val:
                max_val = data[i]
            if data[i] < min_val:
                min_val = data[i]
        else:
            if data[i] > max_val:
                max_val = data[i]
            if data[i] < min_val:
                min_val = data[i]
            before = max(0, before + data[i] - data[i - 1])
            max_dif = max(max_dif, before)

    return max_dif, min_val, max_val


def diff_multithreading(data: list, num_workers=cpu_count()) -> int:
    executor = ProcessPoolExecutor(max_workers=num_workers)
    futures = []
    data_len = len(data)
    core_len = int(data_len / num_workers)

    for i in range(num_workers):
        futures.append(executor.submit(partial(diff_core,
                                               data[i*core_len:(i+1)*core_len])))
    results = [future.result() for future in futures]

    min_res = [result[1] for result in results]
    max_res = [result[2] for result in results]
    cut_res = max([result[0] for result in results])
    sep_res = list()
    for i in range(num_workers):
        sep_res.append(max_res[i])
        sep_res.append(min_res[i])
    sep_res = diff_core(sep_res)[0]

    return max(cut_res, sep_res)

为了测试多线程的加速效果,将数组扩大至1*10^8,在16核,64G内存的linux服务器上进行测试,结果如下:

最大连续子数组和

可以借鉴上述思想,代码如下:

def max_sum(data: list) -> int:
    max_val = 0
    list_size = len(data)

    before = 0
    for i in range(list_size):
        before = max(before, before + data[i])
        max_val = max(max_val, before)

    return max_val

后记

综上,多线程算法比暴力算法快了1000倍,可以看到不同的算法设计对运行的效率有着巨大的影响。