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

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

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

[[424052]]

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

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

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

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

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

この問題には現実世界への応用もいくつかあります。2 つの ID リストの正確な交差を必要とする実際のプログラムを想像してみてください。

「明白な」解決策:

2 つのリストの共通部分を取得するコードを書いてみましょう。以下は、この要件を実装する quadratic.py という名前のプログラムです。

インポートシステム
# 実際の実行コード
交差を定義します(リスト1、リスト2):
    結果 = []
 list1のxの場合:
リスト2のyについて:
            x == yの場合:
                結果.append(y)
結果を返す
# コマンドラインからプログラムを実行し、さまざまなサイズのリストを扱いやすくするための定型文
def run(n):
    # n+1 個の要素を持つ 2 つのリストを定義する
    リスト1 = リスト(範囲(3, n)) + [2]
    リスト2 = リスト(範囲(n+1, 2*n)) + [2]
    # 交差を取って結果を出力します
    print(リスト(交差(リスト1, リスト2)))
 # 最初のコマンドライン引数を入力として使用してプログラムを実行します
実行( int (sys.argv[1]))

プログラムの名前が quadratic.py なのは、list1 と list2 のサイズが n の場合、内部ループ (x == y の場合) が n^2 回実行されるためです。数学では、x^2 のような関数は「二次」関数と呼ばれます。

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

このプログラムを異なる長さのリストで実行すると、2つのリストの交差は常に同じになります: [2]。

 $時間python3 quadratic.py 10
 [2]
実数0分0.037秒
$時間python3 quadratic.py 100
 [2]
実数0分0.053秒
$時間python3 quadratic.py 1000
 [2]
実数0分0.051秒
$時間python3 quadratic.py 10000 # 10,000
 [2]
実数0分1.661秒

これまでのところ順調です。プログラムの実行時間は依然として 2 秒未満です。

次に、それぞれ 100,000 要素の 2 つのリストでプログラムを実行しましたが、長い時間待たなければなりませんでした。結果は次のとおりです。

 $時間python3 quadratic.py 100000 # 100,000
 [2]
実数2分41秒059

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

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

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

高速バージョン: linear.py

さて、プログラムの簡単なバージョンを書いてみましょう。まずプログラムがどのようなものかを示し、その後分析します。

インポートシステム
# 実際に実行されるアルゴリズム
交差を定義します(リスト1、リスト2):
    set1 = set (list1) # これはハッシュセットです 
    結果 = []
リスト2のyについて:
        yがset1にある場合:
            結果.append(y)
結果を返す
# コマンドラインからプログラムを実行し、さまざまなサイズのリストを扱いやすくするための定型文
def run(n):
    # n+1 個の要素を持つ 2 つのリストを定義する
    リスト1 = 範囲(3, n) + [2]
    リスト2 = 範囲(n+1, 2*n) + [2]
    # 交差結果を出力する
    print(交差(リスト1, リスト2))
実行( int (sys.argv[1]))

(これは Python を使用する最も慣用的な方法ではありませんが、Python を知らない人でも理解しやすいように、Python のアイデアをあまり使用せずにコードを書きたかったのです)

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

list1 を set1 という名前のセットに変換します。
2つのforループではなく1つのforループのみを使用する

linear.pyプログラムの速さを見てみましょう

このプログラムがなぜ高速なのかを説明する前に、実際に高速であることを示すために、いくつかの大きなリストでプログラムを実行してみましょう。ここでは、プログラムが 10 から 10,000,000 までのサイズのリストに対して順番に実行されている様子が示されています。 (前のプログラムは 100,000 要素で非常に遅くなり始めたことを思い出してください)

 $時間python3 linear.py 100
 [2]
実数0分0.056秒
$時間python3 linear.py 1000
 [2]
実数0分0.036秒
$時間python3 linear.py 10000 # 10,000
 [2]
実数0分0.028秒
$時間python3 linear.py 100000 # 100,000
 [2]
 real 0m0.048s < -- この場合、quadratic.py に 2 分かかりました。今では 0.04 秒で実行しています。とても速いです!  
 $時間python3 linear.py 1000000 # 1,000,000
 [2]
実数0分0.178秒
$時間python3 linear.py 10000000 # 10,000,000
 [2]
実数0分1.560秒

非常に大きなリストで linear.py を実行する

これを非常に大きなリスト (100 億 / 10,000,000,000 要素) で実行しようとすると、別の問題が発生します。十分に高速ですが (リストは 4.2 秒かかったリストの 100 倍しかないため、おそらく 420 秒以内に終了できるはずです)、コンピューターにはリストのすべての要素を格納するのに十分なメモリがないため、終了する前にプログラムがクラッシュします。

 $時間python3 linear.py 10000000000
トレースバック（最新の呼び出しが最後）：
  ファイル"/home/bork/work/homepage/linear.py" 、行 18 、 <module>
    実行( int (sys.argv[1]))
  ファイル「/home/bork/work/homepage/linear.py」、13行目、実行中
    リスト1 = [1] * n + [2]
メモリエラー
実数0分0.090秒
ユーザー0m0.034s
システム 0分0.018秒

ただし、この記事ではメモリ使用量については説明していないため、この問題は無視できます。

では、なぜ linear.py は高速なのでしょうか?

ここで、linear.py が高速である理由を説明します。

もう一度コードを見てみましょう:

交差を定義します(リスト1、リスト2):
    set1 = set (list1) # これはハッシュセットです 
    結果 = []
リスト2のyについて:
        yがset1にある場合:
            結果.append(y)
結果を返す

list1 と list2 はどちらも約 10,000,000 個の一意の要素を持つリストだとします。これは非常に多い数です。

では、なぜこんなに速く実行できるのでしょうか? それはハッシュマップのおかげです!!!

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

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

 yがset1にある場合:
    結果.append(y)

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

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

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

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

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