[[424110]]

大家好！昨天我與一位朋友聊天，他正在準備編程面試，并試圖學習一些算法基礎知識。

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

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

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

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

目標問題：取兩個列表的交集

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

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

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

我們來寫一些獲取 2 個列表交集的代碼。下面是一個實現(xiàn)此需求的程序，命名為 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)))
 
# 使用第一個命令行參數(shù)作為輸入，運行程序
run(int(sys.argv[1]))

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

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 個小時。我沒時間這樣做！

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

快速版：linear.py

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

import sys
 
# 實際執(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
 
# 一些樣板，便于我們從命令行運行程序，處理不同大小的列表
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 的人能夠更容易理解）

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

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

看看 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 <-- 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

在極大型列表上運行 linear.py

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

$ 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

不過本文不討論內存使用，所以我們可以忽略這個問題。

那么，為什么 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

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

那么為什么它還能夠運行得如此之快呢？因為 hashmap！！！

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

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

if y in set1:
    result.append(y)

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

這是因為 set1 是一個哈希集合，它是一種只有鍵沒有值的 hashmap（hashtable）結構。

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

不經意的二次方：現(xiàn)實中的二次算法！

二次時間算法真的很慢，我們看到的的這個問題實際上在現(xiàn)實中也會遇到——Nelson Elhage 有一個很棒的博客，名為 不經意的二次方，其中有關于不經意以二次時間算法運行代碼導致性能問題的故事。

二次時間算法可能會“偷襲”你

關于二次時間算法的奇怪之處在于，當你在少量元素（如 1000）上運行它們時，它看起來并沒有那么糟糕！沒那么慢！但是如果你給它 1,000,000 個元素，它真的會花費幾個小時去運行。

所以我認為它還是值得深入了解的，這樣你就可以避免無意中使用二次時間算法，特別是當有一種簡單的方法來編寫線性時間算法（例如使用 hashmap）時。

總是讓我感到一絲神奇的 hashmap

hashmap 當然不是魔法（你可以學習一下為什么 hashmap 查找是即時的！真的很酷！），但它總是讓人 感覺 有點神奇，每次我在程序中使用 hashmap 來加速，都會使我感到開心 :)