Pythonのデータ構造のトップ7アルゴリズム-AnalyticsVidhya

導入

効率的なソフトウェア開発は、アルゴリズムとデータ構造を強く理解しています。使いやすさで知られるPythonは、リスト、辞書、セットなどの組み込みデータ構造を提供します。ただし、これらの構造に適切なアルゴリズムを適用することにより、真の力は解き放たれます。アルゴリズムは、基本的に問題を解決するためのルールまたはプロセスのセットです。アルゴリズムとデータ構造を組み合わせた使用は、基本的なスクリプトを高度に最適化されたアプリケーションに変換します。

この記事では、Pythonデータ構造の7つの重要なアルゴリズムについて説明します。

目次

• 導入
• Pythonデータ構造におけるアルゴリズムの重要性
• Pythonデータ構造の7つの重要なアルゴリズム
  • 1. バイナリ検索
  • 2. ソートをマージします
  • 3. クイックソート
  • 4. Dijkstraのアルゴリズム
  • 5. 幅広い検索（BFS）
  • 6. 深さfirst検索（DFS）
  • 7. ハッシュ
• 結論

Pythonデータ構造におけるアルゴリズムの重要性

効果的なアルゴリズムは、いくつかの理由で重要です。

• パフォーマンスの強化：適切なデータ構造と組み合わせた適切に設計されたアルゴリズムは、時間と空間の複雑さを最小限に抑え、より速く効率的なプログラムをもたらします。たとえば、バイナリ検索ツリーのバイナリ検索により、検索時間が劇的に短縮されます。
• 大規模なデータセットのスケーラビリティ：効率的なアルゴリズムは、大規模なデータセットを処理するために不可欠であり、処理が迅速かつリソース効率の良いままであることを保証します。最適化されたアルゴリズムがなければ、大規模なデータ構造の操作は計算高価になります。
• 改善されたデータ組織：アルゴリズムは、構造内でデータを整理し、検索と操作を簡素化するのに役立ちます。 QuickSortやMergESORTなどのソートアルゴリズムは、アクセスを容易にするために、配列またはリンクリストに要素をアレンジします。
• 最適化されたメモリ使用量：アルゴリズムは、メモリ消費を最小限に抑えることで効率的なストレージに貢献します。たとえば、ハッシュ関数は、ハッシュテーブル全体にデータを配布し、検索時間を短縮します。
• ライブラリ機能の活用：多くのPythonライブラリ（Numpy、Pandas、Tensorflow）は、データ操作のために洗練されたアルゴリズムに依存しています。これらのアルゴリズムを理解することで、開発者はこれらのライブラリを効果的に使用できます。

Pythonデータ構造の7つの重要なアルゴリズム

7つの重要なアルゴリズムを調べましょう。

1。バイナリ検索

バイナリ検索は、ソートされたリスト内で特定のアイテムを見つけるための非常に効率的なアルゴリズムです。検索間隔を半分に繰り返し分割することで機能します。ターゲット値が中間要素よりも小さい場合、検索は下半分で続きます。それ以外の場合は、上半分で続きます。この対数時間の複雑さ（o（log n））により、大きなデータセットの線形検索よりも大幅に高速になります。

アルゴリズムの手順

1. 初期化： leftに0に設定し、アレイの長さをマイナス1にrightに設定します。
2. イテレーション： left right以下ですが、
   • 中間指数（ mid ）を計算します。
   • 中間要素をターゲット値と比較します。等しい場合は、 mid戻ります。
   • ターゲットが中間要素よりも少ない場合は、 right mid - 1 。
   • それ以外の場合は、 left mid 1まで更新します。
3. ターゲットが見つかりません：ターゲットを見つけることなくループが完了した場合、-1を返します。

コード実装（例示）

 def binary_search（arr、ターゲット）：
    ＃...（元のテキストのような実装）

バイナリ検索は、データベースインデックスなどの迅速な検索が必要な状況で非常に貴重です。

2。ソートをマージします

Merge Sortは、各サブリストに1つの要素のみが含まれるまで、非セラストリストをより小さなサブリストに再帰的に分割する分割統合アルゴリズムです。これらのサブリストは、単一のソートされたリストが取得されるまで、繰り返し合併して新しいソートされたサブリストを生成します。その時間の複雑さはO（n log n）であり、大規模なデータセットで効率的です。

アルゴリズムの手順

1. 分割：各半分に1つの要素のみが含まれるまで、アレイを2つの半分に再帰的に分割します。
2. 征服：各サブリストを再帰的にソートします（ベースケース：シングルエレメントリストはすでにソートされています）。
3. マージ：各サブリストの要素を比較して、より小さな要素を結果のリストに配置することにより、ソートされたサブリストを単一のソートリストにマージします。

コード実装（例示）

 def merge_sort（arr）：
    ＃...（元のテキストのような実装）

マージソートは、リンクリストの並べ替えやメモリに完全に収まらない可能性のある大きなデータセットの処理に特に適しています。

3。クイックソート

別の分割整理アルゴリズムであるクイックソートは、「ピボット」要素を選択し、ピボットよりも小さいか大きいかに応じて、他の要素を2つのサブアレイに分割します。このプロセスは、配列全体がソートされるまで、サブアレイに再帰的に適用されます。最悪の時間の複雑さはO（n²）ですが、平均ケースのパフォーマンスはO（n log n）であり、非常に実用的なソートアルゴリズムになっています。

アルゴリズムの手順

1. ピボット選択：ピボット要素を選択します（さまざまな戦略が存在します）。
2. パーティション化：ピボットよりも小さい要素がそれよりも前に、要素が大きくなるように配列を再配置します。
3. 再帰：ピボットの前後にサブアレイにクイックソートを再帰的に適用します。

コード実装（例示）

 def Quick_Sort（arr）：
    ＃...（元のテキストのような実装）

Quick Sortの効率により、多くのライブラリやフレームワークで人気のある選択肢になります。

4。Dijkstraのアルゴリズム

Dijkstraのアルゴリズムは、単一のソースノードから非陰性エッジウェイトのグラフ内の他のすべてのノードまでの最短パスを見つけます。ソースから最小の暫定的な距離でノードを選択し、近隣の距離を更新します。

アルゴリズムの手順

1. 初期化：すべてのノードに暫定距離を割り当てます：ソースノードのゼロ、他のすべてのノードの無限。
2. イテレーション：訪問されていないノードがありますが：
   • 最小の暫定距離で未訪問ノードを選択します。
   • それぞれの隣人について、選択したノードを通る距離を計算します。この距離が現在の暫定距離よりも短い場合は、隣人の暫定的な距離を更新します。
3. 終了：アルゴリズムは、すべてのノードが訪問された場合、または優先順位キューが空になったときに終了します。

コード実装（例示）

 heapqをインポートします

def dijkstra（グラフ、開始）：
    ＃...（元のテキストのような実装）

Dijkstraのアルゴリズムには、GPSシステム、ネットワークルーティング、およびさまざまなパスファインディングの問題にアプリケーションがあります。

5。幅広い検索（BFS）

BFSは、レベルごとのグラフレベルを調査するグラフトラバーサルアルゴリズムです。ルートノードから始まり、次のレベルの隣人に移動する前に、すべての隣人を訪問します。非加重グラフで最も短いパスを見つけるのに役立ちます。

アルゴリズムの手順

1. 初期化：ルートノードを含むキューと、訪問したノードを追跡するセットから始めます。
2. イテレーション：キューが空ではありませんが：
   • ノードのdequeue。
   • 訪問していない場合は、訪問したようにマークし、その訪問されていない隣人をenqueしてください。

コード実装（例示）

コレクションからインポートDequeから

def bfs（graph、start）：
    ＃...（元のテキストのような実装）

BFSは、ソーシャルネットワーク、ピアツーピアネットワーク、および検索エンジンでアプリケーションを見つけます。

6。深さ最初の検索（DFS）

DFSは、バックトラッキングの前に各ブランチに沿って可能な限り深く進むことでグラフを探索する別のグラフトラバーサルアルゴリズムです。スタック（または再帰）を使用して、訪問するノードを追跡します。

アルゴリズムの手順

1. 初期化：ルートノードを含むスタックと、訪問したノードを追跡するセットから始めます。
2. イテレーション：スタックが空ではありませんが：
   • ノードをポップします。
   • 訪問していない場合は、訪問したようにマークを付け、訪問されていない隣人をスタックに押し込みます。

コード実装（例示）

 def dfs_iterative（graph、start）：
    ＃...（元のテキストのような実装）

DFSは、トポロジーソート、サイクル検出、およびパズルの解決に使用されます。

7。ハッシュ

Hashingは、効率的なデータ検索のためにハッシュテーブルのインデックスにキーをマッピングするための手法です。ハッシュ関数はキーをインデックスに変換し、高速ルックアップ、挿入、および削除を可能にします。異なるキーが同じインデックスにマッピングされる状況に対処するには、衝突処理メカニズムが必要です。

アルゴリズムの手順

1. ハッシュ関数：キーをインデックスにマッピングするハッシュ関数を選択します。
2. 挿入：ハッシュ関数を使用してインデックスを計算し、キー値ペアを対応するバケット（処理衝突）に挿入します。
3. ルックアップ/削除：ハッシュ関数を使用してインデックスを見つけ、キー値ペアを取得/削除します。

コード実装（例示）

クラスハッシュテーブル：
    ＃...（元のテキストのような実装）

ハッシュテーブルは、データベース、キャッシュ、および高速データアクセスを必要とするその他のアプリケーションの基本です。

結論

アルゴリズムのしっかりとした把握とデー​​タ構造との相互作用は、効率的なPythonプログラミングのために最も重要です。これらのアルゴリズムは、パフォーマンスを最適化し、スケーラビリティを改善し、複雑な問題を解決するための不可欠なツールです。これらのテクニックを習得することにより、開発者は堅牢で高性能のアプリケーションを構築できます。

以上がPythonのデータ構造のトップ7アルゴリズム-AnalyticsVidhyaの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。