3

我有一个文件说 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

我怎样才能得到这个？

4

1 回答 1

5

如果这是您的限制，则可以使用 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，因此对于大型数据集，您可能做的最好的事情就是使用一种近似图形算法进行匹配。

于 2012-10-12T17:29:50.367 回答