1

それぞれ約50行の長さの約5万個のファイルで探している800個の要素のリストがあります。（これらは一般的でない名前のxmlタグです-検索は簡単なので、Beautifulスープは使用していません。）

800個の要素のリストは、1つが見つかるたびに短縮されます。

ファイルを反復処理し、

私が最初に通過するのは重要ですか-すべての可能な要素に対して各行をチェックします（「スポット」、「ローバー」、「フィド」などの行をチェックします...）、または一度に1つの要素をチェックするすべての行を通過します（たとえば、ファイル内のすべての行で「スポット」をチェックしてから、すべての行で「ローバー」などをチェックします...）？

それとも、これはすべて一緒に非効率的ですか？（これはPythonを使用しています。）私は考えていました：

for line in somefile:
        for element in somelist:
              if re.search(element, line):
                  ....

また：

for element in somelist:
        for line in somefile:
              if re.search(element, line):
                  ....
4

3 に答える 3

4

通常、大きい方のデータセットは順次アクセスされるデータセットのままにし、関心のある値をメモリ内に、または大きい方のデータセットのインデックスとして保持します。そうです、それは重要です。あなたの例では、ファイルを複数回スキャンしようとしていますが、これは非常に低速です。

これらの各ファイルが50行で、探している「単語」が800個ある例を見てみましょう。

for filename in filenames:
    for line in open(filename):
        if any(word in line for word in words):
            pass # do something

はメモリ内にあり、スキャンが簡単なためwords、各ファイルを800回以上開くよりもはるかに優れています。これはコストのかかる操作です。

したがって、「最も高価な」データセット（最長ではない可能性があります）を順番にスキャンする必要があると言い換える必要があると思います。

于 2012-10-20T14:43:39.357 に答える
3

アルゴリズムの複雑さを表すbig-O表記はどちらの方法でも同じですが、反復可能ファイルの1つ（たとえば、ファイル）のアクセスが非常に遅く、他の反復可能オブジェクトよりも大きい可能性がある場合は、次のようにする必要があります。可能な限り数回、つまり1回繰り返すのは苦痛です。

それを除けば、アルゴリズムはどちらかの方法で記述または理解する方が簡単かもしれません。たとえば、任意の正規表現に一致するリスト内のすべての文字列のリストが必要な場合は、最初に文字列リストを繰り返し処理し、各正規表現を各行に対してチェックして、一致したときに内部ループから抜け出す方が簡単です。

実際、このように繰り返すと、タスク全体が1つのライナーになる可能性があります。

foundlines = [line for line in inputlines if any(r.search(line) for r in regexes)]

ボーナスとして、リスト内包表記/ジェネレーター式を使用することで、Pythonが可能な最速の反復を取得できますany()。

最初に正規表現を繰り返し処理して、各正規表現に一致する行のリストのリストを作成するか、複数の正規表現に一致する行の1つの大きなリスト（重複を含む）を作成するのが最も自然です。最大で1つの正規表現に一致する行のリストを作成する場合は、アルゴリズムの複雑さに影響を与える重複を何らかの方法で（反復中またはその後に）排除する必要があります。結果も異なる順序で出力される可能性があり、これは懸念事項となる可能性があります。

つまり、反復可能オブジェクトのパフォーマンスが同等である場合に、解決しようとしている問題に最も適したアプローチを選択してください。

于 2012-10-20T14:58:11.547 に答える
1

複雑さの順序はですO(n*m)。ここで、nとmはリストとファイル内のエントリの数を表すことができるため、最初にどちらの方法を実行してもかまいません。

于 2012-10-20T14:45:23.637 に答える