python - Python での関数のパフォーマンスの向上

Question

この形式の数GBのテキストファイルがあります

0 274 593869.99 6734999.96 121.83 1,
0 273 593869.51 6734999.92 121.57 1,
0 273 593869.15 6734999.89 121.57 1,
0 273 593868.79 6734999.86 121.65 1,
0 273 593868.44 6734999.84 121.65 1,
0 273 593869.00 6734999.94 124.21 1,
0 273 593868.68 6734999.92 124.32 1,
0 273 593868.39 6734999.90 124.44 1,
0 273 593866.94 6734999.71 121.37 1,
0 273 593868.73 6734999.99 127.28 1,

Windows 上の Python 2.7 でフィルタリングする単純な関数があります。この関数はファイル全体を読み取り、同じ行idtile(1 列目と 2 列目) を選択し、点 (x、y、z、およびラベル) のリストとidtile.

tiles_id = [j for j in np.ndindex(ny, nx)] #ny = number of row, nx= number of columns
idtile = tiles_id[0]

def file_filter(name,idtile):
        lst = []
        for line in file(name, mode="r"):
            element = line.split() # add value
            if (int(element[0]),int(element[1])) == idtile:
                lst.append(element[2:])
                dy, dx = int(element[0]),int(element[1])
        return(lst, dy, dx)

ファイルは 32 GB を超えており、ボトルネックはファイルの読み取りです。関数を高速化するために、いくつかの提案や例を探しています (例: 並列計算またはその他のアプローチ)。

私の解決策は、テキストファイルをタイルに分割することです (x と y の位置を使用)。ソリューションはエレガントではなく、効率的なアプローチを探しています。

score 1 · Accepted Answer

おそらく、問題を解決するための最善かつ最速の方法は、（大規模な）並列システムでマップリデュースアルゴリズムを使用することです。

score 1 · Accepted Answer

速度の主要なルール: 少ないことをします。

のソートされたバージョンを作成し、huge.txtの位置を追跡できますidtitle。したがって、(223872, 23239) を検索すると、指定された情報がファイル内のどの位置にあるかが既にわかっており、( file.seek) より前のすべてをスキップできます。この情報は'INDEX'とある程度等しいと主張する人もいるかもしれません。
mmapファイルをRAMにmmapするために使用できます。
「ワーカー」を書き始めて、さまざまなファイル/位置で作業することができます
指定されたファイルを SQL サーバーなどに転送し、標準 SQL を使用してデータを取得できます。はい、32ギガのデータをデータベースに転送するには時間がかかりますが、それは一種の前処理と考えてください。その後、データベースはあらゆる手段を使用して、アプローチよりも高速にデータにアクセスします。

マイナーな考え:

line.split()多くの小さなメモリ割り当てを回避する代わりに、スライスを使用できます。

データベースの使用方法の概要:

次のようなものがあるとPostgreSQLします。

CREATE TABLE tiles
(
  tile_x integer,
  tile_y integer,
  x double precision,
  y double precision,
  z double precision,
  flag integer
);

次に、入力ファイル内のすべての空白をに置き換え、すべてをに置き換え|(,素敵で光沢のあるを作成するため.csv)、それをデータベースに直接フィードできます。

 COPY "tiles" from "\full\path\to\huge.txt" WITH DELIMITER "|";

次に、次のような派手なことを行うことができます。

SELECT * FROM "tiles";

tile_x | tile_y |     x     |     y      |   z    | flag
-------+--------+-----------+------------+--------+-----
     0 |    274 | 593869.99 | 6734999.96 | 121.83 |    1
     0 |    273 | 593869.51 | 6734999.92 | 121.57 |    1
     0 |    273 | 593869.15 | 6734999.89 | 121.57 |    1
     0 |    273 | 593868.79 | 6734999.86 | 121.65 |    1
     0 |    273 | 593868.44 | 6734999.84 | 121.65 |    1
     0 |    273 |    593869 | 6734999.94 | 124.21 |    1
     0 |    273 | 593868.68 | 6734999.92 | 124.32 |    1
     0 |    273 | 593868.39 |  6734999.9 | 124.44 |    1
     0 |    273 | 593866.94 | 6734999.71 | 121.37 |    1
     0 |    273 | 593868.73 | 6734999.99 | 127.28 |    1

またはこのようなもの：

SELECT * FROM "tiles" WHERE tile_y > 273;

tile_x | tile_y |     x     |     y      |   z    | flag
-------+--------+-----------+------------+--------+-----
     0 |    274 | 593869.99 | 6734999.96 | 121.83 |    1

score 1 · Accepted Answer

代わりに文字列比較を行うことで、すべての行でsplit()andを実行することを避けることができます。int()

def file_filter(name,idtile):
    lst = []
    id_str = "%d %d " % idtile
    with open(name) as f:
        for line in f:
            if line.startswith(id_str):
                element = line.split() # add value
                lst.append(element[2:])
                dy, dx = int(element[0]),int(element[1])
    return(lst, dy, dx)

score 1 · Accepted Answer

大きなファイルを 1 回読み取り、タイル ID ごとに (一時) ファイルを書き込むようにコードを変更することをお勧めします。何かのようなもの：

def create_files(name, idtiles=None):
    files = {}
    for line in open(name):
         elements = line.split()
         idtile = (int(elements[0]), int(elements[1]))
         if idtiles is not None and idtile not in idtiles:
             continue
         if idtile not in files:
             files[idtile] = open("tempfile_{}_{}".format(elements[0], elements[1]), "w")
         print >>files[idtile], line
    for f in files.itervalues():
        f.close()
    return files

create_files(){(tilex, tiley): fileobject}辞書を返します。

「開いているファイルが多すぎます」エラーを回避するために、各行を書き込んだ後にファイルを閉じるバリアント。{(tilex, tiley: filename}このバリアントは辞書を返します。おそらく少し遅くなるでしょう。

def create_files(name, idtiles=None):
    files = {}
    for line in open(name):
         elements = line.split()
         idtile = (int(elements[0]), int(elements[1]))
         if idtiles is not None and idtile not in idtiles:
             continue
         filename = "tempfile_{}_{}".format(elements[0], elements[1])
         files[idtile] = filename
         with open(filename, "a") as f:
             print >>f, line
    return files

score 1 · Accepted Answer

あなたの idtile は特定の順序で表示されます。つまり、サンプルデータは、特定の「idtile」を通過して次の行にヒットすると、その「idtile」を含む行が再び表示される可能性がないことを示唆しています。この場合、必要なfor'idtile' の処理を終了して別の idtile にヒットしたら、ループを中断することができます。私の頭の上から：

loopkiller = false
for line in file(name, mode="r"):
    element = line.split()
    if (int(element[0]),int(element[1])) == idtile:
        lst.append(element[2:])
        dy, dx = int(element[0]),int(element[1])
        loopkiller = true
    elif loopkiller:
        break;

このように、特定の「idtile」を使い終わったら停止します。あなたの例では、ファイルの最後まで読み続けます。

idtile がランダムな順序で表示される場合は、最初にファイルの順序付きバージョンを作成してみてください。

また、idtiles の数字を個別に評価すると、ファイルをより速くトラバースするのに役立つ場合があります。youridtileが 1 桁と 3 桁の整数の 2 つのタプルであると仮定すると、おそらく次のようなものです。

for line in file(name, mode="r"):
    element = line.split()
    if int(element[0][0]) == idtile[0]:
        if element[1][0] == str(idtile[1])[0]:
            if element[1][1] == str(idtile[1])[1]:
                if element[1][2] == str(idtile[1])[2]:
                    dy, dx = int(element[0]),int(element[1])
                else go_forward(walk)
            else go_forward(run)
         else go_forward(sprint)
     else go_forward(warp)

score 1 · Accepted Answer

ここにいくつかの統計があります。より多くのソリューションが表示されるように更新します。次のプログラムは、質問の行の繰り返しで構成されるファイルを操作します。

import sys

def f0(name, idtile):
    lst = []
    dx, dy = None, None
    with open(name) as f:
        for line in f:
            pass


"""def f0(name, idtile):
    lst = []
    dx, dy = None, None
    with open(name) as f:
        for line in f:
            line.split()"""


def f1(name, idtile):
    lst = []
    dx, dy = None, None
    with open(name) as f:
        for line in f:
            element = line.split() # add value
            if (int(element[0]),int(element[1])) == idtile:
                lst.append(element[2:])
                dy, dx = int(element[0]),int(element[1])
    return(lst, dy, dx)


def f2(name, idtile):
    lst = []
    dx, dy = None, None
    with open(name) as f:
        for line in f:
            element = line.split() # add value
            pdx, pdy = int(element[0]),int(element[1])
            if (pdx, pdy) == idtile:
                lst.append(element[2:])
                dy, dx = pdx, pdy
    return(lst, dy, dx)

def f2(name, idtile):
    lst = []
    dx, dy = None, None
    with open(name) as f:
        for line in f:
            element = line.split() # add value
            pdx, pdy = int(element[0]),int(element[1])
            if (pdx, pdy) == idtile:
                lst.append(element[2:])
                dy, dx = pdx, pdy
    return(lst, dy, dx)


def f3(name,idtile):
    lst = []
    id_str = "%d %d " % idtile
    with open(name) as f:
        for line in f:
            if line.startswith(id_str):
                element = line.split() # add value
                lst.append(element[2:])
                dy, dx = int(element[0]),int(element[1])
    return(lst, dy, dx)

functions = [f0, f1, f2, f3]

functions[int(sys.argv[1])]("./srcdata.txt",(0, 273))

タイミングのシェルスクリプトは簡単です。

#!/bin/sh
time python ./timing.py 0
time python ./timing.py 1
time python ./timing.py 2

以前に実行した関数が他の関数の時間に影響を与えるのを避けるために、そのように実行することを好みます。

結果は次のとおりです。

0.02user 0.01system 0:00.03elapsed
0.42user 0.01system 0:00.44elapsed
0.32user 0.02system 0:00.34elapsed
0.33user 0.01system 0:00.35elapsed

良いニュース:ファイルの読み取りはボトルネックではありません。int への余分な転送を削除すると効果的です。

悪いニュース: 私はまだそれを大幅に最適化する方法を知りません。

score 1 · Accepted Answer

フィルターをジェネレーター関数に変換できます。

def file_filter(name):
        lst = []
        idtile = None
        for line in file(name, mode="r"):
            element = line.split() # add value
            if idtile is None:
               idtile = (int(element[0]), int(element[1]))
            if (int(element[0]), int(element[1])) == idtile:
                lst.append(element[2:])
                dy, dx = int(element[0]),int(element[1])
            else:
                yield lst, dx, dy
                lst = []
                idtile = None

list_of_data, dx, dyファイルが idtile でソートされている場合、この関数は idtile ごとにの 1 つのタプルを返す必要があります。

新しい場合は、次のように使用できます。

for lst, dx, dy in file_filter('you_name_it'):
    process_tile_data(lst, dx, dy)

score 1 · Accepted Answer

完全な読み取り手順と、行を読み取って何もしない場合の時間を比較することをお勧めします。それらの時間が近い場合、実際にできる唯一のことはアプローチを変更すること (ファイルを分割するなど) です。おそらく最適化できるのは、ファイルの読み取り時間ではなく、データ処理時間です。

また、あなたのコードには、修正する価値のある 2 つの箇所があります。

with open(name) as f:
    for line in f:
        pass #Here goes the loop body

ファイルを明示的に閉じるために使用withします。あなたのソリューションは CPython で動作するはずですが、それは実装に依存し、常に効果的であるとは限りません。
文字列の変換をint2 回実行します。これは比較的遅い操作です。結果を再利用して 2 番目のものを削除します。

PS地球表面上の一連のポイントの深さまたは高さの値の配列のように見え、表面はタイルに分割されています。:-)

score 1 · Accepted Answer

私の解決策は、idtile ごとに大きなテキストファイルを多数の小さなバイナリファイルに分割することです。テキストファイルをより速く読み取るには、pandas を使用できます。

import pandas as pd
import numpy as np
n = 400000 # read n rows as one block
for df in pd.read_table(large_text_file, sep=" ", comment=",", header=None, chunksize=n):
    for key, g in df.groupby([0, 1]):
        fn = "%d_%d.tmp" % key
            with open(fn, "ab") as f:
                data = g.ix[:, 2:5].values
                data.tofile(f)

次に、次の方法で 1 つのバイナリファイルの内容を取得できます。

np.fromfile("0_273.tmp").reshape(-1, 4)

score 0 · Accepted Answer

わかった。これを何度も行う必要がある場合は、明らかに何らかのインデックスを作成する必要があります。しかし、これが頻繁なアクティビティでない場合は、このようにマルチスレッド化するのが最善の策です。

NUMWORKERS = 8
workerlist = []
workQ = Queue.Queue()

def file_filter(name,idtile, numworkers):
    for i in range(NUMWORKERS):
        worker = threading.Thread(target=workerThread, args=(lst,))
    lst = []
    for line in file(name, mode="r"):
        workQ.put(line)                
    for i in range(NUMWORKERS):
        workQ.put(None)
    workQ.join()
    return lst , idtile[0], idtile[1]

def workerThread(lst):
    line = workQ.get()
    if not line:
        return
    element = line.split() # add value
    if (int(element[0]),int(element[1])) == idtile:
        lst.append(element[2:])

これが各 idtile に対して非常に頻繁に発生するアクティビティである場合、ソリューションは大幅に異なります。これを多数の idtile に対して一緒に行うと、最高の償却パフォーマンスが得られます。既知の任意の数の idtile を、ファイルの 1 回のループで処理できるためです。

python - Python での関数のパフォーマンスの向上

10 に答える 10

Related

Reference