bash：与えられた親 - 子セットのルートノードを効率的に見つける方法

Question

あなたのファイルに特定の文字で区切られた2つの列があるとします。

問題をもう少し詳しく調べると、ルートノードは決して子ノードとして表示されません。配列の親を追跡し、子の場合は数を増やします。数が0の配列キーがルートノードになります。

awk -F, '
   !($1 in p) {p[$1]=0}   # register a parent in the array
   {p[$2]++}              # increment the count when it's seen as a child
   END {for (n in p) if (p[n] == 0) print n}
' bigfile

@filbrandenが指摘したように、これはルートノードのみを探します。

職場でも同様の状況があります。 Oracleデータベースには、親項目と子項目を含む表があります。サブIDをマッピングするビューを作成します。道親につながるID：

id parent_id
 1 null
 2 1
 3 2
 4 1
 5 null
 6 5

ビューは次のとおりです。

id id_path
 1 1
 2 1\2
 3 1\2\3
 4 1\4
 5 5
 6 5\6

これはPL / SQLを介して達成されます。

CREATE OR REPLACE VIEW "SCHEMA"."ITEM_PATHS" ("ID", "ID_PATH") AS
SELECT 
    pci."ID",
    substr(SYS_CONNECT_BY_PATH(pci.id, '\'), 2)  AS ID_PATH
  FROM schema.parent_child_items pci
    START WITH parent_id IS NULL
    CONNECT BY prior id = parent_id;

したがって、データベースでもこれは小さな問題ではありません。しかし、私はデータベースがより大きなデータセットをよりよく処理できると信じています。

Answer 1