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

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

我們聊到了 二次時間 quadratic-time 與 線性時間 linear-time 演算法的話題，我認為在這裡寫這篇文章會很有趣，因為避免二次時間演算法不僅在面試中很重要——有時在現實生活中了解一下也是很好的！後面我會快速解釋一下什麼是「二次時間演算法」 🙂

以下是我們將要討論的 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&apos;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 來加速，都會使我感到開心 🙂

via: https://jvns.ca/blog/2021/09/10/hashmaps-make-things-fast/

作者：Julia Evans 選題：lujun9972 譯者：unigeorge 校對：wxy

本文由 LCTT 原創編譯，Linux中國 榮譽推出

本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive