☰

bash：如何有效地找到给定父子集的根节点

tag-icon • tag-icon shell-script osx numeric-data
bash：如何有效地找到给定父子集的根节点

我有一个巨大（几 GB）的父 ID、子 ID 对文件。我还有一组（不完整的）已知根节点。

对于每个已知的子节点，我需要找到一个根节点，即该根节点要么不具有已知的进一步的父子对，要么属于一组已知的根节点。找到这样的根节点后，我需要将其作为第三个字段写入上面的对组中。

在命令行环境中最有效的工具和方法是什么？

假设平均节点距根的深度约为 5-10 层；数百个叶节点，深度达数百级。

我需要 MacOS (High Sierra) 和某些 Gnu/Linux 之间的可移植性；我在 MacOS 上有 GNU 工具集；在 Mac 和 Linux 上免费安装更多命令行工具。假设两个平台都有 4GB RAM；不错的SSD；过时的CPU。

答案1

我假设您的文件有 2 列，由某个字符分隔

更仔细地看一下这个问题，根节点永远不会作为子节点出现。跟踪数组中的父级，并在它是子级时增加计数。计数为零的数组键将是根节点。

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 映射到小路通向父级的 ids：

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对并找到第一个祖先，输出一grandparent child对，然后第二步将输出一great-grandparent child对，依此类推。

你可以使用它来实现join(1)，您可以在其中将一个文件的第一个字段与另一个文件的第二个字段匹配，从而用其父节点替换节点。join(1)要求对文件进行排序，并且可以使用轻松完成sort(1)。

您可以使用下面的脚本来完成此操作。它假设输入文件每行nodes.txt都有一对空格分隔的节点。parent child它将产生每行roots.txt都有对的行的结果。root 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 倍（一个用于索引nodes.bychild，两个用于nodes.0同时nodes.1存在一段时间，一个用于排序，一个用于结果roots.txt文件。 ）

每次迭代都有两次调用join(1)，其中一次调用更深一层，另一次调用（使用-v）来查找不存在匹配的情况，用于检测何时找到根节点。这开始暴露出一些缺点join(1)，拥有更灵活的工具将能够一步完成这两项任务。更灵活的工具的另一个优点是保留从子级一直到根的路径，这对于join(1)单独使用来说并不那么明显。替换join(1)为用高级语言（例如 Python）编写的简单工具可能会大大提高该脚本的功能。

复杂性分析

该join(1)工具非常好用，因为它使用 O(1) 空间并花费 O(n) 时间。由于它需要对文件进行排序，因此它一次只考虑每个文件的一行，推进后面的行（或在匹配时同时推进），因此空间恒定。由于它只读取每个文件的每一行一次，因此它以线性时间执行。

所以循环复杂度的重要因素是sort(1)，它需要 O(n log n) 时间。当输入非常大时， Unix 的实现sort(1)使用临时文件来存储临时结果，因此可以对比内存大得多的数据集进行排序。使用的临时磁盘空间使用sort(1)O(n) 空间（上面的磁盘要求中已提到。）

由于每个循环迭代需要 O(n log n) 时间，因此总运行时间将与运行此循环的次数成正比，其次数与子项与其根之间的级别相同。最糟糕的情况是从子节点一直到根节点只有一条链，在这种情况下深度将为n该算法将采用 O(n² log n)，但在大多数实际情况下，预计深度将远低于n所以时间复杂度比这个小很多。

此外，当您开始进入具有更大深度的节点的长尾时，n通常会更快地变小，因此在您的情况下，考虑 5-10 倍（典型深度）而不是 100 倍（长尾的最坏情况深度）可能更容易。

这里一个明显的改进是在计算当前步骤时考虑先前步骤的输出。例如，如果我建立了 (3->2->1) 关系和 (5->4->3) 关系，我应该能够直接转到 (5->1) 而不是 (5- >2).进一步的步骤也将呈指数级加快（例如，9->5 和 5->1 变为 9->1，当前方法需要 8 个步骤，而优化后的方法只需 3 个步骤。）这将采取病态的方法。复杂度为 O(n log² n) 的情况（因为深度现在是指数级的，因此只需要 O(log n) 步即可达到最大值），并且对于正常情况也可能非常有帮助。

可能可以使用 来实现join(1)，但如前所述，用高级语言编写的更灵活的脚本可能会更好地用于这种方法（例如，智能地合并来自多个源的行，这是为特定算法量身定制的.)

如果这是您的常见用例，也许可以花时间实施这种更智能的方法。如果这是一次性的，那么上面的快速而肮脏的脚本可能就足够了......

（如果这是一个重要的用例，请改用数据库！）

答案3

如果我很好地理解你的描述和要求，看来你必须从一组层次相关的节点重建一棵树。

我赞同所有其他人的评论，即这是一个适当的数据库引擎的工作，但如果您必须使用标准命令行工具，那么另一种选择可能是将文件系统用作“数据库”，即作为您的节点的索引。

因此，获得最终结果需要所有节点经过 2 次：

  • 首先从输入数据集传递以在文件系统上创建它的表示，其中每个单个节点将是一个目录，其中包含指向其父节点/目录的符号链接
  • 第二遍向上遍历所有节点到其根节点，然后根据您的要求显示每个节点及其父节点和根节点

尽管概念上很简单，但它确实有一些显着的缺点。

主要的缺点基本上是您依赖于您使用的文件系统的功能，并且您很可能需要准备一个为此目的而设计的专用文件系统，并考虑以下因素：

  • 文件系统在处理单个目录中包含的数百万个目录时的性能：例如 ext4 就不太擅长这一点，因为它在处理数万个目录后就会下降很多； xfs 比 ext4 更好，但也许这方面的最佳选择是 reiserfs（可能是最好的）或 btrfs（比 reiserfs 慢一点）；然而，根据您提到的数字，即使使用 btrfs 或 reiserfs，您仍然需要将节点/目录的数量划分为几个中间（子级别）子目录，这样您就不会在任何目录中放置超过 1M 的目录。一个目录
  • 文件系统在存储如此多的节点/目录时的紧凑性（所需的磁盘空间），其中每个节点/目录仅包含一个符号链接和（第二遍之后）一个非常小的文件：这里您应该承受大量的磁盘空间浪费，因为文件系统的标准配置通常会分配每个目录或文件 4k，每个节点总共 8-12k，尽管文件系统允许在格式化时对此进行一些调整，特别是最小分配大小，但我预计每个节点不少于 2-3k；通过将节点的父节点和根存储在中，您可能会变得更加紧凑扩展属性而不是符号链接和文件，但每个节点仍然可能不少于 1k

另一个缺点可能是您使用什么语言来处理所有这些：使用 shell 脚本将是非常第一次传递很慢，因为每个单个节点都需要一个mkdir和一个ln -s（或者setfattr在 Linux 上，xattr在 MacOS 上是一个）链接到其父节点，这意味着 2 个 forks-and-exec 乘以数千万倍。如果您可以使用允许您直接使用所涉及的系统调用（即 mkdir(2) 和 symlink(2)/setxattr(2)）的语言来开发整个第一遍，那么这种 fork-and-exec 的事情就可以被消除。

具体来说，一个简单的例子第一遍的脚本（主要是伪代码，只是为了显示要应用的基本操作）可能是：

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

该脚本假设每个子/父对都由空格分隔并单独占一行，并期望已知的根作为一行，每个只有一个 ID（即没有父项），所有内容都在标准输入上提供。

为了简化演示，该脚本做了不是使用中间子目录，即它在一个（实际上是当前）目录中创建所有节点/目录。正如所说，这是一个禁忌当节点超过 1M 时。

提供一个（或多个）子级别的目录需要了解节点的 ID 特征，以便选择最佳的分区方法。例如，如果您的 20 位 ID 使用的实际地址空间是均匀分布的，您可能会使用简单的模运算，可能会在子目录的其他级别重复。重要的一点是，任何子级别都可以根据 ID 进行计算，这意味着您不能在添加的每个节点上仅使用递增计数器。

如果您在第一遍中仍然活着 (;-))，那么第二遍可能会轻而易举，即使只使用如下所示的 shell 脚本：

#!/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 位数字之外，或者取决于取决于它们的实际地址空间及其稀疏性，当然还取决于输入数据集已经（未）排序的程度。

相关内容