Pythonアルゴリズムの一般的なテクニックと組み込みライブラリ

[[347377]]

Pythonアルゴリズムの一般的なテクニックと組み込みライブラリ

近年、Python の人気が高まるにつれ、徐々に多くのプログラマーに好まれるようになりました。多くのプログラマーは、問題を練習するための最初の言語として Python を使い始めています。

最近、Python を使用して問題を解決していたときに、Python でよく使用されるライブラリ API と問題解決手法を見つけたいと思いました。これは C++ の STL ライブラリのドキュメントに似ていますが、残念ながら見つけられなかったので、質問に答えたりインターネットを検索したりした自分の経験を組み合わせて、自分とみんなが読めるドキュメントを作成することにしました。

1. 入力と出力:

1.1 最初の行には、スペースで区切られた 2 つの値 n と m が与えられます。最初の n は、次に n 行の入力があることを決定し、m は各行にいくつの数字があるかを決定します。m 個の数字はスペースで区切られます。

解決策: Python の入力関数が受け取る入力はデフォルトで文字列なので、文字列のカット、強制型変換、リスト ジェネレーターを使用することで入力の問題を完全に解決できます。コードは次のとおりです。

 # 2つの値を受け取り、nとmを使用してそれぞれリスト内の2つの値を受け取ります 
 n, m = [int(x) の場合、input().split() 内の x]  
 # 入力リストのリストを構築する 
 num_list = []  
 iが範囲(n)内にある場合:  
    # Pythonはmの値を気にする必要はなく、すべての値を受け取り、lenを使用して長さを決定します。  
 tmp_list = [int(x) は input().split() 内の x を表します]  
    num_list.append(tmp_list)

同様に、カンマ (,) を使用して区切る場合は、同じ値を split 関数に渡すだけです。

1.2 数字の行を出力する

Python の print 関数はデフォルトで改行を終端文字として使用するため、必要な間隔に変更する必要があります。コードは次のとおりです。

 iが範囲(10)内にある場合:  
    print(i,終了= ' ' )

end は print 関数のパラメータで、出力の終了文字を決定します。ここで、これをスペースに変更すると、スペースで区切られた数字の行が出力されることになります。他の文字は自由に変更できます。

2. 空リストの生成、文字列の変更、リストの走査

2.1コードを書くときに、長さと初期値を持つ空のリストが必要になることがあります。生成方法は次のとおりです。

 # 1. 乗算を使用して、初期値がFalseの長さ100の1次元リストを生成します。  
訪問= [False] * 100  
 # 2. リストジェネレータを使用して、初期値が0のn*mの2次元リストを生成します。  
訪問= [[i が範囲(m)内、j が範囲(n)] 内の 0]

2.2 Python では、文字列をその場で変更することはできません。変更ごとに新しい文字列を生成すると、変更の数が多く、文字列が非常に大きい場合にオーバーヘッドが非常に高くなります。したがって、一般的には文字列はリストに変換され、変更されてから元に戻されます。

文字列= '私は鶏肉を食べるのが大好きです'    
 # 文字列をリストに変換する 
 string_list = リスト(文字列)  
 # .......文字列リストを変更する 
 # コード 
 # 文字列のリストを文字列に再構築する 
 #文字列= '' .join(string_list)

2.3 Python でリストをトラバースする方法は数多くあります。最も直接的な方法は、リストを直接反復することです。ただし、インデックスに基づいて配列を操作し、配列の値を変更する必要があることが多いため、次のコードの 2 番目と 3 番目の方法をお勧めします。

 num_list = [i が範囲内(10)]  
 # 1. リストを直接反復する 
 num_list内の項目の場合:  
    # コード 
    合格 
 # 2. インデックスによる反復 
 i が範囲(len(num_list))内にある場合:  
    print(num_list[i])  
 # 3. enumerate関数を反復処理する 
インデックス、enumerate(num_list) の値:  
    # インデックスは現在の要素のインデックス、値は現在の要素の値です 
    print(インデックス, 値)

3. コレクションライブラリの利用

3.1 デキュー

deque は Python のキューです (FIFO、先入れ先出し)。キューの先頭をポップする場合、キューの方がリストよりも高速です。

特に BFS (深さ優先探索) を使用する場合は、キューを使用する必要があります。いくつかの deque 使用コードは次のとおりです。

コレクションから deque をインポート 
 # 最大長3のキューを初期化する 
 d =両端キュー([1,2,3],最大長= 3 )  
 # 初期化されたキューの最大長は3なので、要素を追加すると先頭の要素が押し出されます。  
 d.append(4)  
 # 長さ無制限のキューを初期化する 
 d =デキュー()  
 # キューの最後に要素を追加する 
 d.append(1)  
 d.append(2)  
 d.append(3)  
 # キューの先頭の要素をポップして返します 
 print(d.popleft())  
 # 末尾の要素をポップして値を返す 
印刷(d.pop())  
 # キューの先頭に要素を挿入する 
 d.appendleft(0)

3.2 カウンター

カウンターは、シーケンスをカウントし、シーケンス内の要素の出現回数を計算できるカウンターです。

サンプルコードは次のとおりです。

コレクションをインポートする 
 # 初期化方法は3つあります 
 # 1. シーケンスを渡す 
 print(collections.Counter(['a', 'b', 'c', 'a', 'b', 'b']))  
 # 2. 辞書を渡す
print(コレクション.Counter({'a':2, 'b':3, 'c':1}))  
 # 3. 直接使用 = パラメータ渡し 
 print(コレクション.Counter( a = 2 , b = 3 , c = 1 ))  
 # パラメータなしで構築し、更新関数を使用して更新することもできます 
 c =コレクション.Counter ()  
 print('初期値:', c)  
 # 初期値: Counter()  
 c.update('abcdaab')  
 print('シーケンス:', c)  
 # シーケンス: Counter({'a': 3, 'b': 2, 'c': 1, 'd': 1})  
 c.update({'a':1, 'd':5})  
 print('辞書:', c)  
 # 辞書: カウンター({'d': 6, 'a': 4, 'b': 2, 'c': 1})  
 # 辞書にアクセスすることでCounterオブジェクトにアクセスできます 
 'abcde' の文字の場合: 
     print('%s : %d' % (文字, c[文字]))  
 # elements() メソッドは、すべての Counter データを含むイテレータを返すことができます 
 c = collections.Counter ('非常に')  
 c['z'] = 0  
 print(リスト(c.elements()))  
 # ['e'、'e'、'e'、'm'、'l'、'r'、't'、'y'、'x']  
 # most_common() は、最も共通する上位n個のデータを返します 
 c =コレクション.Counter ('aassdddffff')  
文字の場合、c.most_common(2) でカウントします。  
    print('%s: %d' % (文字, カウント))  
 # 4 位 
 # 日: 3  
 # カウンター オブジェクトは、演算子 +、-、&、| を使用して加算、減算、交差、結合できます。  
 # + は 2 つの辞書内の同じ文字の出現回数を加算し、 - は最初のカウンターと 2 番目のカウンターの差を返します。共通部分は両方のカウンターに存在する要素を示し、カウントは小さい方のカウンターに割り当てられます。また、結合部分は 2 つのカウンターで最も頻繁に出現する要素を示します。  
 c1 =コレクション.Counter(['a', 'b', 'c', 'a', 'b', 'b'])  
 c2 = collections.Counter ('アルファベット')  
印刷 ('C1:', c1)  
印刷 ('C2:', c2)  
 print ('\n合計カウント:')
印刷 (c1 + c2)  
 print ('\n減算:')  
印刷 (c1 - c2)  
 print ('\n交差（正の最小値を取る）:')  
印刷 (c1 & c2)
 print ('\nUnion (最大値を取る):')  
印刷 (c1 | c2)  
 # 出力は次のとおりです:  
 C1: カウンター({'b': 3, 'a': 2, 'c': 1})  
 C2: カウンター({'a': 2, 'l': 1, 'p': 1, 'h': 1, 'b': 1, 'e': 1, 't': 1})  
合計数:  
カウンター({'a': 4, 'b': 4, 'c': 1, 'l': 1, 'p': 1, 'h': 1, 'e': 1, 't': 1})  
減算:  
カウンター({'b': 2, 'c': 1})  
交差（正の最小値を取る）：  
カウンター({'a': 2, 'b': 1})  
結合（最大値を取る）：  
カウンター({'b': 3, 'a': 2, 'c': 1, 'l': 1, 'p': 1, 'h': 1, 'e': 1, 't': 1})

3.3 defaultdict — デフォルト値を持つ辞書

通常、作成された辞書 dict にはデフォルト値は含まれません。つまり、辞書にキー a が含まれていない場合、dct{a} を呼び出すとエラーが発生します。

アルゴリズムやデータ構造を設計する際には、たとえそれが単なるデフォルト値であっても、任意のキーを辞書から取得できることが望まれます。このとき、defaultdict を使用する必要があります。

たとえば、グラフ内のノードに接続されたノードを辞書で表す場合、このノードをキーとして使用し、その値としてそれに接続されたノードのリストを作成します。このとき、defaultdict(list) を使用して、デフォルト値がリストである辞書を作成できます。

 # リストのデフォルト値は空のリストです 
 list_dict = collections.defaultdict (リスト)  
 # intのデフォルト値は0です 
 int_dict =コレクション.defaultdict (int)  
印刷(list_dict['a'])
印刷(int_dict['a'])  
 # 出力: []  
 # 出力: 0

3.4 まとめ

これらは、コレクション内のアルゴリズムやデータ構造を記述するためによく使用されるものです。ソートされた辞書や名前付きタプルなどの他のものはほとんど使用されません。

4. ソート

4.1 リストの並べ替え

リストをソートする方法は 2 つあります。1 つは、リストの組み込みソート関数を使用することです。ソート関数はリストを直接変更し、戻り値はありません。比較キーと比較関数は、パラメーター キーを通じてカスタマイズできます。

2つ目の方法は、Pythonのsorted関数を使う方法です。この関数は自由度が高く、比較関数や比較キーを自分で設定して新しいリストを返すことができます。

比較関数をカスタマイズする必要がある場合は、functools ライブラリから cmp_to_key 関数をインポートして、比較関数をキーに変換する必要があります。使用コードは次のとおりです。

カスタムソートの定義(x,y):  
    x > yの場合:  
        # アイテムを前面に配置することを示すために -1 を返します 
        -1を返す 
    x < yの場合:    
        # アイテムを後ろに配置する必要があることを示すために1を返します 
        戻り値 1  
    0を返す 
 lst = [i は範囲(10, -1, -1)内のiの場合]  
印刷(lst)
ソート()  
印刷(lst)  
 print(sorted(lst, key = cmp_to_key (custom_sort)))  
 # 出力は次のようになります。  
 # [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]  
 # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]  
 # [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

4.2 辞書/タプルのリストのソート

辞書をソートする必要がある場合 (item 関数を使用して辞書をタプル リストに変換)、または各項目に 2 つの値があるタプル リストをソートする必要がある場合は、sorted 関数のキーを使用してソートする値を決定する必要があります。コードは次のとおりです。

 # 文字列を使用してカウンター辞書を作成する 
 d = dict (コレクション.Counter('Hello World'))  
印刷(d)  
 # ソート 
 print(sorted(d.items(), key = lambda x: x[1], reverse = True ))を印刷します。  
 # 出力は次のようになります。  
 # {'H': 1、'e': 1、'l': 3、'o': 2、' ': 1、'W': 1、'r': 1、'd': 1}  
 # [('l', 3), ('o', 2), ('H', 1), ('e', 1), (' ', 1), ('W', 1), ('r', 1), ('d', 1)]

5. 順列と組み合わせ

Python の組み込みモジュール itertools には、順列関数や組み合わせ関数など、いくつかの反復関連関数が統合されています。

5.1 配置

permutations 関数はリストを受け取り、リスト内のすべての要素の完全に順序付けられたリストを返します。

 itertoolsから順列をインポート 
 print(リスト(順列([1,2,3])))  
 # 出力は次のようになります。  
 # [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

5.2 組み合わせ

組み合わせ関数 combinations は 2 つのパラメータを受け取ります。最初のパラメータは結合するリストで、2 番目のパラメータは結合するリストから抽出される要素の数を表す正の整数です。結合されたリストを返します。

 itertoolsからの組み合わせのインポート 
 print(リスト(組み合わせ([1,2,3],2)))  
 # 出力は次のようになります。  
 # [(1, 2), (1, 3), (2, 3)]

6. ヒント

6.1 Pythonには、可変型と不変型があります。関数にパラメータを渡す場合:

• 文字列などの不変のデータ型の場合、パラメータが渡されたときにディープコピーが作成され、新しいデータに変更を加えても元のデータは変更されません。
• リストなどの可変型の場合、パラメータを渡すときに参照が渡されるため、浅いコピーになります。関数内で新しいリストを操作すると、元のリストに影響します。

関数に変数型を渡す必要がある場合は、次のように関数の最初の行でディープコピーを作成できます。

 def test(num_list:リスト):  
    # ディープコピーを作成する 
 num_list num_list = num_list[:]

6.2 リスト内の要素を削除すると、リストの末尾の要素が自動的に前方に移動し、エラーが発生します。

たとえば、リストが [1,2,3,4,5,6] で、リスト内の偶数を削除したい場合、次のコード (間違ったデモンストレーション) に示すように、偶数を直接検索し、そのインデックスを使用して削除すると、申し訳ありませんが、問題が発生します。

 # これはエラーのデモです! ！ ！ ！ ！ ！ ！ ！  
 1番目= [1, 2, 3, 4, 5, 6]  
 iが範囲(len(lst))内にある場合:  
    lst[i] % 2 == 0の場合:  
        lst.pop(i)  
印刷(lst)  
 # 上記のコードは、インデックス範囲外エラーを報告しているため、出力はありません。

次のコードは正しいデモンストレーションです。

 1番目= [1, 2, 3, 4, 5, 6]  
 lst = [i が i 内にある場合、i % 2 != 0]  
印刷(lst)  
 # 出力は次のようになります。  
 # [1, 3, 5]

より複雑なスクリーニング方法が必要な場合は、if i%2 !=0 を関数判定に変更し、関数内にスクリーニング方法を実装できます。

6.3 辞書要素にアクセスするにはgetメソッドを使用する

前述のように、通常の dict 辞書にはデフォルト値がないため、値を見つけるために角括弧を使用してキーを直接配置すると、エラーが発生する可能性があります。

この状況を回避するには、辞書のキーを使用して値を取得するときに、辞書の get 関数を使用する必要があります。

get 関数の最初のパラメータはキーで、2 番目のパラメータはオプションです (デフォルトは None)。渡されたキーが辞書に見つからない場合、2 番目のパラメータによって割り当てられた値が返されます。

7. まとめ

上記はPythonを使って練習問題を解いた際にまとめたものです。間違っている点がありましたらご指摘ください。

この記事は、私自身のための文書を作成するとともに、皆様にとっての利便性を提供することを目的としています。

私の公開アカウント[プログラマー]をフォローして、福祉に関する多くの知識を受け取ってください。

洛陽でございます。ご来訪ありがとうございます。