如何在bash中选择值的子集

Question

我有一个文件说input.dat像这样

column1 column2
 0       0
 1.3     1.6
 1.8     2.1
 2.0      
 2.6

我需要从第1列中提取最接近第2列的值的子集,以便两列中的条目总数相等.在这个例子中,我需要获得输出

column1 column2
0      0 
1.8    1.6
2.0    2.1

我怎么能得到这个？

Answer 1

使用bash脚本可以做到这一点,如果这是你的限制,但用Python/C++/Java处理这样的问题会更容易,因为这是优化的二分匹配问题的一个版本(你必须如果在脚本中完成,则重复读取每一行,或使用大量辅助变量)

==>如果我们可以假设两列中的值都已排序和增加,那么一个天真的解决方案是:

对于第2列中的每个值:

• 按顺序读取第1列中的值,直到col2_value - col1_value的差值从负值变为正值
• 然后找到min(abs(negative_difference),positive_difference)并选择对应于较小差异的col1_value
• 从col1和col2中删除这两个条目,并将它们添加到结果表中
• 重复此过程,直到原始表的col2中没有任何内容

这是m*n的最坏情况运行时间,其中m是col1中的#个条目,n是col2中的#个条目,如果你聪明的话,则是O(n)的平均运行时间并且进行恒定时间交替检查(比较-1) ,从最后选择的col1_value的索引+1,因为-2,+ 2等当然会导致更大的差异)而不是顺序的,以找到col2中的当前值和vol1中的值之间的最小差异.

这是一个天真的解决方案,因为它不会最小化系统中的整体差异.最佳解决方案是NP,因此对于大型数据集,您可能做的最好的是使用一种近似图形算法进行匹配.