bash - 如何在bash中选择值的子集

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

column1 column2
 0       0
 1.3     1.6
 1.8     2.1
 2.0
 2.6

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

column1 column2
0      0
1.8    1.6
2.0    2.1

我怎样才能得到这个？

最佳答案

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

==> 如果我们可以假设两列中的值都已排序并递增，那么简单的解决方案是:

对于第二列中的每个值:

依次读取第一列中的值，直到 col2_value - col1_value 的差值从负变为正

然后找到 min( abs(negative_difference), positive_difference ) 并选择对应于较小差异的 col1_value

从 col1 和 col2 中删除两个条目并将它们添加到结果表

重复这个过程，直到原表的 col2 中没有剩余

这有 m*n 的最坏情况运行时间，其中 m 是 col1 中的 # 个条目，n 是 col2 中的 # 个条目，平均运行时间为 O(n) 如果您很聪明并进行恒定时间交替检查(比较 -1 , +1 从最后选择的 col1_value 的索引开始，因为 -2、+2 等当然会导致更大的差异)而不是连续的，以找到 col2 中的当前值与 vol1 中的值之间的最小差异。

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

关于bash - 如何在bash中选择值的子集，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12863767/