如何比较 bash 中的 2 个范围列表？
How to compare 2 lists of ranges in bash?
使用 bash 脚本 (Ubuntu 16.04)，我正在尝试比较 2 个范围列表：file1 中任何范围内的任何数字是否与 file1 中任何范围内的任何数字一致文件 2 中的范围？如果是这样，打印第二个文件中的行。在这里，我将每个范围作为 2 个制表符分隔的列（在文件 1 中，第 1 行表示范围 1-4，即 1、2、3、4）。真正的文件是相当大的。
文件 1:
1 4
5 7
8 11
12 15
文件 2:
3 4
8 13
20 24
期望的输出：
3 4
8 13
我最好的尝试是：
awk 'NR=FNR { x[] = +0; y[] = +0; next};
{for (i in x) {if (x[i] > +0); then
{for (i in y) {if (y[i] <+0); then
{print , }}}}}' file1 file2 > output.txt
此 returns 一个空文件。
我认为脚本需要使用 if-then 条件进行范围比较，并遍历两个文件中的每一行。我找到了每个概念的示例，但无法弄清楚如何将它们组合起来。
感谢任何帮助！
当然，这取决于您的文件有多大。如果它们不够大，无法耗尽内存，您可以试试这个 100% bash 解决方案：
declare -a min=() # array of lower bounds of ranges
declare -a max=() # array of upper bounds of ranges
# read ranges in second file, store then in arrays min and max
while read a b; do
min+=( "$a" );
max+=( "$b" );
done < file2
# read ranges in first file
while read a b; do
# loop over indexes of min (and max) array
for i in "${!min[@]}"; do
if (( max[i] >= a && min[i] <= b )); then # if ranges overlap
echo "${min[i]} ${max[i]}" # print range
unset min[i] max[i] # performance optimization
fi
done
done < file1
这只是一个起点。有许多可能的性能/内存占用改进。但它们在很大程度上取决于文件的大小和范围的分布。
编辑 1：改进了范围重叠测试。
编辑 2：重新使用了 RomanPerekhrest 提出的优秀优化（未设置已打印的范围 file2）。当范围重叠的概率高时，性能应该更好。
编辑 3：与 RomanPerekhrest 提出的 awk 版本的性能比较（修复最初的小错误后）：awk 在 10 到 20 之间在这个问题上比 bash 快 1 倍。如果性能很重要，而您在 awk 和 bash 之间犹豫不决，则首选：
awk 'NR == FNR { a[FNR] = ; b[FNR] = ; next; }
{ for (i in a)
if ( <= b[i] && a[i] <= ) {
print a[i], b[i]; delete a[i]; delete b[i];
}
}' file2 file1
awk 'FNR == 1 && NR == 1 { file=1 } FNR == 1 && NR != 1 { file=2 } file ==1 { for (q=1;q<=NF;q++) { nums[$q]=[=10=]} } file == 2 { for ( p=1;p<=NF;p++) { for (i in nums) { if (i == $p) { print [=10=] } } } }' file1 file2
细分：
FNR == 1 && NR == 1 {
file=1
}
FNR == 1 && NR != 1 {
file=2
}
file == 1 {
for (q=1;q<=NF;q++) {
nums[$q]=[=11=]
}
}
file == 2 {
for ( p=1;p<=NF;p++) {
for (i in nums) {
if (i == $p) {
print [=11=]
}
}
}
}
基本上我们在处理第一个文件时设置file = 1，在处理第二个文件时设置file = 2。当我们在第一个文件中时，将该行读入以该行的每个字段为键的数组中。当我们在第二个文件中时，处理数组 (nums) 并检查该行的每个字段是否有一个条目。如果有，打印出来。
awk 解决办法：
awk 'NR==FNR{ a[]=; next }
{ for(i in a)
if ((>=i+0 && <=a[i]) || (<=a[i] && >=i+0)) {
print i,a[i]; delete a[i];
}
}' file2 file1
输出：
3 4
8 13
对于 GNU awk，因为我正在控制 for 扫描顺序以优化时间：
$ cat program.awk
BEGIN {
PROCINFO["sorted_in"]="@ind_num_desc"
}
NR==FNR { # hash file1 to a
if(( in a==0) || <a[]) # avoid collisions
a[]=
next
}
{
for(i in a) { # in desc order
# print "DEBUG: For:",[=10=] ":", a[i], i # remove # for debug
if(i+0>) { # next after
if(<=i+0 && a[i]<=) {
print
next
}
}
else
next
}
}
测试数据：
$ cat file1
0 3 # testing for completely overlapping ranges
1 4
5 7
8 11
12 15
$ cat file2
1 2 # testing for completely overlapping ranges
3 4
8 13
20 24
输出：
$ awk -f program.awk file1 file2
1 2
3 4
8 13
和
$ awk -f program.awk file2 file1
0 3
1 4
8 11
12 15
如果首选 Perl 解决方案，那么下面一行就可以了
/tmp> cat marla1.txt
1 4
5 7
8 11
12 15
/tmp> cat marla2.txt
3 4
8 13
20 24
/tmp> perl -lane ' BEGIN { %kv=map{split(/\s+/)} qx(cat marla2.txt) } { foreach(keys %kv) { if($F[0]==$_ or $F[1]==$kv{$_}) { print "$_ $kv{$_}" }} } ' marla1.txt
3 4
8 13
/tmp>
如果范围根据其下限排序，我们可以使用它来提高算法的效率。这个想法是交替处理 file1 和 file2 中的范围。更准确地说，当我们在 file2 中有一个特定范围 R 时，我们在 file1 中采取越来越远的范围，直到我们知道这些范围是否与 [=19= 重叠]R。一旦我们知道这一点，我们就切换到 file2.
中的下一个范围
#!/bin/bash
exec 3< "" # file whose ranges are checked for overlap with those ...
exec 4< "" # ... from this file, and if so, are written to stdout
l4=-1 # lower bound of current range from file 2
u4=-1 # upper bound
# initialized with -1 so the first range is read on the first iteration
echo "Ranges in that intersect any ranges in :"
while read l3 u3; do # read next range from file 1
if (( u4 >= l3 )); then
(( l4 <= u3 )) && echo "$l3 $u3"
else # the upper bound from file 2 is below the lower bound from file 1, so ...
while read l4 u4; do # ... we read further ranges from file 2 until ...
if (( u4 >= l3 )); then # ... their upper bound is high enough
(( l4 <= u3 )) && echo "$l3 $u3"
break
fi
done <&4
fi
done <&3
脚本可以用./script.sh file2 file1
调用
使用 bash 脚本 (Ubuntu 16.04)，我正在尝试比较 2 个范围列表：file1 中任何范围内的任何数字是否与 file1 中任何范围内的任何数字一致文件 2 中的范围？如果是这样，打印第二个文件中的行。在这里，我将每个范围作为 2 个制表符分隔的列（在文件 1 中，第 1 行表示范围 1-4，即 1、2、3、4）。真正的文件是相当大的。
文件 1:
1 4
5 7
8 11
12 15
文件 2:
3 4
8 13
20 24
期望的输出：
3 4
8 13
我最好的尝试是：
awk 'NR=FNR { x[] = +0; y[] = +0; next};
{for (i in x) {if (x[i] > +0); then
{for (i in y) {if (y[i] <+0); then
{print , }}}}}' file1 file2 > output.txt
此 returns 一个空文件。
我认为脚本需要使用 if-then 条件进行范围比较，并遍历两个文件中的每一行。我找到了每个概念的示例，但无法弄清楚如何将它们组合起来。
感谢任何帮助！
当然，这取决于您的文件有多大。如果它们不够大，无法耗尽内存，您可以试试这个 100% bash 解决方案：
declare -a min=() # array of lower bounds of ranges
declare -a max=() # array of upper bounds of ranges
# read ranges in second file, store then in arrays min and max
while read a b; do
min+=( "$a" );
max+=( "$b" );
done < file2
# read ranges in first file
while read a b; do
# loop over indexes of min (and max) array
for i in "${!min[@]}"; do
if (( max[i] >= a && min[i] <= b )); then # if ranges overlap
echo "${min[i]} ${max[i]}" # print range
unset min[i] max[i] # performance optimization
fi
done
done < file1
这只是一个起点。有许多可能的性能/内存占用改进。但它们在很大程度上取决于文件的大小和范围的分布。
编辑 1：改进了范围重叠测试。
编辑 2：重新使用了 RomanPerekhrest 提出的优秀优化（未设置已打印的范围 file2）。当范围重叠的概率高时，性能应该更好。
编辑 3：与 RomanPerekhrest 提出的 awk 版本的性能比较（修复最初的小错误后）：awk 在 10 到 20 之间在这个问题上比 bash 快 1 倍。如果性能很重要，而您在 awk 和 bash 之间犹豫不决，则首选：
awk 'NR == FNR { a[FNR] = ; b[FNR] = ; next; }
{ for (i in a)
if ( <= b[i] && a[i] <= ) {
print a[i], b[i]; delete a[i]; delete b[i];
}
}' file2 file1
awk 'FNR == 1 && NR == 1 { file=1 } FNR == 1 && NR != 1 { file=2 } file ==1 { for (q=1;q<=NF;q++) { nums[$q]=[=10=]} } file == 2 { for ( p=1;p<=NF;p++) { for (i in nums) { if (i == $p) { print [=10=] } } } }' file1 file2
细分：
FNR == 1 && NR == 1 {
file=1
}
FNR == 1 && NR != 1 {
file=2
}
file == 1 {
for (q=1;q<=NF;q++) {
nums[$q]=[=11=]
}
}
file == 2 {
for ( p=1;p<=NF;p++) {
for (i in nums) {
if (i == $p) {
print [=11=]
}
}
}
}
基本上我们在处理第一个文件时设置file = 1，在处理第二个文件时设置file = 2。当我们在第一个文件中时，将该行读入以该行的每个字段为键的数组中。当我们在第二个文件中时，处理数组 (nums) 并检查该行的每个字段是否有一个条目。如果有，打印出来。
awk 解决办法：
awk 'NR==FNR{ a[]=; next }
{ for(i in a)
if ((>=i+0 && <=a[i]) || (<=a[i] && >=i+0)) {
print i,a[i]; delete a[i];
}
}' file2 file1
输出：
3 4
8 13
对于 GNU awk，因为我正在控制 for 扫描顺序以优化时间：
$ cat program.awk
BEGIN {
PROCINFO["sorted_in"]="@ind_num_desc"
}
NR==FNR { # hash file1 to a
if(( in a==0) || <a[]) # avoid collisions
a[]=
next
}
{
for(i in a) { # in desc order
# print "DEBUG: For:",[=10=] ":", a[i], i # remove # for debug
if(i+0>) { # next after
if(<=i+0 && a[i]<=) {
print
next
}
}
else
next
}
}
测试数据：
$ cat file1
0 3 # testing for completely overlapping ranges
1 4
5 7
8 11
12 15
$ cat file2
1 2 # testing for completely overlapping ranges
3 4
8 13
20 24
输出：
$ awk -f program.awk file1 file2
1 2
3 4
8 13
和
$ awk -f program.awk file2 file1
0 3
1 4
8 11
12 15
如果首选 Perl 解决方案，那么下面一行就可以了
/tmp> cat marla1.txt
1 4
5 7
8 11
12 15
/tmp> cat marla2.txt
3 4
8 13
20 24
/tmp> perl -lane ' BEGIN { %kv=map{split(/\s+/)} qx(cat marla2.txt) } { foreach(keys %kv) { if($F[0]==$_ or $F[1]==$kv{$_}) { print "$_ $kv{$_}" }} } ' marla1.txt
3 4
8 13
/tmp>
如果范围根据其下限排序，我们可以使用它来提高算法的效率。这个想法是交替处理 file1 和 file2 中的范围。更准确地说，当我们在 file2 中有一个特定范围 R 时，我们在 file1 中采取越来越远的范围，直到我们知道这些范围是否与 [=19= 重叠]R。一旦我们知道这一点，我们就切换到 file2.
#!/bin/bash
exec 3< "" # file whose ranges are checked for overlap with those ...
exec 4< "" # ... from this file, and if so, are written to stdout
l4=-1 # lower bound of current range from file 2
u4=-1 # upper bound
# initialized with -1 so the first range is read on the first iteration
echo "Ranges in that intersect any ranges in :"
while read l3 u3; do # read next range from file 1
if (( u4 >= l3 )); then
(( l4 <= u3 )) && echo "$l3 $u3"
else # the upper bound from file 2 is below the lower bound from file 1, so ...
while read l4 u4; do # ... we read further ranges from file 2 until ...
if (( u4 >= l3 )); then # ... their upper bound is high enough
(( l4 <= u3 )) && echo "$l3 $u3"
break
fi
done <&4
fi
done <&3
脚本可以用./script.sh file2 file1