Python Language
プログラムのPython速度
サーチ…
記法
基本理念
Pythonプログラムの速度を記述するときに使用される表記法はBig-O表記と呼ばれます。関数があるとしましょう：
def list_check(to_check, the_list):
for item in the_list:
if to_check == item:
return True
return False
これは、アイテムがリストに含まれているかどうかをチェックする単純な関数です。この関数の複雑さを記述するために、あなたはO（n）と言うでしょう。これは、O関数としての "Order of n"がOrder関数として知られていることを意味します。
O（n） - 一般的にnはコンテナ内のアイテムの数です
O（k） - 一般的に、kはパラメータの値またはパラメータの要素の数です
リスト操作
操作：平均ケース（パラメータがランダムに生成されていると仮定）
追加：O（1）
コピー：O（n）
Delスライス：O（n）
アイテムを削除：O（n）
挿入：O（n）
アイテムを取得する：O（1）
設定項目：O（1）
反復：O（n）
スライスを取得する：O（k）
スライスを設定する：O（n + k）
拡張：O（k）
ソート：O（n log n）
乗算：O（nk）
x in s：O（n）
min（s）、max（s）：O（n）
長さを取得する：O（1）
デキ操作
両端キューは両端キューです。
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0,item)
def removeFront(self):
return self.items.pop()
def removeRear(self):
return self.items.pop(0)
def size(self):
return len(self.items)
操作：平均ケース（パラメータがランダムに生成されていると仮定）
追加：O（1）
Appendleft：O（1）
コピー：O（n）
拡張：O（k）
Extendleft：O（k）
ポップ：O（1）
Popleft：O（1）
削除：O（n）
回転：O（k）
操作を設定する
操作：平均ケース（ランダムに生成されたパラメータを仮定）：最悪の場合
x in s：O（1）
差s - t：O（len（s））
交差点s＆t：O（min（len（s）、len（t）））：O（len（s）* len（t）
ここで、lはmax（len（s1）、...、len（sn））であり、s1＆s2＆s3＆
s（t）：O（len（t））：O（len（t）* len（s））s.difference_update
s.symetric_difference_update（t）：O（len（t））
対称差s ^ t：O（len（s））：O（len（s）* len（t））
連合体| t：O（len（s）+ len（t））
アルゴリズム表記法...
任意のコンピュータ言語の最適化に適用されるいくつかの原則があり、Pythonも例外ではありません。 最適化を考慮せずにプログラムを作成し、コードがきれいで正確で理解できるものであることを確認することに集中してください。完了したときに大きすぎたり遅すぎたりする場合は、最適化を検討することができます。
80/20ルールを覚えておいてください 。多くのフィールドで、努力の20％で結果の80％を得ることができます（90/10ルールとも呼ばれます）。コードを最適化しようとするときはいつでも、プロファイリングを使用して実行時間の80％がどこにあるのかを知ることができます。
常に「前」と「後」のベンチマークを実行します。最適化が実際に効果を発揮したことを他にどのように知っていますか？最適化されたコードが元のバージョンよりわずかに速くなったり小さくなったりする場合は、変更を元に戻して元のクリアコードに戻ります。
適切なアルゴリズムとデータ構造を使用する：O（n log n）クイックソートが利用可能な場合に、千個の要素をソートするためにO（n 2）バブルソートアルゴリズムを使用しないでください。同様に、O（log n）バイナリツリー、またはO（1）Pythonハッシュテーブルを使用できる場合には、O（n）検索が必要な配列に1000個の項目を格納しないでください。
以下のリンクを参照してください... Python Speed Up
次の3つの漸近表記は、主にアルゴリズムの時間複雑さを表すために使用されます。
Θ表記法 ：シータ表記法は、上と下の関数に拘束されるため、正確な漸近挙動を定義します。式のTheta表記を取得する簡単な方法は、低次の項を削除し、先行する定数を無視することです。たとえば、次の式を考えてみましょう。 （Θ（n3）は常にΘn2よりも高い値を持ちます）、関係する定数に関係なく、常にn0が存在するため、低次項を削除することは常に有効です。3n3 + 6n2 + 6000 =Θ与えられた関数g（n）に対して、Θ（g（n））が関数の集合に従っていることを示す。すべてのn> nに対して0 <= c1 g（n）<= f（n）<= c2 g（n）となるような正の定数c1、c2およびn0が存在する。 = n0}上記定義は、f（n）がg（n）のシータである場合、n（n> 0）の大きな値に対して常にc1 g（n）とc2 g = n0）。シータの定義はまた、f（n）がn0より大きいnの値に対して非負でなければならないことも必要とする。
ビッグO表記法 ：ビッグO表記法は、アルゴリズムの上限を定義します。これは、上からのみ関数を限定します。たとえば、挿入ソートの場合を考えてみましょう。最良の場合は線形時間、最悪の場合は二次の時間がかかります。私たちは、挿入ソートの時間の複雑さはO（n ^ 2）であると言うことができます。 O（n ^ 2）も線形時間をカバーすることに注意してください。 Θ表記を使用して挿入のソートの時間の複雑さを表すと、最悪の場合と最悪の場合に2つのステートメントを使用する必要があります。
- 挿入のソートの最悪の時間複雑度はΘ（n ^ 2）です。
- 挿入ソートの最良のケース時間の複雑さはΘ（n）です。
Big O表記は、アルゴリズムの時間複雑度に上限がある場合に便利です。多くの場合、アルゴリズムを見るだけで簡単に上限を見つけることができます。すべてのn> = n0に対して0 <= f（n）<= cg（n）となるような正の定数cおよびn0が存在する。
- Ω表記法 ：Big O表記法が関数に漸近上限を与えるように、Ω表記法は漸近的な下限を提供する。 ΩNotation <は、アルゴリズムの時間複雑度の下限がある場合に便利です。前の記事で説明したように、アルゴリズムの最良の場合のパフォーマンスは一般的に有用ではありません。オメガ表記は、3つの中で最も使用頻度の低い表記法です。与えられた関数g（n）に対して、関数の集合をΩ（g（n））で表す。すべてのn> = n0に対して0 <= cg（n）<= f（n）となるような正の定数cおよびn0が存在する。ここでは、同じ挿入ソートの例を考えてみましょう。挿入ソートの時間の複雑さはΩ（n）と書くことができますが、一般的に最悪のケースや時には平均的なケースに興味があるので、挿入ソートについてはあまり有益な情報ではありません。