Ruby開発者のための時間計算量への決定的なガイド

時間計算量は、コンピュータサイエンスから学ぶことができる最も興味深い概念のひとつであり、それを理解するのに学位は必要ありません！

特定のアルゴリズムやプログラムが遅い理由を確認するのに役立つので興味深いです ＆それをより速くするためにあなたは何ができますか。

これを独自のコードに適用できます。

これはすべての派手なアルゴリズムを超えて これは、この記事の後半で説明するように、コンピュータサイエンスの本にあります。

しかし、最初に、何が遅いのか、何が速いのかについて話す必要があります。

遅いvs速い

150ミリ秒（ミリ秒）で100万個の数値を並べ替えるのは遅いですか、それとも速いですか？

それはかなり速いと思いますが、これは時間計算量が答えようとしている問題ではありません。

「入力サイズ」が大きくなるにつれて、アルゴリズムがどのように実行されるかを知りたいのです。

「入力サイズ」について話すときは、関数またはメソッドの引数について話します。メソッドが引数として1つの文字列を受け取る場合、それが入力であり、文字列の長さが入力サイズです。

ビッグO表記

Big O表記を使用すると、パフォーマンスに応じてアルゴリズムを分類できます。

次のようになります：

O(1)

この場合、O(1) 「定数時間」アルゴリズムを表します。

つまり、アルゴリズムは、実行する必要のある作業量に関係なく、作業を完了するのに常に同じ時間がかかります。

もう1つは「線形時間」です：

O(n)

ここで、「n」は入力のサイズ（文字列サイズ、配列サイズなど）を表します。これは、アルゴリズムが入力サイズに対して1：1の関係で作業を終了することを意味します。したがって、入力サイズを2倍にすると、作業の完了にかかる時間も2倍になります。

ここに表があります ：

表記 名前 説明 一定 常に同じ時間がかかります。 対数 線形 線形 二次方程式 キュービック 指数関数

O（1）
O（log n）	ループを繰り返すたびに、作業量が2で除算されます（二分探索）。
O（n）	作業を完了する時間は、入力サイズと1対1の関係で増加します。
O（n log n）	これはネストされたループであり、内側のループはlog nで実行されます。 時間。例としては、クイックソート、マージソート、ヒープソートなどがあります。
O（n ^ 2）	作業を完了する時間はinput size ^ 2で長くなります 関係。これは、すべての要素を通過するループがあり、ループのすべての反復がすべての要素を通過する場合はいつでも認識できます。ネストされたループがあります。
O（n ^ 3）	n^2と同じ 、ただし、n^3では時間が長くなります 入力サイズとの関係。これを認識するために、トリプルネストループを探してください。
O（2 ^ n）	作業を完了する時間は2 ^ input sizeで長くなります 関係。これはn^2よりもはるかに遅いです 、混同しないでください。 1つの例は、再帰的なフィボナッチアルゴリズムです。

アルゴリズム分析

入力を「n」個の要素の配列として考えると、このための直感を開発し始めることができます。

偶数であるすべての要素を検索したいとします。これを行う唯一の方法は、すべての要素を1回読み取って、条件に一致するかどうかを確認することです。

[1,2,3,4,5,6,7,8,9,10].select(&:even?)

探している数字の一部を見逃す可能性があるため、数字をスキップすることはできません。そのため、これは線形時間アルゴリズムO(n)になります。 。

同じ問題に対する3つの異なる解決策

個々の例を分析することは興味深いですが、このアイデアを理解するのに本当に役立つのは、異なるソリューションを使用して同じ問題をどのように解決できるかを確認することです。

Scrabbleソリューションチェッカーの3つのコード例を調べます。

スクラブルは、キャラクターのリスト（ollheなど）を提供するゲームです。 ）単語を作成するように求められます（helloなど） ）これらの文字を使用します。

これが最初の解決策です ：

def scramble(characters, word)
  word.each_char.all? { |c| characters.count(c) >= word.count(c) }
end

このコードの時間計算量を知っていますか？キーはcountにあります メソッドなので、そのメソッドが何をするのかを理解してください。

答えは次のとおりです。O(n^2) 。

その理由は、each_charを使用するためです。 文字列wordのすべての文字を調べます 。それだけで線形時間アルゴリズムO(n) 、ただし、ブロック内にはcountがあります メソッド。

このメソッドは、事実上、文字列内のすべての文字を再度調べてそれらをカウントする別のループです。

2番目の解決策

わかりました。

どうすればもっとうまくできるでしょうか？ループを回避する方法はありますか？

文字を数える代わりに、それらを削除することができます。そうすれば、通過する文字が少なくなります。

これが2番目の解決策です ：

def scramble(characters, word)
  characters = characters.dup
  word.each_char.all? { |c| characters.sub!(c, "") }
end

これはもう少し面白いです。これは、countよりもはるかに高速になります 最良の場合のバージョンで、探している文字が文字列の先頭近くにあります。

ただし、文字がすべて最後にある場合は、wordでの検索とは逆の順序になります。 、パフォーマンスはcountのパフォーマンスと同様になります バージョンなので、これはまだO(n^2)であると言えます。 アルゴリズム。

wordの文字がない場合は心配する必要はありません。 all?なので、利用可能です sub!が実行されるとすぐにメソッドが停止します falseを返します 。しかし、これを知っているのは、通常のRubyコースが提供するものをはるかに超えてRubyを広範囲に研究した場合のみです。

別のアプローチで試してみましょう

ブロック内のループを削除するとどうなりますか？ハッシュでそれを行うことができます。

def scramble(characters, word)
  available = Hash.new(1)

  characters.each_char { |c| available[c] += 1 }
  word.each_char.all? { |c| available[c] -= 1; available[c] > 0 }
end

ハッシュ値の読み取りと書き込みはO(1)です 操作。これは、特にループと比較して、かなり高速であることを意味します。

まだ2つのループがあります ：

1つはハッシュテーブルを作成し、もう1つはそれをチェックします。これらのループはネストされていないため、これはO(n)です。 アルゴリズム。

これらの3つのソリューションをベンチマークすると、分析が結果と一致することがわかります。

hash    1.216667   0.000000   1.216667 (  1.216007)
sub     6.240000   1.023333   7.263333 (  7.268173)
count 222.866644   0.073333 222.939977 (223.440862)

折れ線グラフは次のとおりです。

いくつかの点に注意してください ：

1. Y軸（垂直）は作業を完了するのにかかった秒数を表し、X軸（水平）は入力サイズを表します。
2. これは対数グラフであり、特定の範囲の値を圧縮しますが、実際にはcount 線はかなり急です。
3. これを対数グラフにした理由は、入力サイズが非常に小さいcountで、興味深い効果を評価できるようにするためです。 実際には高速です！

概要

アルゴリズムの時間計算量、大きなO表記、時間計算量の分析について学びました。また、同じ問題に対するさまざまなソリューションを比較し、それらのパフォーマンスを分析した例もいくつか見ました。

新しくて面白いことを学んだことを願っています！

ソーシャルメディアでこの投稿を共有し、まだニュースレターを購読していない場合は、このようなコンテンツをさらに送信できるようにしてください。

読んでくれてありがとう。