如何在 shell 中对有向图中的值进行快速求和？
How to fast sum values in directed graph in shell?
我有一个有向图，文件中存储了大约 2000 个节点。每条线代表从第一列中存储的节点到第二列中存储的节点的一条边，甚至可以很容易地可视化数据，例如 dot(1) 中的数据。列由制表符分隔，行由换行符分隔，节点以任何 a-zA-Z0-9_ 字符命名。树可以有多个根，也可以有环，这些都可以忽略。我不关心循环，它们是多余的，但它们可以在输入中发生。下面我展示了一个图表示例，用 tr 代替制表符和此处文档的空格，以便轻松重现输入文件：
tr ' ' '\t' <<EOF >connections.txt
str1 str2
str2 str3
str3 str4
str100 str2
str100 str101
str101 str102
EOF
我还有图中某个节点的列表，称为 heads。这些将是起始节点，即。头：
tr ' ' '\t' <<EOF >heads.txt
str1
str100
EOF
而且我还有一个与每个节点关联的 "cost" 列表。一些随机数据的示例：
tr ' ' '\t' <<EOF >cost.txt
str1 1
str2 5
str3 10
str4 548
str100 57
str101 39
str102 23
EOF
我想在从存储在 head.txt 中的节点遍历树时对每个节点的 "cost" 求和，并使用每个叶子的一些遍历信息打印成本。
我想：
- 对于 heads.txt 中的每个节点
- 将节点 costs.txt 的成本求和到某个变量中
- 在 connections.txt
中找到该节点
- 找到这个节点连接到什么
- 并为节点连接到的每个节点重复该算法
- 当节点没有连接时，打印成本总和
理想情况下，脚本如下所示：
$ script.sh heads.txt connections.txt cost.txt
str1->str2->str3->str4 1+5+10+548 564
str100->str2->str3->str4 57+5+10+548 620
str100->str101->str102 57+39+23 119
我什至写了这个，而且有效：
#!/bin/bash
set -euo pipefail
headsf=
connectionsf=
costf=
get_cost() {
grep "^"$'\t' "$costf" | cut -f2 || echo 0
}
get_conn() {
grep "^"$'\t' "$connectionsf" | cut -f2
}
check_conns() {
grep -q "^"$'\t' "$connectionsf"
}
f_output() {
printf "%s\t%s\n" "" ""
}
f() {
local func cost
func=""
cost=$(get_cost "$func")
if ! check_conns "$func"; then
f_output "${2:+->}$func" "${3:++}$cost"
return
fi
get_conn "$func" |
while IFS=$'\t' read -r calls; do
if [ "$func" = "$calls" ]; then
echo "$func is recursive" >&2
continue
fi
if <<<"" grep -q -w "$calls"; then
printf " calls recursive $calls\n" >&2
continue
fi
f "$calls" "${2:+->}$func" "${3:++}$cost"
done
}
while IFS= read -r head; do
f "$head" "" ""
done < "$headsf" |
while IFS=$'\t' read -r func calc; do
tmp=$(<<<$calc bc)
printf "%s\t%s\t%s\n" "$func" "$calc" "$tmp"
done |
column -t -s $'\t'
然而，它在更大的输入上慢得不可思议。即使这里有示例文件（只有 6 行），脚本在我的机器上也需要 200 毫秒。我怎样才能加快速度？输入是否可以排序，以某种方式连接以加快速度（grep 不关心输入是否排序）？这可以在 awk 或其他 unix 工具中更快地完成吗？
我想将自己限制在 bash shell 和标准 *unix 工具、coreutils、moreutils、datamash 等。我尝试在 awk 中执行此操作，但失败了，我不知道如何在 awk 的输入中递归查找某些内容。这对我来说 "doable" 在 shell 脚本中感觉非常快。
由于还没有人发布答案，这里有一个 awk 解决方案作为起点：
#!/usr/bin/awk -f
BEGIN {
FS=OFS="\t"
}
FILENAME=="connections.txt" {
edges[,++count[]]=
next
}
FILENAME=="cost.txt" {
costs[]=
next
}
FILENAME=="heads.txt" {
f()
}
function f(node,
path,cost,sum,prev,sep1,sep2,i) {
if(node in prev)
# cycle detected
return
path=path sep1 node
cost=cost sep2 costs[node]
sum+=costs[node]
if(!count[node]) {
print path,cost,sum
}
else {
prev[node]
for(i=1;i<=count[node];++i)
f(edges[node,i],path,cost,sum,prev,"->","+")
delete prev[node]
}
}
在 heads.txt 之前读取 connections.txt 和 cost.txt。
它的输出（填充）：
$ awk -f tst.awk connections.txt cost.txt heads.txt
str1->str2->str3->str4 1+5+10+548 564
str100->str2->str3->str4 57+5+10+548 620
str100->str101->str102 57+39+23 119
你说你只需要标准工具，但你也提到在你的数据上使用 dot，所以我假设你有其他可用的 graphviz 实用程序......特别是，gvpr ，类似于图表的 awk：
#!/usr/bin/env bash
graph=$(mktemp)
join -t$'\t' -j1 -o 0,1.2,2.2 -a2 \
<(sort -k1,1 connections.txt) \
<(sort -k1,1 cost.txt) |
awk -F$'\t' 'BEGIN { print "digraph g {" }
{ printf "%s [cost = %d ]\n", ,
if ( != "") printf "%s -> %s\n", , }
END { print "}" }' > "$graph"
while read root; do
gvpr -a "$root" '
BEGIN {
int depth;
int seen[string];
string path[int];
int costs[int];
}
BEG_G {
$tvtype = TV_prepostfwd;
$tvroot = node($, ARGV[0]);
}
N {
if ($.name in seen) {
depth--;
} else {
seen[$.name] = 1;
path[depth] = $.name;
costs[depth] = $.cost;
depth++;
if (!fstout($) && path[0] == ARGV[0]) {
int i, c = 0;
for (i = 0; i < depth - 1; i++) {
printf("%s->", path[i]);
}
printf("%s\t", $.name);
for (i = 0; i < depth - 1; i++) {
c += costs[i];
printf("%d+", costs[i]);
}
c += $.cost;
printf("%d\t%d\n", $.cost, c);
}
}
}' "$graph"
done < heads.txt
rm -f "$graph"
运行 创建数据文件后：
$ ./paths.sh
str1->str2->str3->str4 1+5+10+548 564
str100->str2->str3->str4 57+5+10+548 620
str100->str101->str102 57+39+23 119
或者，由于它无处不在，它也可能是标准的，基于 sqlite 的解决方案。与上面的不同，这个甚至不需要 bash/zsh/ksh93。
$ sqlite3 -batch -noheader -list <<EOF
.separator "\t"
CREATE TABLE heads(node TEXT);
.import heads.txt heads
CREATE TABLE costs(node TEXT PRIMARY KEY, cost INTEGER) WITHOUT ROWID;
.import cost.txt costs
CREATE TABLE connections(from_node TEXT, to_node TEXT
, PRIMARY KEY(from_node, to_node)) WITHOUT ROWID;
.import connections.txt connections
WITH RECURSIVE paths(tail, path, costs, cost) AS
(SELECT h.node, h.node, c.cost, c.cost
FROM heads AS h
JOIN costs AS c ON h.node = c.node
UNION ALL
SELECT conn.to_node, p.path || '->' || conn.to_node
, p.costs || '+' || c.cost, p.cost + c.cost
FROM paths AS p
JOIN connections AS conn ON conn.from_node = p.tail
JOIN costs AS c ON c.node = conn.to_node
)
SELECT path, costs, cost FROM paths AS p
WHERE tail NOT IN (SELECT from_node FROM connections)
ORDER BY path;
EOF
str1->str2->str3->str4 1+5+10+548 564
str100->str101->str102 57+39+23 119
str100->str2->str3->str4 57+5+10+548 620
我有一个有向图，文件中存储了大约 2000 个节点。每条线代表从第一列中存储的节点到第二列中存储的节点的一条边，甚至可以很容易地可视化数据，例如 dot(1) 中的数据。列由制表符分隔，行由换行符分隔，节点以任何 a-zA-Z0-9_ 字符命名。树可以有多个根，也可以有环，这些都可以忽略。我不关心循环，它们是多余的，但它们可以在输入中发生。下面我展示了一个图表示例，用 tr 代替制表符和此处文档的空格，以便轻松重现输入文件：
tr ' ' '\t' <<EOF >connections.txt
str1 str2
str2 str3
str3 str4
str100 str2
str100 str101
str101 str102
EOF
我还有图中某个节点的列表，称为 heads。这些将是起始节点，即。头：
tr ' ' '\t' <<EOF >heads.txt
str1
str100
EOF
而且我还有一个与每个节点关联的 "cost" 列表。一些随机数据的示例：
tr ' ' '\t' <<EOF >cost.txt
str1 1
str2 5
str3 10
str4 548
str100 57
str101 39
str102 23
EOF
我想在从存储在 head.txt 中的节点遍历树时对每个节点的 "cost" 求和，并使用每个叶子的一些遍历信息打印成本。
我想：
- 对于 heads.txt 中的每个节点
- 将节点 costs.txt 的成本求和到某个变量中
- 在 connections.txt 中找到该节点
- 找到这个节点连接到什么
- 并为节点连接到的每个节点重复该算法
- 当节点没有连接时，打印成本总和
理想情况下，脚本如下所示：
$ script.sh heads.txt connections.txt cost.txt
str1->str2->str3->str4 1+5+10+548 564
str100->str2->str3->str4 57+5+10+548 620
str100->str101->str102 57+39+23 119
我什至写了这个，而且有效：
#!/bin/bash
set -euo pipefail
headsf=
connectionsf=
costf=
get_cost() {
grep "^"$'\t' "$costf" | cut -f2 || echo 0
}
get_conn() {
grep "^"$'\t' "$connectionsf" | cut -f2
}
check_conns() {
grep -q "^"$'\t' "$connectionsf"
}
f_output() {
printf "%s\t%s\n" "" ""
}
f() {
local func cost
func=""
cost=$(get_cost "$func")
if ! check_conns "$func"; then
f_output "${2:+->}$func" "${3:++}$cost"
return
fi
get_conn "$func" |
while IFS=$'\t' read -r calls; do
if [ "$func" = "$calls" ]; then
echo "$func is recursive" >&2
continue
fi
if <<<"" grep -q -w "$calls"; then
printf " calls recursive $calls\n" >&2
continue
fi
f "$calls" "${2:+->}$func" "${3:++}$cost"
done
}
while IFS= read -r head; do
f "$head" "" ""
done < "$headsf" |
while IFS=$'\t' read -r func calc; do
tmp=$(<<<$calc bc)
printf "%s\t%s\t%s\n" "$func" "$calc" "$tmp"
done |
column -t -s $'\t'
然而，它在更大的输入上慢得不可思议。即使这里有示例文件（只有 6 行），脚本在我的机器上也需要 200 毫秒。我怎样才能加快速度？输入是否可以排序，以某种方式连接以加快速度（grep 不关心输入是否排序）？这可以在 awk 或其他 unix 工具中更快地完成吗？
我想将自己限制在 bash shell 和标准 *unix 工具、coreutils、moreutils、datamash 等。我尝试在 awk 中执行此操作，但失败了，我不知道如何在 awk 的输入中递归查找某些内容。这对我来说 "doable" 在 shell 脚本中感觉非常快。
由于还没有人发布答案，这里有一个 awk 解决方案作为起点：
#!/usr/bin/awk -f
BEGIN {
FS=OFS="\t"
}
FILENAME=="connections.txt" {
edges[,++count[]]=
next
}
FILENAME=="cost.txt" {
costs[]=
next
}
FILENAME=="heads.txt" {
f()
}
function f(node,
path,cost,sum,prev,sep1,sep2,i) {
if(node in prev)
# cycle detected
return
path=path sep1 node
cost=cost sep2 costs[node]
sum+=costs[node]
if(!count[node]) {
print path,cost,sum
}
else {
prev[node]
for(i=1;i<=count[node];++i)
f(edges[node,i],path,cost,sum,prev,"->","+")
delete prev[node]
}
}
在 heads.txt 之前读取 connections.txt 和 cost.txt。
它的输出（填充）：
$ awk -f tst.awk connections.txt cost.txt heads.txt
str1->str2->str3->str4 1+5+10+548 564
str100->str2->str3->str4 57+5+10+548 620
str100->str101->str102 57+39+23 119
你说你只需要标准工具，但你也提到在你的数据上使用 dot，所以我假设你有其他可用的 graphviz 实用程序......特别是，gvpr ，类似于图表的 awk：
#!/usr/bin/env bash
graph=$(mktemp)
join -t$'\t' -j1 -o 0,1.2,2.2 -a2 \
<(sort -k1,1 connections.txt) \
<(sort -k1,1 cost.txt) |
awk -F$'\t' 'BEGIN { print "digraph g {" }
{ printf "%s [cost = %d ]\n", ,
if ( != "") printf "%s -> %s\n", , }
END { print "}" }' > "$graph"
while read root; do
gvpr -a "$root" '
BEGIN {
int depth;
int seen[string];
string path[int];
int costs[int];
}
BEG_G {
$tvtype = TV_prepostfwd;
$tvroot = node($, ARGV[0]);
}
N {
if ($.name in seen) {
depth--;
} else {
seen[$.name] = 1;
path[depth] = $.name;
costs[depth] = $.cost;
depth++;
if (!fstout($) && path[0] == ARGV[0]) {
int i, c = 0;
for (i = 0; i < depth - 1; i++) {
printf("%s->", path[i]);
}
printf("%s\t", $.name);
for (i = 0; i < depth - 1; i++) {
c += costs[i];
printf("%d+", costs[i]);
}
c += $.cost;
printf("%d\t%d\n", $.cost, c);
}
}
}' "$graph"
done < heads.txt
rm -f "$graph"
运行 创建数据文件后：
$ ./paths.sh
str1->str2->str3->str4 1+5+10+548 564
str100->str2->str3->str4 57+5+10+548 620
str100->str101->str102 57+39+23 119
或者，由于它无处不在，它也可能是标准的，基于 sqlite 的解决方案。与上面的不同，这个甚至不需要 bash/zsh/ksh93。
$ sqlite3 -batch -noheader -list <<EOF
.separator "\t"
CREATE TABLE heads(node TEXT);
.import heads.txt heads
CREATE TABLE costs(node TEXT PRIMARY KEY, cost INTEGER) WITHOUT ROWID;
.import cost.txt costs
CREATE TABLE connections(from_node TEXT, to_node TEXT
, PRIMARY KEY(from_node, to_node)) WITHOUT ROWID;
.import connections.txt connections
WITH RECURSIVE paths(tail, path, costs, cost) AS
(SELECT h.node, h.node, c.cost, c.cost
FROM heads AS h
JOIN costs AS c ON h.node = c.node
UNION ALL
SELECT conn.to_node, p.path || '->' || conn.to_node
, p.costs || '+' || c.cost, p.cost + c.cost
FROM paths AS p
JOIN connections AS conn ON conn.from_node = p.tail
JOIN costs AS c ON c.node = conn.to_node
)
SELECT path, costs, cost FROM paths AS p
WHERE tail NOT IN (SELECT from_node FROM connections)
ORDER BY path;
EOF
str1->str2->str3->str4 1+5+10+548 564
str100->str101->str102 57+39+23 119
str100->str2->str3->str4 57+5+10+548 620