遅い二次アルゴリズムと高速ハッシュマップについての簡単な説明

[[424110]]

こんにちは、みんな！昨日、プログラミング面接の準備をしていて、アルゴリズムの基礎を学ぼうとしている友人とチャットをしていました。

私たちは話しました二次時間二次時間そして線形時間線形時間アルゴリズムの話題については、ここでそれについて書くのは楽しいだろうと思いました。なぜなら、二次時間アルゴリズムを避けることは、面接で重要であるだけでなく、実生活でそれについて知っておくと便利な場合があるからです。「二次時間アルゴリズム」とは何かについては後で簡単に説明します :)

ここで議論する 3 つの事項は次のとおりです。

二次関数は一次関数よりもはるかに遅い
ハッシュマップを使うことで、二次アルゴリズムを線形アルゴリズムに変換できる場合がある。
これは、ハッシュマップの検索が非常に高速であるためです (即時検索!)

数学の専門用語は避け、実際のコード例と、実際にどれくらい速いか遅いかに焦点を当てたいと思います。

目標問題: 2つのリストの共通部分を見つける

2 つの数値リストの共通部分を取得するという、簡単なインタビュー形式の問題について説明しましょう。たとえば、 intersect([1,2,3], [2,4,5]) [2]を返します。

この問題には現実世界への応用もいくつかあります。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なのは、 list1とlist2のサイズがnの場合、内部ループ ( if x == y ) がn^2回実行されるためです。数学では、 x^2のような関数は「二次」関数と呼ばれます。

`quadratic.py`はどれくらい遅いですか?

このプログラムを異なる長さのリストで実行すると、2つのリストの共通部分は常に同じになります: [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 要素の 2 つのリストでプログラムを実行しましたが、長い時間待たなければなりませんでした。結果は次のとおりです。

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

かなり遅いですね！これには合計 160 秒かかり、10,000 要素で実行した場合 (1.6 秒) のほぼ 100 倍の時間がかかりました。したがって、ある時点以降、リストを 10 倍大きくするたびに、プログラムの実行にかかる時間が約 100 倍長くなることがわかります。

このプログラムを 1,000,000 個の要素で実行しようとはしませんでした。100 倍の時間がかかることがわかっていたからです (おそらく 3 時間程度)。こんな時間はないよ！

おそらくこれで、2 次時間アルゴリズムがなぜ問題になるのかがお分かりいただけたと思います。この非常に単純なプログラムでさえ、すぐに非常に遅くなる可能性があるのです。

高速バージョン: `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 のアイデアをあまり使用せずにコードを書きたかったのです)

ここでは、低速バージョンとは異なる 2 つのことを行います。

list1 set1という名前のセットに変換します。
2つのforループではなく1つの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 個の異なる要素を持つリストであるとします。この要素数は非常に大きいと言えます。

では、なぜそんなに速く走るのでしょうか?ハッシュマップのせいだ！！！

ハッシュマップの検索は瞬時に行われます（「一定時間」）

プログラムのクイックバージョンのifステートメントを見てみましょう。

 if y in set1 :
 result . append ( y )

set1 1,000 万の要素が含まれている場合、 if y in set1検索は、 set1に 1,000 の要素が含まれている場合よりも遅くなると思われるかもしれません。しかし、そうではありません！ set1がどれだけ大きくても、必要な時間は基本的に同じです (超高速)。

これは、 set1がハッシュセットであり、キーのみで値のないハッシュマップ (ハッシュテーブル) 構造であるためです。

この記事ではハッシュマップ検索がなぜ瞬時に行われるのかについては説明しません。ただし、ハッシュテーブルとハッシュ関数に関する Vaidehi Joshi の素晴らしい basecs シリーズでは、ハッシュマップ検索がなぜ瞬時に行われるのかについて説明しています。

偶然の二次方程式: 現実世界における二次方程式アルゴリズム!

2 次時間アルゴリズムは非常に遅く、私たちが目にする問題は現実世界で実際に遭遇したものです。Nelson Elhage は、Accidentally Quadratic という素晴らしいブログを運営しており、そこには、誤って 2 次時間でコードを実行し、パフォーマンスの問題を引き起こした事例が紹介されています。