1

私はbashで次の問題を解決しましたが、ファイルのサイズを減らす必要があることを考えると、非常に非効率的で非常に遅いと感じています。誰かがPythonで同じことを行う方法を知っていて、うまくいけば物事をスピードアップすることを望んでいました。

元々の問題は、非常に大きなテキストファイル(5000万から6000万行、タブ区切りの列)を減らすことでした。列の1つがキーとして扱われています。つまり、ファイル内に一意のキーを持つ行がいくつあるかを判断し、それらのパーセンテージ(たとえば、75%削減した場合は総数の4分の1)をランダムに選択して追加します。結果を保持する新しいファイル。残りのキーを引き続き調べ、ランダム化してから、各一意のキーを含むすべての行を同じ割合で減らします。削減ができない場合は、すべての行を結果のファイルに引き継ぐだけです。

私が言ったように、私のbashスクリプトは非常にうまく機能しますが、それは遅く、さまざまなawkおよびgrepコンストラクトをつなぎ合わせます。すべてのアカウントで、Pythonはこれをはるかに洗練された方法で、メモリをあまり損なうことなく処理する必要があります(この場合も、5,000万行以上のファイルを処理しています)。どんな提案/トリックも役に立ちます!ありがとう!

4

3 に答える 3

2

簡単な解決策は、キー列でファイルを並べ替えることです。たとえば、タブで区切られた入力を2番目の列で並べ替えます。

#!/bin/bash
printf "a\tz\nb\ty\nc\tx" | sort -k 2 -t $'\t'

次に、一意のキーごとにランダムな行の25%を取得するという単純な問題を解決します。この場合、キーが等しいすべての行が隣接しており、一意のキーごとに少なくとも1つの行を保持する必要があります。

#!/usr/bin/env python
import random
import sys
from itertools import chain, groupby

def choose_random(iterator, fraction, random=random.random):
    """Lazy analog of:

        L = list(iterator)
        k = int(len(L) * fraction + .5) or 1 # get at least one
        result = random.sample(L, k)

    Note: this function doesn't randomize the order of elements
          that would require to keep selected elements in memory
          and number of output elements is not exactly k
    """
    # always yield at least one item if input is not empty
    item = next(iterator)
    it = (x for x in chain([item], iterator) if random() < fraction)
    for x in chain([next(it, item)], it):
        yield x

def getkey(line):
    return line.split("\t")[1] # 2nd column

for key, group in groupby(sys.stdin, key=getkey):
    sys.stdout.writelines(choose_random(group, fraction=0.25))

注:入力ファイルの最後の行には改行が含まれている必要があります。含まれていない場合、最後の行を選択すると出力が破損します。

スクリプトは、stdinで(キー列によって)ソートされた入力を受け入れ、縮小された出力をstdoutに出力します。一度に1行だけメモリに保存する必要があります。これはシングルパスアルゴリズム(O(n))です。

于 2013-02-27T14:54:18.983 に答える
1

あなたの問題は曖昧なので、私は高レベルの解決策を提供します

  1. fileObj.read()メモリ内のファイル全体を読み取らないでください。fileObj.readlines()ファイルを繰り返し処理してfor line in fileObjください。なんで?これは熱狂的に記憶になります
  2. リストに基づいてキューの実装を作成します

    class Queue(object):
        def __init__(self, max_size):
            self.queue = []
            self.max_size = max_size
        def __getitem__(self, index):
            if 0 <= index < max_size:
                return self.queue[index]
            else:
                raise IndexError
        def __iter__(self):
            return iter(self.queue)
        def push(seq):
            if isinstance(seq, Iterable):
                if len(self.queue) + len(seq) > self.max_size:
                    raise Full
                self.queue = seq
            else:
                if len(self.queue) + 1 > self.max_size:
                    raise Full
                self.queue.append(seq)
        def pop():
            if self.queue:
                return self.queue.pop(0)
    
  3. maxsize =2*選択したアイテムのパーセンテージでキューの辞書を作成します

何かのようなもの

    PCT_SELECTED = 100
    MAXSIZE = 2 * PCT_SELECTED
    KEY_START = 10
    KEY_STOP = 15 
    from collection import defaultdict
    queue_dict = defaultdict(Queue(MAXSIZE))
  1. キュー内の要素をノンブロッキングファションに配置します
  2. キューがいっぱいの場合、例外Fullが発生します。その場合、キューから要素の50%をランダムに選択し、残りを破棄します。

何かのようなもの

    with open("your-file") as fin:
        for line in fin:
            key = line[KEY_START: KEY_STOP]
            try:
                queue_dict[key].push(line)
            except Full:
                queue_dict[key] = random.sample(queue_dict[key], PCT_SELECTED)
  1. 最後に辞書を繰り返し処理し、キューをランダムに削除します

    queue_dict = {key: random.sample(value, PCT_SELECTED) for key, value in queue_dict.items()}
    
  2. これで、辞書を読み、ファイルに書き込むことができます。

于 2013-02-27T10:36:36.880 に答える
0

多数のアイテムについては、75%を選択するだけで、各アイテムの乱数をチェックすることができます。

import random

with open('input') as f:
for line in f:
    if random.random() < 0.75:
        print line

また、各キーから少なくとも1つのアイテムを保証する必要がある場合(2行しかない場合でも):

import random
keys = set()

with open('input') as f:
    for line in f:
        columns = line.split('\t')
        key = columns[0]

        if not key in keys:
           print line
           keys.add(key)
           continue

        if random.random() < 0.75:
            print line
于 2013-02-27T12:38:54.740 に答える