如何在bash選擇值的子集

Question

我有一個文件說input.dat這樣

column1 column2 
0  0 
1.3  1.6 
1.8  2.1 
2.0  
2.6 

我需要提取從第一列的值，這是最接近於那些在列2的子集，使兩列中的條目總數相等。 在這個例子中，我需要的輸出，以獲得

column1 column2 
0  0 
1.8 1.6 
2.0 2.1 

如何我能得到這個？

Answer 1

如果這是你所限制的，可以用bash腳本來做到這一點，但用Python/C++/Java來處理這樣的問題會更容易，因爲這是一個優化的雙方匹配問題的版本（你如果我們可以假設兩列中的值都被排序並且增加，那麼一個天真的解決方案將是：

對於第二列中的每個值：

• 閱讀過第1列順序值，直到col2_value的差 - col1_value從負變爲正
• 然後找到分鐘（ABS（negative_difference），positive_difference）並選取一個對應於更小的差
• 同時刪除col1_value從COL1和COL2並將它們添加到結果表
• 重複此過程項，直至有留在原表

這最壞情況下的運行m * n個的時間，其中m爲COL2什麼col1和n中的＃個條目是col2中的＃個條目，如果你很聰明，則平均運行時間爲O（n），並執行一個常數tim交替檢查（比較最後選擇的col1_value的索引-1，+1，因爲-2，+2等等當然會導致更大的差異）而不是順序檢查，以找出col2中的當前值與vol1中的值。

這是一個天真的解決方案，因爲它不會最小化系統的整體差異。最佳解決方案是NP，因此對於大型數據集，最好的做法是使用近似圖形算法之一進行匹配。