3

大きなtxtファイルからN行を取得するには、pythonを使用する必要があります。これらのファイルは、基本的にタブ区切りのテーブルです。私のタスクには次の制約があります。

  • これらのファイルにはヘッダーが含まれる場合があります (複数行のヘッダーを持つものもあります)。
  • ヘッダーは同じ順序で出力に表示される必要があります。
  • 各行は 1 回だけ取得できます。
  • 現在、最大のファイルは約 150GB (約 60 000 000 行) です。
  • ファイル内の行の長さはほぼ同じですが、ファイルによって異なる場合があります。
  • 私は通常、5000行のランダム行を取得します（最大1000,000行が必要になる場合があります）

現在、私は次のコードを書いています：

inputSize=os.path.getsize(options.input)
usedPositions=[] #Start positions of the lines already in output

with open(options.input) as input:
    with open(options.output, 'w') as output:

        #Handling of header lines
        for i in range(int(options.header)):
            output.write(input.readline())
            usedPositions.append(input.tell())

        # Find and write all random lines, except last
        for j in range(int(args[0])):
            input.seek(random.randrange(inputSize)) # Seek to random position in file (probably middle of line)
            input.readline() # Read the line (probably incomplete). Next input.readline() results in a complete line.
            while input.tell() in usedPositions: # Take a new line if current one is taken
                input.seek(random.randrange(inputSize))
                input.readline() 
            usedPositions.append(input.tell()) # Add line start position to usedPositions
            randomLine=input.readline() # Complete line
            if len(randomLine) == 0: # Take first line if end of the file is reached
                input.seek(0)
                for i in range(int(options.header)): # Exclude headers
                    input.readline()
                randomLine=input.readline()
            output.write(randomLine)

このコードは正しく動作しているようです。

seek() が最も長い行の位置を返す可能性が高く、次の行が出力に書き込まれるため、このコードが入力の最も長い行に続く行を好むことは承知しています。入力ファイルの行はほぼ同じ長さであるため、これは関係ありません。また、Nが入力ファイルの行数よりも大きい場合、このコードが無限ループになることも認識しています。行数の取得には時間がかかるため、このチェックは実装しません。

RAM と HDD の制限は関係ありません。プログラムの速度だけが気になります。このコードをさらに最適化する方法はありますか? それとも、より良いアプローチがありますか？

編集: 明確にするために、1 つのファイル内の行の長さはほぼ同じです。ただし、このスクリプトを実行する必要がある複数のファイルがあり、これらのファイルの行の平均の長さは異なります。たとえば、ファイル A は 1 行あたり最大 100 文字、ファイル B は 1 行あたり最大 50000 文字の場合があります。ファイルの平均行長は事前にわかりません。

4

5 に答える 5

8

サンプリングしている最後の行までのすべてのファイルの順次読み取りを回避する唯一の方法があります-これまでの回答のどれもそれについて言及していないことに驚いています:

あなたが言ったように、典型的な行の長さがある場合は、ファイル内の任意の場所を探して、いくつかのバイトを読み取る必要があります.3倍または4倍の値が必要です。次に、読み取ったチャンクを改行文字 (「\n」) で分割し、2 番目のフィールド (ランダムな位置にある行) を選択します。

また、ファイルを一貫してシークできるようにするには、ファイルを「バイナリ読み取り」モードで開く必要があります。したがって、行末マーカーの変換は手動で処理する必要があります。

この手法では、読み取られた行番号を取得できないため、選択した行のオフセットをファイルに保持して、繰り返しを回避します。

#! /usr/bin/python
# coding: utf-8

import random, os


CHUNK_SIZE = 1000
PATH = "/var/log/cron"

def pick_next_random_line(file, offset):
    file.seek(offset)
    chunk = file.read(CHUNK_SIZE)
    lines = chunk.split(os.linesep)
    # Make some provision in case yiou had not read at least one full line here
    line_offset = offset + len(os.linesep) + chunk.find(os.linesep) 
    return line_offset, lines[1]

def get_n_random_lines(path, n=5):
    lenght = os.stat(path).st_size
    results = []
    result_offsets = set()
    with open(path) as input:
        for x in range(n):
            while True:
                offset, line = pick_next_random_line(input, random.randint(0, lenght - CHUNK_SIZE))
                if not offset in result_offsets:
                    result_offsets.add(offset)
                    results.append(line)
                    break
    return results

if __name__ == "__main__":
    print get_n_random_lines(PATH)
于 2012-09-05T16:11:39.787 に答える
4

ファイルに N 行の均一なサンプルが必要な場合は、選択する正確な行数を知る必要があります。ランダムにシークしてもこれは行われません。より長い行は、最も長い行に直接続く行を優先して結果を歪めます。

幸いなことに、ファイルを 1 回読み取るだけで、これらの N 行を選択できます。基本的に、最初の N 行を (ランダムな順序で) 選択し、選択した行を、読み取った行数に基づいて確率が減少する新しい行にランダムに置き換えます。

N == 1 の場合、読み取った n 行目が前のランダム ピックを置き換える確率randint(0, n) < 1は同じ分布で、より多くの行が読み取られるにつれて、セット内の既に選択された行がランダムに選択されます。

Python random lines from subfoldersで、Blkknght は iterable からサイズ N のランダム サンプルを選択するための非常に役立つ関数を作成しました。

import random

def random_sample(n, items):
    results = []

    for i, v in enumerate(items):
        r = random.randint(0, i)
        if r < n:
            if i < n:
                results.insert(r, v) # add first n items in random order
            else:
                results[r] = v # at a decreasing rate, replace random items

    if len(results) < n:
        raise ValueError("Sample larger than population.")

    return results

これは、一連のヘッダーを保持するための要件と組み合わせるのは簡単です。

from itertools import islice

with open(options.input) as input:
    with open(options.output, 'w') as output:

        # Handling of header lines
        # Use islice to avoid buffer issues with .readline()
        for line in islice(input, int(options.header)):
            output.write(line)

        # Pick a random sample
        for line in random_sample(int(args[0]), input):
            output.write(line)

これにより、ファイル全体が一度に読み取られ、均一なランダム サンプルが選択され、出力ファイルに書き込まれます。したがって、これには Θ(L) の複雑さがあり、L はファイル内の行数です。

于 2012-09-06T08:23:45.933 に答える
3

N 行番号をランダムに選択してから、ファイルを 1 行ずつ調べて、リストにある番号の行を取得する方が速いと思います。現在、乱数ごとにランダムな場所を探す必要があるため、O(N*M) であり、M はファイルのサイズです。私が提案するのはO(M)です。

于 2012-09-05T10:42:35.300 に答える
1
  • 明らかな改善は、変数に使用することset()です。usedPositionsルックアップが高速になり、最大 10^6 の使用位置を処理する必要があるため、ルックアップ時間は無関係ではありません。
  • for ループのxrange代わりに使用します。range整数の完全なリストを割り当てる必要はないようです。
于 2012-09-05T10:43:13.240 に答える
0

未テスト (ファイルを 2 回読み取る必要があります):

import random

N = 5000
with open('file.in') as fin:
    line_count = sum(1 for i in fin)
    fin.seek(0)
    to_take = set(random.sample(xrange(line_count), N))
    for lineno, line in enumerate(fin):
        if lineno in to_take:
            pass # use it

ただし、行は「ほぼ」同じサイズであると述べているため、それを使用os.path.getsizeして平均行長で割ることができます（既知であるか、ファイルからN行から盗聴されたかに関係なく）、それを使用して生成しますline_count-それ無作為抽出には十分近いでしょう。

ファイルをmmap検索し、ファイルサイズ、平均行長、行数の最適な推測、ランダムな行番号を組み合わせて「シーク」し、次の行の開始点まで後方または前方に検索することもできます。(mmap文字列のように扱えるようになるので.index、オフセットを使用したり、re本当に必要に応じて使用したりできます)。

于 2012-09-05T12:29:47.643 に答える