3

最近、このスレッドで Jon Clements の助けを借りて、次のコードの実行時間が大きく異なることを発見しました。

なぜこれが起こっているのか分かりますか？

コメント: self.stream_data は多くのゼロと int16 値を持つベクトル タプルであり、create_ZS_data メソッドはいわゆる ZeroSuppression を実行しています。

環境
入力: 多くの (3.5k) 小さなファイル (それぞれ ~120kb)
OS: Linux64
Python ver 2.6.8

ジェネレーターに基づくソリューション:

def create_ZS_data(self):
    self.ZS_data = ( [column, row, self.stream_data[column + row * self.rows ]]
                     for row, column in itertools.product(xrange(self.rows), xrange(self.columns))
                     if self.stream_data[column + row * self.rows ] )

プロファイラー情報:

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     3257    1.117    0.000   71.598    0.022 decode_from_merlin.py:302(create_ZS_file)
   463419   67.705    0.000   67.705    0.000 decode_from_merlin.py:86(<genexpr>)

ジョンのソリューション:

create_ZS_data(self):
    self.ZS_data = list()
    for rowno, cols in enumerate(self.stream_data[i:i+self.columns] for i in xrange(0, len(self.stream_data), self.columns)):
        for colno, col in enumerate(cols):
            # col == value, (rowno, colno) = index
            if col:
                self.ZS_data.append([colno, rowno, col])


プロファイラー情報:

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     3257   18.616    0.006   19.919    0.006 decode_from_merlin.py:83(create_ZS_data)
4

2 に答える 2

4

以前の議論を見ました。あなたの賢い理解力は、ソース コードの文字ほど効率的ではないことに悩んでいるようです。私が指摘しなかったのは、これが私の好ましい実装であるということでした:

def sparse_table_elements(cells, columns, rows):
    ncells = len(cells)
    non_zeros = list()
    for nrow in range(0, ncells, columns):
         row = cells[nrow:nrow+columns]
         for ncol, cell in enumerate(row):
             if cell:
                 non_zeros.append([ncol, nrow, cell])
    return non_zeros

私はそれをテストしていませんが、それを理解することはできます。潜在的な非効率性として私に飛びつくことがいくつかあります。2 つの一定の単調な "退屈な" インデックスのデカルト積を再計算するには、コストがかかります。

itertools.product(xrange(self.rows), xrange(self.columns))

次に、結果[(0, 0), (0, 1), ...]を使用して、ソースから単一要素のインデックス付けを行います。

stream_data[column + row * self.rows]

これは、「ジョンの」実装のように大きなスライスを処理するよりもコストがかかります。

ジェネレーターは、効率を保証する秘密のソースではありません。この特定のケースでは、135kb のデータが既にコアに読み込まれているため、ジェネレーターの構築が不十分であるとコストがかかるようです。簡潔な行列演算が必要な場合は、APLを使用してください。読みやすいコードが必要な場合は、Python で極端に最小化しようとしないでください。

于 2012-07-23T13:15:59.283 に答える
2

Jonのソリューションをジェネレーターとして簡単に書き直すことができます。

def create_ZS_data(self):
    self.ZS_data = ([colno, rowno, col]
                    for rowno, cols in enumerate(self.stream_data[i:i+self.columns]
                                                 for i in xrange(0, len(self.stream_data), self.columns))
                    for colno, col in enumerate(cols)
                    if col)

これがJonのループベースのソリューションと同じように動作することを強く期待します。これは、パフォーマンスの違いがアルゴリズム実装のミッドスケールの詳細にあることを示しています。

于 2012-07-23T13:37:36.787 に答える