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

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

[[424052]]

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

1. 二次時間函數比線性時間函數慢得非常非常多
2. 有時可以通過使用 hashmap 把二次算法變成線性算法
3. 這是因為 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”意為“二次方的”)的原因是：如果 list1 和 list2 的大小為 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 的人能夠更容易理解)

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

1. 將 list1 轉換成名為 set1 的 set 集合
2. 只使用一個 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 <-- 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 很快呢?

現在我將試著解釋為什么 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 個不同元素的列表，這樣的元素數量可以說是很大了!

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

hashmap 查找是即時的(“常數級時間”)

我們看一下快速版程序中的 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 函數 的解釋，其中討論了 hashmap 即時查找的原因。

不經意的二次方：現實中的二次算法!

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

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

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

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

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

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