浅谈慢速的二次算法与快速的 hashmap

2024年 7月 17日 61.5k 0

浅谈慢速的二次算法与快速的 hashmap-1

大家好!昨天我与一位朋友聊天,他正在准备编程面试,并试图学习一些算法基础知识。

我们聊到了 二次时间 quadratic-time 与 线性时间 linear-time 算法的话题,我认为在这里写这篇文章会很有趣,因为避免二次时间算法不仅在面试中很重要——有时在现实生活中了解一下也是很好的!后面我会快速解释一下什么是“二次时间算法” 🙂

以下是我们将要讨论的 3 件事:

  • 二次时间函数比线性时间函数慢得非常非常多
  • 有时可以通过使用 hashmap 把二次算法变成线性算法
  • 这是因为 hashmap 查找非常快(即时查询!)
  • 我会尽量避免使用数学术语,重点关注真实的代码示例以及它们到底有多快/多慢。

    目标问题:取两个列表的交集

    我们来讨论一个简单的面试式问题:获取 2 个数字列表的交集。 例如,intersect([1,2,3], [2,4,5]) 应该返回 [2]

    这个问题也是有些现实应用的——你可以假设有一个真实程序,其需求正是取两个 ID 列表的交集。

    “显而易见”的解决方案:

    我们来写一些获取 2 个列表交集的代码。下面是一个实现此需求的程序,命名为 quadratic.py

    import sys
    
    # 实际运行的代码
    def intersection(list1, list2):
        result = []
        for x in list1:
            for y in list2:
                if x == y:
                    result.append(y)
        return result
    
    # 一些样板,便于我们从命令行运行程序,处理不同大小的列表
    def run(n):
        # 定义两个有 n+1 个元素的列表
        list1 = list(range(3, n)) + [2]
        list2 = list(range(n+1, 2*n)) + [2]
        # 取其交集并输出结果
        print(list(intersection(list1, list2)))
    
    # 使用第一个命令行参数作为输入,运行程序
    run(int(sys.argv[1]))
    

    程序名为 quadratic.py(LCTT 译注:“quadratic”意为“二次方的”)的原因是:如果 list1list2 的大小为 n,那么内层循环(if x == y)会运行 n^2 次。在数学中,像 x^2 这样的函数就称为“二次”函数。

    quadratic.py 有多慢?

    用一些不同长度的列表来运行这个程序,两个列表的交集总是相同的:[2]

    $ time python3 quadratic.py 10
    [2]
    
    real    0m0.037s
    $ time python3 quadratic.py 100
    [2]
    
    real    0m0.053s
    $ time python3 quadratic.py 1000
    [2]
    
    real    0m0.051s
    $ time python3 quadratic.py 10000 # 10,000
    [2]
    
    real    0m1.661s
    

    到目前为止,一切都还不错——程序仍然只花费不到 2 秒的时间。

    然后运行该程序处理两个包含 100,000 个元素的列表,我不得不等待了很长时间。结果如下:

    $ time python3 quadratic.py 100000 # 100,000
    [2]
    
    real    2m41.059s
    

    这可以说相当慢了!总共花费了 160 秒,几乎是在 10,000 个元素上运行时(1.6 秒)的 100 倍。所以我们可以看到,在某个点之后,每次我们将列表扩大 10 倍,程序运行的时间就会增加大约 100 倍。

    我没有尝试在 1,000,000 个元素上运行这个程序,因为我知道它会花费又 100 倍的时间——可能大约需要 3 个小时。我没时间这样做!

    你现在大概明白了为什么二次时间算法会成为一个问题——即使是这个非常简单的程序也会很快变得非常缓慢。

    快速版:linear.py

    好,接下来我们编写一个快速版的程序。我先给你看看程序的样子,然后再分析。

    import sys
    
    # 实际执行的算法
    def intersection(list1, list2):
        set1 = set(list1) # this is a hash set
        result = []
        for y in list2:
            if y in set1:
                result.append(y)
        return result
    
    # 一些样板,便于我们从命令行运行程序,处理不同大小的列表
    def run(n):
        # 定义两个有 n+1 个元素的列表
        list1 = range(3, n) + [2]
        list2 = range(n+1, 2*n) + [2]
        # 输出交集结果
        print(intersection(list1, list2))
    
    run(int(sys.argv[1]))
    

    (这不是最惯用的 Python 使用方式,但我想在尽量避免使用太多 Python 思想的前提下编写代码,以便不了解 Python 的人能够更容易理解)

    这里我们做了两件与慢速版程序不同的事:

  • list1 转换成名为 set1 的 set 集合
  • 只使用一个 for 循环而不是两个
  • 看看 linear.py 程序有多快

    在讨论 为什么 这个程序快之前,我们先在一些大型列表上运行该程序,以此证明它确实是很快的。此处演示该程序依次在大小为 10 到 10,000,000 的列表上运行的过程。(请记住,我们上一个的程序在 100,000 个元素上运行时开始变得非常非常慢)

    $ time python3 linear.py 100
    [2]

    real 0m0.056s
    $ time python3 linear.py 1000
    [2]

    real 0m0.036s
    $ time python3 linear.py 10000 # 10,000
    [2]

    real 0m0.028s
    $ time python3 linear.py 100000 # 100,000
    [2]

    real 0m0.048s

    相关文章

    Linux 命令行的聊天工具 CenterIM
    Linux 桌面年仍未到来 但 Linux 移动之年已到来
    12 个在线学习 Linux 技能网站
    Linux Mint : 会是另一个新的 Ubuntu 吗?
    W3Conf 开发者大会将于下周召开
    Ubuntu 10.04 ARM 处理器上网本版本结束服务期

    发布评论