3

このような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

どうすればこれを入手できますか？

4

1 に答える 1

5

それが制限されている場合は、bash スクリプトでこれを行うことができますが、Python / C++ / Java でこのような問題を処理する方が簡単です。スクリプトで実行されている場合は各行を繰り返し読むか、多くのヘルパー変数を使用します)

==> 両方の列の値がソートされて増加していると仮定できる場合、単純な解決策は次のようになります。

2 列目のすべての値について:

  • col2_value - col1_value の差が負から正になるまで、1 列目の値を順番に読み取ります。
  • 次に、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 であるため、大規模なデータセットの場合、マッチングに近似グラフ アルゴリズムの 1 つを使用するのが最善の方法です。

于 2012-10-12T17:29:50.367 に答える