Big-O表記法のRubyistsガイド

表記がどのように機能するかを理解している限り、さまざまなBig-O値をすべて覚える必要はありません。

たとえば、恐ろしい恐ろしいO(2^n) 。それをRubyで表現すると、次のようになります。

# O(2^n) translated to Ruby
def o(n)
  2 ** n  # This is ruby for 2^n
end

まだ明らかではありませんか？メソッドと引数の名前をよりユーザーフレンドリーなものに変更した場合はどうでしょうか？

# O(2^n) translated to prettier Ruby
def execution_time(size_of_dataset)
  2 ** size_of_dataset
end

あなたはそれらすべてのためにこれを行うことができます：

# O(1)
def o1_execution_time(size_of_dataset)
  1
end

# O(n)
def on_execution_time(size_of_dataset)
  size_of_dataset
end

# O(n^2)
def on2_execution_time(size_of_dataset)
  size_of_dataset * size_of_dataset
end

...etc

表記法がどのように機能するかがわかったので、いくつかの典型的なルビーコードを見て、それがどのように関連するかを見てみましょう。

O（1）

何かがO(1)であると言うとき これは、その速度がデータセットのサイズに依存しないことを意味します。

たとえば、ハッシュルックアップ時間はハッシュサイズに依存しません：

# These should all take the same amount of time
hash_with_100_items[:a]
hash_with_1000_items[:a]
hash_with_10000_items[:a]

これが、大きなデータセットの場合、ハッシュは配列よりも高速であると言う傾向がある理由です。

O（n）

対照的に、Array#find O(n)です 。つまり、Array#find 配列内のアイテムの数に直線的に依存します。 100個のアイテムを含む配列は、1個のアイテムを含む配列よりも検索に100倍の時間がかかります

配列を反復処理する多くのコードは、O(n)に従います。 パターン。

(0..9).each do |i|
  puts i
end

# This example is 1/2 the speed of the previous because it contains 2x the items. 
(0..19).each do |i|
  puts i
end

O（n ^ 2）

O(n^2)に適合するコード プロファイルにはネストされたループが含まれる傾向があります。あなたがそれについて考えるならば、それは理にかなっています。 1つのループでO(n)が得られます 、2番目のネストされたループはO(n^2)を提供します 。なんらかの理由で、5レベルのネストされたループがあった場合、それはO(n^5)になります。 。

data = (0..100)
data.each do |d1|
  data.each do |d2|
    puts "#{ d1 }, #{ d2 }"
  end
end

O（n log n）

O(n log n) コードは、多くの場合、誰かが他の方法でO(n^2)する作業量を減らすための賢い方法を見つけた結果です。 アルゴリズムで十分です。

コードの一部を見て、それがO(n log n)であると言うことはできません。 。これは、より高度な数学が登場する場所であり、私がお辞儀をする場所でもあります。

ただし、O(n log n)について知っておくことが重要です。 多くの一般的な検索アルゴリズムについて説明しているためです。 RubyのArray#sort 由緒あるクイックソートアルゴリズムを使用します。これは平均してO(n log n)です。 最悪の場合はO(n^2)

クイックソートに慣れていない場合は、この優れたデモを確認してください。

すべてをまとめる：データベース

新しいWebアプリケーションで最も一般的な問題の1つは、開発者のコ​​ンピューターでは高速ですが、本番環境ではますます遅くなることです。

これは、データベース内のレコードの量が時間の経過とともに増加するために発生しますが、コードはDBに適切にスケーリングされない操作を実行するように要求しています。すなわち。 O(n) またはさらに悪い。

たとえば、postgresでは、カウントクエリは常にO(n)であることをご存知ですか。 ？

# This makes the DB iterate over every row of Users
# ...unless you're using a Rails counter cache. 
Users.count

これは、postgresのexplainを使用して確認できます。 指図。以下では、これを使用して、カウントクエリのクエリプランを取得します。ご覧のとおり、テーブル内の104,791行すべてに対してシーケンシャルスキャン（ループを意味する）を実行することを計画しています。

# explain select count(*) from users;
                           QUERY PLAN
-----------------------------------------------------------------
 Aggregate  (cost=6920.89..6920.90 rows=1 width=0)
   ->  Seq Scan on users  (cost=0.00..6660.71 rows=104701 width=0)
(2 rows)

多くの一般的なレールイディオムは、データベースを特に最適化してそれらを防止しない限り、意図しないシーケンシャルスキャンをトリガーする可能性があります。

# This asks the DB to sort the entire `products` table
Products.order("price desc").limit(1)

# If `hobby` isn't indexed, the DB loops through each row of Users to find it. 
User.where(hobby: "fishing")

explainを使用できます それも確認するコマンド。ここでは、テーブル全体でソート（おそらくクイックソート）を実行していることがわかります。メモリの制約がある場合は、パフォーマンス特性が異なる別の並べ替えアルゴリズムを選択した可能性があります。

# explain select * from users order by nickname desc limit 1;
                               QUERY PLAN
-------------------------------------------------------------------------
 Limit  (cost=7190.07..7190.07 rows=1 width=812)
   ->  Sort  (cost=7190.07..7405.24 rows=104701 width=812)
         Sort Key: nickname
         ->  Seq Scan on users  (cost=0.00..6606.71 rows=104701 width=812)

もちろん、これらすべての問題に対する答えは索引付けです。ハッシュルックアップを使用する場合、データベースにインデックスを使用するように指示するのは、Rubyの場合と少し似ていますO(1) 配列の代わりにO(n)を見つけます 。

それだけです、皆さん

これがBig-O表記法の有用な紹介であり、ルビー開発者としてのあなたにどのような影響を与えるかを願っています。ご不明な点がございましたら、@StarrHorneまでpingしてください。