淺談慢速的二次算法與快速的 hashmap

作者：Julia Evans 2021-09-15 15:50:46

我們聊到了二次時(shí)間與線性時(shí)間算法的話題，我認(rèn)為在這里寫這篇文章會(huì)很有趣，因?yàn)楸苊舛螘r(shí)間算法不僅在面試中很重要——有時(shí)在現(xiàn)實(shí)生活中了解一下也是很好的！后面我會(huì)快速解釋一下什么是“二次時(shí)間算法” :)

[[424110]]

大家好！昨天我與一位朋友聊天，他正在準(zhǔn)備編程面試，并試圖學(xué)習(xí)一些算法基礎(chǔ)知識(shí)。

我們聊到了二次時(shí)間quadratic-time與線性時(shí)間linear-time算法的話題，我認(rèn)為在這里寫這篇文章會(huì)很有趣，因?yàn)楸苊舛螘r(shí)間算法不僅在面試中很重要——有時(shí)在現(xiàn)實(shí)生活中了解一下也是很好的！后面我會(huì)快速解釋一下什么是“二次時(shí)間算法” :)

以下是我們將要討論的 3 件事：

二次時(shí)間函數(shù)比線性時(shí)間函數(shù)慢得非常非常多
有時(shí)可以通過使用 hashmap 把二次算法變成線性算法
這是因?yàn)?hashmap 查找非常快（即時(shí)查詢！）

我會(huì)盡量避免使用數(shù)學(xué)術(shù)語，重點(diǎn)關(guān)注真實(shí)的代碼示例以及它們到底有多快/多慢。

目標(biāo)問題：取兩個(gè)列表的交集

我們來討論一個(gè)簡單的面試式問題：獲取 2 個(gè)數(shù)字列表的交集。例如，intersect([1,2,3], [2,4,5]) 應(yīng)該返回 [2]。

這個(gè)問題也是有些現(xiàn)實(shí)應(yīng)用的——你可以假設(shè)有一個(gè)真實(shí)程序，其需求正是取兩個(gè) ID 列表的交集。

“顯而易見”的解決方案：

我們來寫一些獲取 2 個(gè)列表交集的代碼。下面是一個(gè)實(shí)現(xiàn)此需求的程序，命名為 quadratic.py。

import sys
 
# 實(shí)際運(yùn)行的代碼
def intersection(list1, list2):
    result = []
    for x in list1:
        for y in list2:
            if x == y:
                result.append(y)
    return result
 
# 一些樣板，便于我們從命令行運(yùn)行程序，處理不同大小的列表
def run(n):
    # 定義兩個(gè)有 n+1 個(gè)元素的列表
    list1 = list(range(3, n)) + [2]
    list2 = list(range(n+1, 2*n)) + [2]
    # 取其交集并輸出結(jié)果
    print(list(intersection(list1, list2)))
 
# 使用第一個(gè)命令行參數(shù)作為輸入，運(yùn)行程序
run(int(sys.argv[1]))

程序名為 quadratic.py（LCTT 譯注：“quadratic”意為“二次方的”）的原因是：如果 list1 和 list2 的大小為 n，那么內(nèi)層循環(huán)（if x == y）會(huì)運(yùn)行 n^2 次。在數(shù)學(xué)中，像 x^2 這樣的函數(shù)就稱為“二次”函數(shù)。

`quadratic.py` 有多慢？

用一些不同長度的列表來運(yùn)行這個(gè)程序，兩個(gè)列表的交集總是相同的：[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

到目前為止，一切都還不錯(cuò)——程序仍然只花費(fèi)不到 2 秒的時(shí)間。

然后運(yùn)行該程序處理兩個(gè)包含 100,000 個(gè)元素的列表，我不得不等待了很長時(shí)間。結(jié)果如下：

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

這可以說相當(dāng)慢了！總共花費(fèi)了 160 秒，幾乎是在 10,000 個(gè)元素上運(yùn)行時(shí)（1.6 秒）的 100 倍。所以我們可以看到，在某個(gè)點(diǎn)之后，每次我們將列表擴(kuò)大 10 倍，程序運(yùn)行的時(shí)間就會(huì)增加大約 100 倍。

我沒有嘗試在 1,000,000 個(gè)元素上運(yùn)行這個(gè)程序，因?yàn)槲抑浪鼤?huì)花費(fèi)又 100 倍的時(shí)間——可能大約需要 3 個(gè)小時(shí)。我沒時(shí)間這樣做！

你現(xiàn)在大概明白了為什么二次時(shí)間算法會(huì)成為一個(gè)問題——即使是這個(gè)非常簡單的程序也會(huì)很快變得非常緩慢。

快速版：`linear.py`

好，接下來我們編寫一個(gè)快速版的程序。我先給你看看程序的樣子，然后再分析。

import sys
 
# 實(shí)際執(zhí)行的算法
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
 
# 一些樣板，便于我們從命令行運(yùn)行程序，處理不同大小的列表
def run(n):
    # 定義兩個(gè)有 n+1 個(gè)元素的列表
    list1 = range(3, n) + [2]
    list2 = range(n+1, 2*n) + [2]
    # 輸出交集結(jié)果
    print(intersection(list1, list2))
 
run(int(sys.argv[1]))

（這不是最慣用的 Python 使用方式，但我想在盡量避免使用太多 Python 思想的前提下編寫代碼，以便不了解 Python 的人能夠更容易理解）

這里我們做了兩件與慢速版程序不同的事：

將 list1 轉(zhuǎn)換成名為 set1 的 set 集合
只使用一個(gè) for 循環(huán)而不是兩個(gè)

看看 `linear.py` 程序有多快

在討論 為什么 這個(gè)程序快之前，我們先在一些大型列表上運(yùn)行該程序，以此證明它確實(shí)是很快的。此處演示該程序依次在大小為 10 到 10,000,000 的列表上運(yùn)行的過程。（請記住，我們上一個(gè)的程序在 100,000 個(gè)元素上運(yùn)行時(shí)開始變得非常非常慢）

$ 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 <-- quadratic.py took 2 minutes in this case! we're doing it in 0.04 seconds now!!! so fast!
$ time python3 linear.py 1000000 # 1,000,000
[2]
 
real    0m0.178s
$ time python3 linear.py 10000000 # 10,000,000
[2]
 
real    0m1.560s

在極大型列表上運(yùn)行 `linear.py`

如果我們試著在一個(gè)非常非常大的列表（100 億 / 10,000,000,000 個(gè)元素）上運(yùn)行它，那么實(shí)際上會(huì)遇到另一個(gè)問題：它足夠快了（該列表僅比花費(fèi) 4.2 秒的列表大 100 倍，因此我們大概應(yīng)該能在不超過 420 秒的時(shí)間內(nèi)完成），但我的計(jì)算機(jī)沒有足夠的內(nèi)存來存儲(chǔ)列表的所有元素，因此程序在運(yùn)行結(jié)束之前崩潰了。

$ time python3 linear.py 10000000000
Traceback (most recent call last):
  File "/home/bork/work/homepage/linear.py", line 18, in <module>
    run(int(sys.argv[1]))
  File "/home/bork/work/homepage/linear.py", line 13, in run
    list1 = [1] * n + [2]
MemoryError
 
real    0m0.090s
user    0m0.034s
sys 0m0.018s

不過本文不討論內(nèi)存使用，所以我們可以忽略這個(gè)問題。

那么，為什么 `linear.py` 很快呢？

現(xiàn)在我將試著解釋為什么 linear.py 很快。

再看一下我們的代碼:

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

假設(shè) list1 和 list2 都是大約 10,000,000 個(gè)不同元素的列表，這樣的元素?cái)?shù)量可以說是很大了！

那么為什么它還能夠運(yùn)行得如此之快呢？因?yàn)?hashmap！！！

hashmap 查找是即時(shí)的（“常數(shù)級(jí)時(shí)間”）

我們看一下快速版程序中的 if 語句：

if y in set1:
    result.append(y)

你可能會(huì)認(rèn)為如果 set1 包含 1000 萬個(gè)元素，那么這個(gè)查找——if y in set1 會(huì)比 set1 包含 1000 個(gè)元素時(shí)慢。但事實(shí)并非如此！無論 set1 有多大，所需時(shí)間基本是相同的（超級(jí)快）。

這是因?yàn)?nbsp;set1 是一個(gè)哈希集合，它是一種只有鍵沒有值的 hashmap（hashtable）結(jié)構(gòu)。

我不準(zhǔn)備在本文中解釋 為什么 hashmap 查找是即時(shí)的，但是神奇的 Vaidehi Joshi 的 basecs 系列中有關(guān)于 hash table 和 hash 函數(shù) 的解釋，其中討論了 hashmap 即時(shí)查找的原因。

不經(jīng)意的二次方：現(xiàn)實(shí)中的二次算法！

二次時(shí)間算法真的很慢，我們看到的的這個(gè)問題實(shí)際上在現(xiàn)實(shí)中也會(huì)遇到——Nelson Elhage 有一個(gè)很棒的博客，名為不經(jīng)意的二次方，其中有關(guān)于不經(jīng)意以二次時(shí)間算法運(yùn)行代碼導(dǎo)致性能問題的故事。