0

次のようなファイルがあります。

0.000000
0.000051
0.000076
0.000102
0.000152
0.000178
0.000203
0.000229
0.000254
0.000279
0.000305
0.000356
0.000381
0.000406

そして、2 つの数値とその最も近い距離を見つけたいと思います。シェルスクリプトを使用しています。当時、私は：

points.dat cat | cut-f1 | sort | uniq

次のケースでは、2 つの列を検討したいと思います。x 軸の列と y 軸の列も同様です。これは、最も近い点のペアの問題のようなものです。私もそのお手伝いがしたいです。

助けてくれてありがとう！

4

2 に答える 2

2

これはコメントではなく回答です。

アルゴリズムをチェックするときは、この出力を使用してください。

Python コード:

import itertools

data = [
0.000000, #data[0]
0.000051, #data[1]
0.000076, #data[2]
0.000102, #data[3]
0.000152, #data[4]
0.000178, #data[5]
0.000203, #data[6]
0.000229, #data[7]
0.000254, #data[8]
0.000279, #data[9]
0.000305, #data[10]
0.000356, #data[11]
0.000381, #data[12]
0.000406  #data[13]
]

for j in sorted((abs(i[0][0]-i[1][0]), (i[0][1],i[1][1])) for i in itertools.combinations( zip(data,range(len(data))), 2)):
    print str(j[1]).ljust(8), '->',j[0]#indices -> distance

出力：

(7, 8)   -> 2.5e-05
(1, 2)   -> 2.5e-05
(5, 6)   -> 2.5e-05
(8, 9)   -> 2.5e-05
(11, 12) -> 2.5e-05
(12, 13) -> 2.5e-05
(4, 5)   -> 2.6e-05
(9, 10)  -> 2.6e-05
(2, 3)   -> 2.6e-05
(6, 7)   -> 2.6e-05
(7, 9)   -> 5e-05
(3, 4)   -> 5e-05
(11, 13) -> 5e-05
(4, 6)   -> 5.1e-05
(6, 8)   -> 5.1e-05
(8, 10)  -> 5.1e-05
(10, 11) -> 5.1e-05
(0, 1)   -> 5.1e-05
(1, 3)   -> 5.1e-05
(5, 7)   -> 5.1e-05
(7, 10)  -> 7.6e-05
(3, 5)   -> 7.6e-05
(0, 2)   -> 7.6e-05
(2, 4)   -> 7.6e-05
(5, 8)   -> 7.6e-05
(6, 9)   -> 7.6e-05
(10, 12) -> 7.6e-05
(9, 11)  -> 7.7e-05
(4, 7)   -> 7.7e-05
(3, 6)   -> 0.000101
(1, 4)   -> 0.000101
(5, 9)   -> 0.000101
(10, 13) -> 0.000101
(2, 5)   -> 0.000102
(4, 8)   -> 0.000102
(6, 10)  -> 0.000102
(8, 11)  -> 0.000102
(9, 12)  -> 0.000102
(0, 3)   -> 0.000102
(7, 11)  -> 0.000127
(1, 5)   -> 0.000127
(2, 6)   -> 0.000127
(3, 7)   -> 0.000127
(4, 9)   -> 0.000127
(5, 10)  -> 0.000127
(8, 12)  -> 0.000127
(9, 13)  -> 0.000127
(7, 12)  -> 0.000152
(0, 4)   -> 0.000152
(1, 6)   -> 0.000152
(3, 8)   -> 0.000152
(8, 13)  -> 0.000152
(4, 10)  -> 0.000153
(6, 11)  -> 0.000153
(2, 7)   -> 0.000153
(7, 13)  -> 0.000177
(3, 9)   -> 0.000177
(0, 5)   -> 0.000178
(2, 8)   -> 0.000178
(5, 11)  -> 0.000178
(6, 12)  -> 0.000178
(1, 7)   -> 0.000178
(0, 6)   -> 0.000203
(1, 8)   -> 0.000203
(2, 9)   -> 0.000203
(3, 10)  -> 0.000203
(5, 12)  -> 0.000203
(6, 13)  -> 0.000203
(4, 11)  -> 0.000204
(1, 9)   -> 0.000228
(5, 13)  -> 0.000228
(2, 10)  -> 0.000229
(4, 12)  -> 0.000229
(0, 7)   -> 0.000229
(0, 8)   -> 0.000254
(1, 10)  -> 0.000254
(3, 11)  -> 0.000254
(4, 13)  -> 0.000254
(0, 9)   -> 0.000279
(3, 12)  -> 0.000279
(2, 11)  -> 0.00028
(3, 13)  -> 0.000304
(0, 10)  -> 0.000305
(1, 11)  -> 0.000305
(2, 12)  -> 0.000305
(1, 12)  -> 0.00033
(2, 13)  -> 0.00033
(1, 13)  -> 0.000355
(0, 11)  -> 0.000356
(0, 12)  -> 0.000381
(0, 13)  -> 0.000406

したがって、最小のセットは (data[7], data[8]) です。

出力から、calc の前にデータを並べ替えると、次のように最小距離を簡単に見つけることができます。

#This is pseudocode.
x[n] = data[n] - data[n-1]
min(x)
于 2014-04-24T00:49:26.807 に答える
1

現在の入力ファイルによると、これは最も近い距離を計算します。

sort -u points.dat \
| xargs -n2 -J{} echo {} "- _1 * p" \
| dc \
| sort -u \
| sed '1!d;s/^\./0./'

より正確な回答を得るには、最終的な入力ファイルを投稿する必要があります。

編集: まあ、これはより正確な距離になります:

sort -n -u points.dat \
| sed '1!p' \
| paste - - \
| head -n-1 \
| xargs -n2 -I{} echo {} "- _1 * p" \
| dc \
| sort -n -u \
| sed '1!d;s/^\./0./'
于 2014-04-24T18:21:07.180 に答える