☰

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

tag-icon • tag-icon shell-script osx numeric-data
bash：与えられた親 - 子セットのルートノードを効率的に見つける方法

私は親ID、子IDペアの巨大な（数GB）ファイルを持っています。また、既知のルートノードの（不完全な）セットがあります。

既知の子ノードごとに、既知の親と子のペアがないか、または既知のルートノードセットに属するルートノードを見つける必要があります。これらのルートノードが見つかったら、それを上のペアの3番目のフィールドとして作成する必要があります。

コマンドライン環境で最も効果的なツールと方法は何ですか？

ルートの平均ノード深さが約5-10レベルであると仮定すると、何百もの葉ノードがある場合、深さは数百レベルに達します。

MacOS（High Sierra）と一部のGnu / Linuxの間の移植性が必要です。 MacOSにGNUツールセットがあり、MacとLinuxにさらにコマンドラインツールを無料でインストールします。どちらのプラットフォームも4GBのRAM、まともな古いCPUを持っているとします。

答え1

あなたのファイルに特定の文字で区切られた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;

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

答え2

私が提案することは、もはや進行が不可能になるまで、各段階で一段階深く入り、根本的な原因を発見する反復アプローチを使用することです。したがって、最初のステップでは、parent childペアを取り、最初の祖先を見つけてペアを出力してから、2grandparent child番目のステップでペアを出力するgreat-grandparent child式に進みます。

これを使用して達成できます。join(1)ここで、あるファイルの最初のフィールドを別のファイルの2番目のフィールドと一致させ、ノードを親ノードに置き換えます。join(1)ファイルを並べ替える必要があり、以下を使用して簡単に実行できます。sort(1)。

これを行うには、以下のスクリプトを使用できます。入力ファイルには、1行にスペースでnodes.txt区切られた1対のノードがあるとします。各行の行ペアを含む結果がparent child生成されます。roots.txtroot child

export LC_COLLATE=C
sort -k 2 nodes.txt -o nodes.bychild
: >roots.txt
sort -k 1 nodes.txt -o nodes.0
depth=0
while [[ -s nodes.0 ]]; do
  echo "Depth: $((depth++)) - $(date)"
  join -1 2 -2 1 -o '1.1 2.2' nodes.bychild nodes.0 | sort -k 1 -o nodes.1
  # Nodes not present in nodes.1 have
  # their root in nodes.0 already:
  join -1 2 -2 1 -v 2 -o '2.1 2.2' nodes.bychild nodes.0 >>roots.txt
  # Next step:
  mv nodes.1 nodes.0
done
rm nodes.0 nodes.bychild
sort -k 2 roots.txt -o roots.txt

あなたはできますオンラインでお試しください小さなサンプル入力用。

この方法を使用するには、ハードドライブに空き容量を確保するためにデータセットサイズの約5倍が必要です（インデックス用に1個、同時に存在するnodes.bychild2個、ソート用に1個、結果ファイル用に1個）。nodes.0nodes.1roots.txt

各反復には2つの呼び出しがありますjoin(1)。 1つはもう1つのレベルを深く動かし、もう1つは-vルートノードが見つかったときに検出するために一致するものがない場合を見つけることです。これにより、いくつかの欠点が明らかになり始め、join(1)より柔軟なツールを使用すると、2つのタスクを1つのステップで実行できます。より柔軟なツールのもう一つの利点は、子からルートへのパスが保存されることです。これはjoin(1)単独で使用してもあまり明確ではありません。これをjoin(1)高度な言語（Pythonなど）で書かれた簡単なツールに置き換えることで、このスクリプトの機能を大幅に向上させることができます。

複雑性分析

このjoin(1)ツールはO（1）スペースを使用し、O（n）時間がかかるため、非常に使いやすいです。ファイルをソートする必要があるため、各ファイルを一度に1行だけ考慮し、次の行（または一致する場合は同時に2行）を進めるため、スペースは一定です。各ファイルの各行を一度だけ読み取るため、線形時に実行されます。

したがって、循環的複雑さの重要な要素は、sort(1)O（n log n）時間がかかることです。入力が非常に大きい場合、Unix実装はsort(1)一時ファイルを使用して一時結果を保存するため、メモリよりもはるかに大きなデータセットをソートできます。使用される一時ディスク領域はsort(1)O（n）領域を使用します（上記のディスク要件で説明されています）。

各ループ反復にはO（n log n）時間がかかるため、合計実行時間はこのループが実行される回数に比例し、子とそのルート間のレベル数に比例します。最悪の場合は、子ノードからルートノードまで1つのチェーンしかないことです。この場合、深さは次のようになります。NこのアルゴリズムはO（n² log n）を使用しますが、ほとんどの実際の場合、深さは次のものよりはるかに低いと予想されます。Nしたがって、時間の複雑さはこれよりはるかに小さいです。

また、より深い深さでノードの長い尾に入り始めるとN通常、より速く小さくなるため、100x（長い尾の場合は最悪の場合の深さ）よりも5〜10x（一般的な深さ）を考える方が簡単になる可能性があります。

ここで明らかな改善点は、現在のステップを計算するときに前のステップの出力を考慮することです。たとえば、(3->2->1)関係と(5->4->3)関係を設定すると、(5->の代わりに(5->1)に直接移動できるはずです。指数関数的に高速化されます（例：9-> 5および5-> 1は9-> 1になり、現在の方法は8段階を必要としますが、最適化された方法は3段階のみ必要です） - ポーズ方法。複雑さがO（n log² n）の場合（深さは指数的であるため、最大値に達するためにO（log n）ステップのみが必要です）、一般的な場合にも非常に役立ちます。

join(1)カスタムメイドを使用して実装することもできます

これが一般的なユースケースであれば、時間をかけてより賢明なアプローチを実装してみてください。これがワンタイムであれば、上記の迅速で汚れたスクリプトで十分です。

（重要なユースケースの場合は、代わりにデータベースを使用してください！）

答え3

もしあなたの説明と要件をよく理解してください。階層的に関連するノードのセットからツリーを再構成する必要があるようです。

私はこれが適切なデータベースエンジンのための仕事であるという他のすべての人の意見に同意しますが、標準のコマンドラインツールを使用する必要がある場合は、ファイルシステムを「データベース」、つまりノードインデックスとして使用することが別のオプションかもしれません。

したがって、最終結果を得るには、すべてのノードを2回通過する必要があります。

  • まず、入力データセットから渡され、ファイルシステムに表現を生成します。ここで、個々のノードは親ノード/ディレクトリへのシンボリックリンクを含むディレクトリになります。
  • 2 番目のパスは、すべてのノードをルートノードまで巡回し、要件に応じて親ノードとルートノードとともに各ノードを表示します。

概念的には単純ですが、いくつかの重要な欠点があります。

主な欠点は、基本的に使用しているファイルシステムの機能によって異なり、次の要因を考慮して、この目的のために設計された専用ファイルシステムを準備する必要がある可能性が高いことです。

  • 単一のディレクトリに含まれている数百万のディレクトリを処理するときのファイルシステムのパフォーマンス：たとえば、ext4は数万のディレクトリを処理した後にあまり落ちないため、あまり良くありません。しかし、おそらくこれが最良のオプションはreiserfsです。 （おそらく最高です）またはbtrfs（reiserfsより少し遅い）ですが、上記の数字によると、btrfsまたはreiserfsを使用しても、ノード/ディレクトリの数を中間（下位レベル）のサブディレクトリに分割する必要があります。どのディレクトリにも1M以上を入れないでください。ディレクトリ
  • あまりにも多くのノード/ディレクトリを保存する場合、ファイルシステムの圧縮性（必要なディスク容量）（各々はシンボリックリンクのみを含み、2番目のパス以降）非常に小さいファイル：ここでは無駄なディスク容量が必要です。ファイルシステムの標準構成は通常、ディレクトリまたはファイルあたり4k、つまりノードあたり合計8〜12kを割り当てます。ただし、ファイルシステムでは、フォーマット時にはいくつかの調整、特に最小割り当てサイズが許可されますが、それ以下は期待できません。ノードあたり2〜3,000を超えるノードの親とルートを保存すると、はるかにコンパクトになります。拡張属性シンボリックリンクとファイルの代わりに、それでもノードあたり1,000個以上です。

もう1つの欠点は、これらすべてを処理するために使用する言語です。シェルスクリプトの使用は非常にmkdir各単一ノードには、その親ノードへの分岐と実行ln -s（またはsetfattrLinuxでは単一、MacOSでは単一）リンクが必要なため、最初のパスは遅くなります。xattrこれは、2つの分岐と実行乗算数千万回を意味します。このブランチと実行タスクは、関連するシステムコール（たとえば、mkdir（2）およびSymlink（2）/ setxattr（2））を直接使用できる言語で完全な最初のステップを開発できればよいでしょう。削除されました。

具体的には、シンプルはい最初のパスのスクリプト（主に適用される基本タスクを表示するための擬似コード）は次のとおりです。

while read -r child parent; do
    # here I use '-p' only for 'no error if existing'
    mkdir -p $child $parent  # <-- note lack of quotes for once, so to ignore empty $parent
    [ $parent ] && (cd $child && ln -s ../${parent} parent)
done

スクリプトは、各子/親ペアが空白で区切られて独自の行にあると仮定し、既知のルートがそれぞれ1つのIDのみを持つ（つまり、親なし）行と見なし、すべて標準入力に提供されます。

デモを簡素化するために、スクリプトは次のことを行います。いいえ中間サブディレクトリを使用します。つまり、1つの（実際には現在の）ディレクトリにすべてのノード/ディレクトリを作成します。言ったように、それはタブーです。ノードが1Mを超える場合。

1つ以上のディレクトリ下位レベルを提供するには、最良の分割方法を選択するためにノードのID属性についての知識が必要です。たとえば、20ビットIDで使用される物理アドレス空間が均等に分散されている場合は、単純なモジュール操作を使用でき、サブディレクトリの異なるレベルで繰り返すこともできます。重要なのは、すべての下位レベルがIDに基づいて計算できることです。つまり、追加する各ノードに増分カウンタを使用することはできません。

最初のステップ（;-））でまだ生きている場合は、次のシェルスクリプトのみを使用しても、2番目のステップはおそらく非常に簡単です。

#!/bin/bash

# make sure $PWD has physical dir
cd -P .
fs="${1:-$PWD}"

# for each node
while read -r node; do
    cd "$node"
    # check that node does not already have a root: if it does, read that and do not enter the loop
    while ! { [ -e myroot ] && read -r root < myroot; }; do
        # remember visited node
        traversed+=("$node")
        # if node does not have parent it is a root, so quit loop
        [ -L parent ] || { root="$node" && parents+=() && break; }
        # go up to parent, which becomes node to consider
        cd -P parent
        node="$PWD"
        # add to visited parents
        parents+=("$node")
    done
    # cd back to the root of this filesystem
    cd "$fs"
    for ((i=0; i < ${#traversed[@]}; i++)) ; do
        # for each traversed node (if any) set its root and display it
        echo "$root" > "${traversed[i]}/myroot"
        echo "${traversed[i]##*/}" "${parents[i]##*/}" "${root##*/}"
    done
    traversed=()
    parents=()
done < <(find "$fs" -mindepth "$((${2:-0}+1))" -type d)

コンパイルされた言語は当然より速く、親とルートがシンボリックリンクやファイルではなく各ノード/ディレクトリの拡張属性に保存されると、はるかに高速になります。

スクリプトは分岐して実行する必要はなく、ノードのナビゲーション中に見つかった親エントリを表示して、分岐が複数回ナビゲートされないようにします。また、物理ノードを含む固定数の中間サブディレクトリを許可し、ファイルシステムのルートと中間サブディレクトリの数を引数として想定しているため、次のように実行できます。

traverse.sh /mnt/dataset-on-filesystem 3

これは、3ノード自身のディレクトリの前に3つのレベルのサブディレクトリがあることを意味します。

このスクリプトで使用されるプロセスは、最も深いチェーンを最初に受け取ることによって大きな利点を得ることができます。ただし、このチェーンは他の多くの浅いチェーンでも共有されます。これにより、初期段階で多くの親チェーンが表示され、多くの後続のチェーンでより少ない巡回が必要になるため、スクリプトはすべてのノードをより迅速に消費します。

このコマンドを実行すると、必要な出力全体を標準出力として取得できるだけでなく、各ノードのルートがノードのディレクトリファイルに保存され、いつでも使用myrootできます。cat

最後に、ファイルシステムの機能に加えて、このソリューションの多くの詳細には、パス間キャッシュを実行するか、IDがパックできるかどうか（または方法）に応じて最適化する余地があります。 20ビット数は、実際のアドレス空間とスパース性、および入力データセットがどのようにソートされたか（ソートされていない）かによって異なります。

関連情報