Python プログラミングにおける 3 つの一般的なデータ構造とアルゴリズム

Python には、リスト、セット、辞書など、非常に便利な組み込みデータ構造が多数あります。ほとんどの場合、これらのデータ構造を直接使用できます。ただし、通常は、検索、並べ替え、配置、フィルタリングなどの一般的な問題も考慮する必要があります。

この記事では、3 つの一般的なデータ構造とデータ関連のアルゴリズムを紹介します。さらに、コレクションモジュールには、さまざまなデータ構造のソリューションも含まれています。

[[262323]]

1. 系列を個別の変数に分解する

（１）問題点

N 個の要素を含むタプルまたはシーケンスがあり、それを N 個の個別の変数に分解したいと考えています。

（２）解決策

任意のシーケンス (または反復可能なオブジェクト) は、単純な代入操作で個別の変数に分割できます。 1 つの要件は、変数の合計数と構造がシーケンスのものと一致することです。例えば：

 > > >   p = (4, 5)
 >>> x , y = p  
 > > > ×
 4
 > > >はい
5
 > > >  
 > > >  データ= [ 'ACME', 50, 91.1, (2012, 12, 21) ]
 > > >名前、株数、価格、日付=データ 
 > > >名前
「アクメ」
 > > >日付
(2012年12月21日)
 > > >名前、株数、価格、（年、月、日）=データ
> > >名前
「アクメ」
 > > >年
2012
 > > >月曜日
12
 > > >日
21
 > > >

要素数が一致しない場合はエラーが発生します。例えば：

 > > >   p = (4, 5)
 >>> x , y, z = p  
トレースバック（最新の呼び出しが最後）:
 ファイル " < stdin > "、行 1、 < module >  
 ValueError: 解凍するには 2 つ以上の値が必要です
> > >

（３）議論

実際、タプルやリストだけでなく、オブジェクトが反復可能である限り、分解操作を実行できます。これには、文字列、ファイル、反復子、ジェネレーターが含まれます。例えば：

 > > >   s = 'こんにちは'  
 > > > a、b、c、d、 e = s  
 > > >は
「は」
 > > >バ
'え'
 > > > e
 「お」
 > > >

分解操作を行うときに、特定の値を破棄したい場合があります。 Python ではこれを行うための特別な構文は提供されていませんが、通常は、破棄する値の名前として未使用の変数名を選択できます。例えば：

 > > >  データ= [ 'ACME', 50, 91.1, (2012, 12, 21) ]
 > > > _、株、価格、 _ =データ 
 > > >シェア
50
 > > >価格
91.1
 > > >

ただし、他の場所で使用されていない変数名を選択するようにしてください。

2. 任意の長さの反復可能オブジェクトの要素を分解する

（１）問題点

反復可能オブジェクトから N 個の要素をアンパックする必要がありますが、反復可能オブジェクトの長さが N を超える場合があり、「アンパックする値が多すぎます」という例外が発生します。

（２）解決策

この問題を解決するには、Python の「* 式」を使用できます。たとえば、あるコースが提供され、最終成績から最初と最後の課題を削除し、残りの中間の成績のみを平均することにしたとします。グレードが 4 つしかない場合は、単純に 4 つすべてを因数分解できるかもしれませんが、24 あった場合はどうなるでしょうか。 * 式を使用すると、すべてが簡単になります。

 def drop_first_last(成績):
 1、*中間、最終=成績 
 平均(中央)を返す

もう 1 つの使用例としては、名前と電子メールアドレス、それに続く任意の数の電話番号で構成されるユーザーレコードがいくつかあると想定します。次に、レコードを次のように分解します。

 > > >  レコード= ('Dave', '[email protected]', '773-555-1212', '847-555-1212')
 > > >名前、メールアドレス、*電話番号=ユーザーレコード 
 > > >名前
「デイブ」
 > > >メール
'[email protected]'
 > > >電話番号
['773-555-1212', '847-555-1212']
 > > >

いくつの電話番号を因数分解する必要があるかに関係なく (または電話番号がない場合でも)、変数 phone_numbers は常にリストになり、意味がありません。そうすれば、変数 phone_numbers を使用するコードは、それがリストではないかもしれないという事実を心配する必要がなくなり、追加の型チェックを行う必要もなくなります。

* で変更された変数は、リストの最初の位置に置くこともできます。たとえば、過去 8 四半期の会社の売上を表す一連の値があるとします。直近の四半期の売上を過去 7 四半期の平均と比較する場合は、次のようにします。

 *trailing_qtrs、 current_qtr =売上記録 
後続平均=合計(後続四半期) / 長さ (後続四半期)
 avg_comparison(trailing_avg, current_qtr) を返します。

Python インタープリターの観点から見ると、この操作は次のようになります。

 > > > *末尾、現在= [10, 8, 7, 1, 9, 5, 10, 3]
 > > >末尾
[10、8、7、1、9、5、10]
 > > >現在
3

（３）議論

この拡張分解操作は、長さが不明または任意の反復可能なオブジェクトを分解するためのカスタムツールです。多くの場合、このような反復可能オブジェクトには既知のコンポーネントまたはパターンがあり (たとえば、要素 1 の後はすべて電話番号です)、* 式を使用して反復可能オブジェクトを分解すると、開発者は関連する要素を取得するために反復可能オブジェクト内で複雑な操作を実行する必要なく、これらのパターンを簡単に利用できます。

* スタイルの構文は、可変長のタプルのシーケンスを反復処理する場合に特に便利です。たとえば、ラベル付きタプルのシーケンスがあるとします。

レコード= [
 ('foo', 1, 2),
 (「バー」、「こんにちは」)、
 ('foo', 3, 4),
 ]
 do_foo(x, y)を定義します。
 print('foo', x, y)
 def do_bar(s):
 印刷('bar', s)
タグの場合、レコード内の*引数:
 タグ== 'foo' の場合:
 do_foo(*引数)
 elifタグ== 'bar':
 do_bar(*引数)

この * スタイルの構文でサポートされている分解操作は、分割などの特定の文字列処理操作と組み合わせた場合にも非常に便利です。例えば：

 > > >  行= 'nobody:*:-2:-2:権限のないユーザー:/var/empty:/usr/bin/false'  
 > > > uname、*fields、homedir、 sh =行.split(':')
 > > >名前なし
'誰でもない'
 > > >ホームディレクトリ
'/var/空'
 > > >シュ
'/usr/bin/偽'
 > > >

場合によっては、特定の値を除外して破棄したい場合があります。分解する際には、* を一つだけ指定するのではなく、_ や ign (無視) など、破棄する値を表すためによく使われる変数名を複数使用することができます。例えば：

 > > >  レコード= ('ACME', 50, 123.45, (12, 18, 2012))
 > > >名前、*_、(*_、年) = レコード
> > >名前
「アクメ」
 > > >年
2012
 > > >

*分解操作は、さまざまな関数型言語のリスト処理関数とある程度類似しています。たとえば、リストがある場合、次のように簡単に先頭と末尾に分解できます。

 > > >  アイテム= [1, 10, 7, 4, 5, 9]
 > > >ヘッド、*テール=アイテム 
 > > >頭
1
 > > >しっぽ
[10、7、4、5、9]
 > > >

この種の分割機能を実行する関数を作成する場合、何らかの高度な再帰アルゴリズムを実装することを意図していると思われるかもしれません。例えば：

 >>> def sum (items) :
 ... ヘッド、*テール=アイテム 
 ... 末尾の場合は head + sum(tail) を返し、それ以外の場合は head を返します
...
 > > >合計(アイテム)
 36
 > > >

ただし、再帰は固有の制限があるため、Python の強みではないことに注意してください。したがって、この最後の例には実用的な意味はあまりなく、単なる学術的な好奇心によるものです。

3. 最後のN要素を保存する

（１）問題点

反復処理やその他の形式の処理中に、最後のいくつかのレコードの限定的な履歴記録を作成したいと考えています。

（２）解決策

限定された履歴レコードを保存することは、collections.deque のアプリケーションシナリオと見なすことができます。たとえば、次のコードは、一連のテキスト行に対して単純なテキストマッチング操作を実行します。一致が見つかると、現在の一致行とチェックされたテキストの最後の N 行を出力します。

コレクションから deque をインポート
def search(行、パターン、履歴= 5 ):
 previous_lines = deque ( maxlen = history )
 行内の行の場合:
 パターンが行内にある場合:
 譲歩ライン、前の行
 previous_lines.append(行)
 # ファイルでの使用例
__name__ == '__main__' の場合:
 open('somefile.txt') を f として実行します:
 行に対して、prevlines in search(f, 'python', 5):
 prevlines の pline の場合:
 print(ポリライン、終了= '' )
 print(行,終了= '' )
 印刷('-'*20)

（３）議論

上記のコードスニペットのように、レコードを検索するコードを記述する場合、通常は yield キーワードを含むジェネレーター関数を使用します。これにより、検索を処理するコードと検索結果を使用するコードが適切に分離されます。ジェネレーターに慣れていない場合は、セクション 4.3 を参照してください。

deque(maxlen=N) は固定長のキューを作成します。新しいレコードが追加され、キューがいっぱいになると、最も古いレコードが自動的に削除されます。例えば：

 > > >   q =デキュー(最大長= 3 )
 > > > q.append(1)
 > > > q.append(2)
 > > > q.append(3)
 > > >質問
デキュー([1, 2, 3],最大長= 3 )
 > > > q.append(4)
 > > >質問
デキュー([2, 3, 4],最大長= 3 )
 > > > q.append(5)
 > > >質問
deque([3, 4, 5],最大長= 3 )

このような操作 (追加、削除) はリストに対して手動で実行できますが、キューソリューションの方がはるかに洗練されており、実行速度もはるかに速くなります。

より一般的には、単純なキュー構造が必要な場合、 deque が役立ちます。キューのサイズを指定しない場合は、無制限のキューが取得され、両端で操作の追加とポップを実行できます。次に例を示します。

 > > >   q =デキュー()
 > > > q.append(1)
 > > > q.append(2)
 > > > q.append(3)
 > > >質問
デキュー([1, 2, 3])
 > > > q.appendleft(4)
 > > >質問
デキュー([4, 1, 2, 3])
 > > > q.pop()
 3
 > > >質問
デキュー([4, 1, 2])
 > > > q.popleft()
 4