2

数値が特定の範囲内にあるかどうかを確認する必要がある問題に取り組んでいます。ただし、私が扱っているファイルには数十万行あるため、問題は複雑です。

以下では、できるだけ簡単な言葉で問題を説明しようとしています。

ここに私の入力ファイルの簡単な説明があります:

ファイルRanges.txtには、最小値と最大値がタブで区切られた範囲がいくつかあります。

10 20
30 40
60 70

これには、範囲を含む約 10,000,000 行を含めることができます。

注:範囲が重複することはありません。

ファイルNumbers.txtには、数字のリストと、各数字に関連付けられたいくつかの値が含まれています。

12 0.34
22 0.14
34 0.79
37 0.87

等々。繰り返しますが、数十万のそのような行とそれに関連付けられた値があります。

私がやりたいことは、 Numbers.txt からすべての数値を取得し、それがRanges.txtのいずれかの範囲内にあるかどうかを確認することです。

範囲内にあるそのようなすべての数値について、関連する値の平均 (つまり、範囲ごとの平均) を取得する必要があります。

たとえば。上記のNumbers.txtの例では、 Ranges.txtの範囲 30-40 に含まれる 34 と 37 の 2 つの数値があるため、範囲 30-40 については、関連する 34 と 37 の値の平均を計算する必要があります。 . (つまり、0.79 と 0.87 の平均)、つまり 0.82

最終的な出力ファイルはRanges.txtである必要がありますが、すべての数値の関連値の平均が各範囲内にあります。何かのようなもの ：

出力.txt

10 20 <mean>
30 40 0.82
60 70 <mean>

等々。

これをPythonで効率的に書く方法についての助けとアイデアをいただければ幸いです。

4

3 に答える 3

4

明らかに、Numbers.txt の各行を Ranges.txt の各行に対して実行する必要があります。

Numbers.txt を反復処理し、各行について Ranges.txt を反復処理することができます。しかし、これにはとてつもなく時間がかかり、Ranges.txt ファイル全体を何百万回も読み取ることになります。

両方をメモリに読み込むこともできますが、それには多くのストレージが必要であり、両方のファイルの読み込みと前処理が完了するまで処理を行うことができません。

つまり、Ranges.txt を一度メモリに読み込んで、代わりに int のペアのリストとして保存しますが、Numbers.txt を遅延して読み取り、各数値のリストを反復処理します。

このようなことはしょっちゅう出てきます。一般に、より大きなコレクションを外側のループに入れ、可能な限り遅延させたいと考えていますが、小さなコレクションは内側のループに入り、可能な限り高速にするために前処理されます。しかし、より大きなコレクションをより効率的に前処理できる場合 (そして、それを格納するのに十分なメモリがある場合) は、それを逆にします。

前処理について言えば、単に int のペアのリストを読み取るよりもはるかに優れた処理を行うことができます。Ranges.txt を並べ替えた場合、各範囲を徹底的にチェックする (100000 ステップ) のではなく、2 等分することなく最も近い範囲を見つけて、それをチェックする (18 ステップ) ことができます。

を使用するとオフバイワンエラーが発生しやすいため、これは stdlib では少し面倒ですが、簡単にするためbisectの ActiveState レシピがたくさんあります (公式ドキュメントからリンクされたものを含む)。blistまたはのようなパーティモジュールbintreesは、シンプルな OO インターフェイスでソートされたコレクションを提供します。

したがって、この擬似コードのようなもの:

with open('ranges.txt') as f:
    ranges = sorted([map(int, line.split()) for line in f])
range_values = {}
with open('numbers.txt') as f:
    rows = (map(int, line.split()) for line in f)
    for number, value in rows:
        use the sorted ranges to find the appropriate range (if any)
        range_values.setdefault(range, []).append(value)
with open('output.txt') as f:
    for r, values in range_values.items():
        mean = sum(values) / len(values)
        f.write('{} {} {}\n'.format(r[0], r[1], mean))

ちなみに、構文解析がsplit各行で呼び出すだけよりも複雑であることが判明した場合は、csvモジュールを使用することをお勧めします...しかし、ここでは問題にならないようです。

Ranges.txt をメモリに収めることができないが、Numbers.txt を収めることができる場合はどうなるでしょうか。それを並べ替えてから、Ranges.txt を反復処理し、並べ替えられた数値に一致するものをすべて見つけて、その範囲の結果を書き出すことができます。

bisect_left と bisect_right の間のすべてを繰り返す必要があるため、これはもう少し複雑です。しかし、それがより困難な唯一の方法です。(ここでは、サードパーティ クラスがさらに役立ちます。たとえば、bintrees.FastRBTree並べ替えられたコレクションとして a を使用すると、それは単にsorted_number_tree[low:high].)

範囲がオーバーラップする可能性がある場合は、もう少し賢くする必要があります。開始点を超えずに最も近い範囲を見つけ、最後を超えずに最も近い範囲を見つけ、その間のすべてをチェックする必要があります。しかし、主なトリックは、最後のバージョンで使用されたものとまったく同じです。他の唯一のトリックは、範囲の 2 つのコピーを保持することです。1 つは開始値でソートされ、もう 1 つは終了値でソートされます。そのうちの 1 つは単なるリストではなく、もう 1 つのインデックスへのマップである必要があります。

于 2013-09-25T00:05:11.843 に答える
1

両方のファイルのデータは既にソートされているようです。そうでない場合は、まず外部ツールまたは Python を使用して並べ替えます。

次に、2 つのファイルを並行して処理できます。ファイルから数値を読み取り、Numbers.txtそれがファイル内の範囲内にあるかどうかを確認し、Ranges.txtその質問に答えるために必要な数の行をそのファイルから読み取ります。次に、 から次の番号を読み取り、Numbers.txt繰り返します。アイデアは、2 つの並べ替えられた配列をマージすることに似ており、O(n+m)時間内nに実行する必要mがあり、ファイルのサイズです。ファイルを並べ替える必要がある場合、実行時間はO(n lg(n) + m lg(m)). これを実装するために私が書いた簡単なプログラムを次に示します。

import sys
from collections import Counter

class Gen(object):
    __slots__ = ('rfp', 'nfp', 'mn', 'mx', 'num', 'd', 'n')
    def __init__(self, ranges_filename, numbers_filename):
        self.d = Counter() # sum of elements keyed by range
        self.n = Counter() # number of elements keyed by range 

        self.rfp = open(ranges_filename)
        self.nfp = open(numbers_filename)
        # Read the first number and the first range values
        self.num = float(self.nfp.next()) # Current number
        self.mn, self.mx = [int(x) for x in self.rfp.next().split()] # Current range

    def go(self):
        while True:
            if self.mx < self.num:
                try:
                    self.mn, self.mx = [int(x) for x in self.rfp.next().split()]
                except StopIteration:
                    break
            else:   
                if self.mn <= self.num <= self.mx:
                    self.d[(self.mn, self.mx)] += self.num
                    self.n[(self.mn, self.mx)] += 1
                try:
                    self.num = float(self.nfp.next())
                except StopIteration:
                    break
        self.nfp.close()
        self.rfp.close()
        return self.d, self.n

def run(ranges_filename, numbers_filename):
    r = Gen(ranges_filename, numbers_filename)
    d, n = r.go()
    for mn, mx in sorted(d):
        s, N = d[(mn, mx)], n[(mn, mx)]
        if s:
            av = s/N
        else:
            av = 0
        sys.stdout.write('%d %d %.3f\n' % (mn, mx, av))

各ファイルに 10,000,000 個の数字が含まれるファイルでは、上記は出力部分なしで私のコンピューターで約 1.5 分で実行されます。

于 2013-09-25T17:30:16.083 に答える
1

素朴なアプローチは、 Numbers.txt をいくつかの構造に番号順に読み取り、次に Ranges の各行を読み取り、バイナリ検索を使用して範囲内の最小の数値を見つけ、それよりも大きい数値を読み取ってそれらすべてを見つけることです。これにより、対応する出力行を生成できます。

問題は、すべての数値をメモリに保持できないことだと思います。

したがって、各フェーズで数値の一部を読み取り、上記のプロセスを実行する段階で問題を実行できますが、注釈付きバージョンの範囲を使用して、これまでに生成された値の COUNT を各行に含めることができます。意味し、同様に注釈付きのバージョンを書き込みます。

明らかに、最初のパスには注釈付きバージョンの Ranges がなく、最終パスではそれが生成されません。

于 2013-09-25T00:01:19.620 に答える