Python 実用コード - 無限分類ツリー構造生成アルゴリズム

バックエンド開発者にとっては、無限レベルの分類に強い印象を受けたのではないでしょうか。最初はかなり時間がかかったのではないでしょうか。

無限分類ツリー構造の応用シナリオは多数あります。たとえば、バックエンド開発では、ユーザーの関連権限を読み取ってツリー構造を生成する必要があります。フロントエンド開発で権限ツリーを取得したら、構造に従ってユーザーがアクセスする権限を持つ列を表示できます。別の例として、Web ページの列分類があります。

著者も、最初にツリー構造を生成する必要に迫られたとき、頭を悩ませました。その後、コードが少なく、明確で理解しやすい生成アルゴリズムを見つけました。それは、再帰です。

まず、データベースに保存されているカテゴリ情報が次のとおりであることを確認します。

 [
 { "id" : 1 , "name" : '電化製品' , "parent" : 0 },
 { "id" : 2 、 "name" : 'フルーツ' 、 "parent" : 0 },
 { "id" : 3 , "name" : '家電製品' , "parent" : 1 },
 { "id" : 4 , "name" : 'ヘアドライヤー' , "parent" : 3 },
 { "id" : 5 , "name" : '扇風機' , "parent" : 3 },
 { "id" : 6 , "name" : 'テーブルランプ' , "parent" : 3 },
 { "id" : 7 , "name" : '業務用電化製品' , "parent" : 1 },
 { "id" : 8 , "name" : '大型電気鍋' , "parent" : 7 },
 ]

親フィールドには、このエントリの親番号が記録されます。たとえば、ヘアドライヤーの親番号は 3 で、ヘアドライヤーは家電製品に属していることを意味し、家電製品の親番号は 1 で、家電製品は電化製品のカテゴリに属していることを意味します。ヘアドライヤーのエントリを電化製品のエントリに関連付ける直接的な識別はありませんが、電化製品 <- 家電製品 <- ヘアドライヤーの関係を示すツリー構造が必要です。

著作権透かし WeChat 公開アカウント Python プログラミングリファレンス

親を通じて親番号を見つけ、関連付け関係を確立する操作は、実際にはすべてのノードが見つかるまで繰り返される操作です。これは再帰アルゴリズムと非常に一致しており、対応する再帰コードは簡単に記述できます。

 def generate_tree(ソース、親):
 木 = []
ソース内の項目:
項目[ "親" ] == 親の場合:
 アイテム[ "child" ] = generate_tree(source, アイテム[ "id" ])
 ツリーに追加(アイテム)
リターンツリー

データベースに保存されている情報を generate_tree 関数に渡すだけです。この再帰コードは、親を使用して往復ループで子ノードを見つけ、見つけた子ノードをツリーに追加します。完全なコードは次のとおりです。

 jsonをインポート
def generate_tree(ソース、親):
 木 = []
ソース内の項目:
項目[ "親" ] == 親の場合:
 アイテム[ "child" ] = generate_tree(source, アイテム[ "id" ])
 ツリーに追加(アイテム)
リターンツリー
__name__ == '__main__'の場合:
 権限ソース = [
 { "id" : 1 , "name" : '電化製品' , "parent" : 0 },
 { "id" : 2 、 "name" : 'フルーツ' 、 "parent" : 0 },
 { "id" : 3 , "name" : '家電製品' , "parent" : 1 },
 { "id" : 4 , "name" : 'ヘアドライヤー' , "parent" : 2 },
 { "id" : 5 , "name" : '扇風機' , "parent" : 3 },
 { "id" : 6 , "name" : 'テーブルランプ' , "parent" : 3 },
 { "id" : 7 , "name" : '業務用電化製品' , "parent" : 1 },
 { "id" : 8 , "name" : '大型電気鍋' , "parent" : 7 },
 ]
 permission_tree = generate_tree(permission_source, 0 )
 print(json.dumps(permission_tree、ensure_ascii=False))

実行してみて、構造が期待どおりであるかどうかを確認してください。

キャッシュ最適化アルゴリズムの使用

再帰アルゴリズムには繰り返し計算が多く含まれており、余分なリソースを消費するだけでなく、関数の実行効率も低下します。そのため、再帰を最適化する必要があります。ここでは、関数実行の効率を向上させるためにキャッシュ最適化方式が使用されます。

基本的な考え方は、このエントリの番号をリストに追加し、ノード関係が見つかるたびにそれをキャッシュして、このエントリに対してノード関係が見つかったことを示すことです。関数を実行する往復ループ内でこのエントリが再度検出された場合は、スキップできます。コードの変更は簡単で、キャッシュリストと制御フローステートメントを追加するだけです。

 def generate_tree(ソース、親、キャッシュ=[]):
 木 = []
ソース内の項目:
キャッシュ内にアイテム[ "id" ]がある場合:
続く 
項目[ "親" ] == 親の場合:
 キャッシュに追加(アイテム[ "id" ])
 アイテム[ "child" ] = generate_tree(ソース、アイテム[ "id" ]、キャッシュ)
 ツリーに追加(アイテム)
リターンツリー