0

フォームの各行を含む大きなファイルがあります

a b c

次のような別の行が存在しないような行をすべて削除したいと思います

b d e

またd a e

とabs(c - e) < 10。

a、b、c、dはeすべて整数です。

たとえば、入力が次の場合:

0 1 10 
1 2 20
2 3 25
0 1 15 
1 4 40

出力は次のようになります

1 2 20
2 3 25
0 1 15

線形時間のようなものでこれを行うことは可能ですか?

1 つのアイデアは、並べ替えられたリストの 2 つの辞書を作成することです。最初の列の値に関連付けられた 3 番目の列の値の 1 つ。もう 1 つは、2 番目の列の値に関連付けられた 3 番目の列の値です。次に、abcが表示されたら、2番目の辞書のキーaを使用して取得したソート済みリストでcを検索し、最初の辞書のキーbを使用して取得したソート済みリストでcを検索します。

4

3 に答える 3

3

これが線形時間で実行できるかどうかはわかりません。入力に ​​n 個のトリプレットがある場合、O(n·log n) 時間でそれを行うのは簡単です。以下は、必ずしも好ましいとは限らない実装形式のメソッドのスケッチです。

  1. マーカー M の配列を作成します。最初はすべてクリアです。

  2. 配列を作成し、入力のコピーを作成します。最初に中央の要素で並べ替え、次に中央の要素が等しい場合は 3 番目の要素で並べ替えます。(ここまでの時間はO(n・log n)です。)

  3. 中間値ごとに、key = 3 番目の要素で BST (二分探索木) を作成します。(時間はまたO(n・log n)です。)

  4. 適切な BST を指すデータを使用して、中間値をキーとするハッシュ テーブルを作成します。つまり、中間値 y と 3 番目の要素 z が与えられると、時間 O(1) で、中間値が y であるトリプレットの BST に到達できます。それから、時間内に O(log n) は、z に最も近い 3 番目の要素の値を持つトリプレットを見つけることができます。

  5. 各トリプレット t = (x,y,z) に対して、マーカーがまだ設定されていない場合は、ハッシュ テーブルを使用して、x に対応する BST を見つけます (存在する場合)。その BST で、z に最も近い 3 番目の要素を持つトリプレット u を見つけます。差が 10 未満の場合は、t と u のマーカーを設定します。(時間はまたO(n・log n)です。)

  6. 手順 2 ～ 5 を繰り返しますが、BST は中間値ではなく最初の要素の値に基づいており、手順 5 のルックアップは x ではなく y に基づいています。(一致関係は対称的であるため、ステップ 5 の各サイクルで 2 つのマーカーを設定できますが、一部の適格なトリプレットはマークされない場合があります。つまり、それらは許容範囲内にありますが、見つかった最も近い一致よりも離れています。ステップ 5 ですべての適格なトリプレットをマークすることは可能ですが、最悪の場合の時間が O(n・log n) から O(n²・log n) に増加します。)

  7. 設定されているマーカーごとに、対応するトリプレットを出力します。

総時間：O(n・log n)。BST を構築せずに、ソートされた配列の部分範囲内でバイナリ検索を使用することで、同じ時間を達成できます。

編集: Python では、ipython インタープリター セッションからの抜粋で以下に示すように、bisectで使用可能な構造を構築できます。(これらのステップを実行するためのより効率的な方法があるかもしれません。) 辞書の各データ項目hは、 での検索に適した配列bisectです。

In [1]: from itertools import groupby

In [2]: a=[(0,1,10), (1,2,20), (2,3,25), (0,1,15), (1,4,40), (1,4,33), (3,3,17), (2,1,19)]

In [3]: b=sorted((e[1],e[2],i) for i,e in enumerate(a)); print b
[(1, 10, 0), (1, 15, 3), (1, 19, 7), (2, 20, 1), (3, 17, 6), (3, 25, 2), (4, 33, 5), (4, 40, 4)]

In [4]: h={k:list(g) for k,g in groupby(b,lambda x: x[0])}; h
Out[4]: 
{1: [(1, 10, 0), (1, 15, 3), (1, 19, 7)],
 2: [(2, 20, 1)],
 3: [(3, 17, 6), (3, 25, 2)],
 4: [(4, 33, 5), (4, 40, 4)]}
于 2013-07-23T16:39:35.213 に答える
0

あなたが探しているのは次のようなものだと思います

set lines
for line in infile:
  if line not in lines:
    lines.add(line)
    outfile.write(line)
于 2013-07-23T16:02:14.457 に答える