linux - 如何比较bash中的2个范围列表？

Question

使用 bash 脚本(Ubuntu 16.04)，我正在尝试比较 2 个范围列表:file1 中任何范围内的任何数字是否与 file2 中任何范围内的任何数字一致？如果是这样，打印第二个文件中的行。在这里，我将每个范围作为 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[$1] = $1+0; y[$2] = $2+0; next}; 
{for (i in x) {if (x[i] > $1+0); then
{for (i in y) {if (y[i] <$2+0); then            
{print $1, $2}}}}}' file1 file2 > output.txt

这将返回一个空文件。

我认为脚本需要使用 if-then 条件进行范围比较，并遍历两个文件中的每一行。我找到了每个概念的示例，但无法弄清楚如何将它们组合起来。

感谢任何帮助!

Answer 1

当然，这取决于您的文件有多大。如果它们不够大，无法耗尽内存，您可以尝试这个 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:改进了范围重叠测试。

EDIT 2:重用了 RomanPerekhrest 提出的出色优化(未设置 file2 中已打印的范围)。当范围重叠的可能性很高时，性能应该更好。

编辑 3:与 RomanPerekhrest 提出的 awk 版本的性能比较(修复了最初的小错误后):awk 介于 10 和在这个问题上比 bash 快 20 倍。如果性能很重要，而您在 awk 和 bash 之间犹豫不决，则首选:

awk 'NR == FNR { a[FNR] = $1; b[FNR] = $2; next; }
    { for (i in a)
          if ($1 <= b[i] && a[i] <= $2) {
              print a[i], b[i]; delete a[i]; delete b[i];
          } 
    }' file2 file1