0

最小値と最大値でスライスできるようにしたい数千のフロートのリストがあります。

EG 使用:

flist = [1.9842, 9.8713, 5.4325, 7.6855, 2.3493, 3.3333]

(私の実際のリストは 400,000 フロートの長さですが、上記は実際の例です)

私は何かが欲しい

def listclamp(minn, maxn, nlist):

そのような

print listclamp(3, 8, flist)

私に与えるべきです

[3.3333, 5.4325, 7.6855]

また、これを 10,000 ～ 30,000 回行う必要があるため、速度は重要です。

（これは私にとって新しいpython領域であるため、これまでに試したことのサンプルコードはありません）

4

3 に答える 3

4

当然のことですが、並べ替えてからフィルター処理するか、フィルター処理してから並べ替えます。

毎回同じリストを持っている場合、最初に並べ替えると明らかに有利です。また、線形ウォークの代わりにフィルタリングにバイナリ検索を使用できることも意味します ( ventsyv の回答で説明されているように)。

毎回異なるリストがある場合は、ソートがおそらく遅い部分であり、小さなリストをそのようにソートしているため、最初にフィルタリングする方がおそらく有利です。

しかし、憶測をやめてテストを始めましょう。

数千の float のリストを使用すると、その約半分が範囲内にあります。

In [1591]: flist = [random.random()*10 for _ in range(5000)]
In [1592]: %timeit sorted(x for x in flist if 3 <= x < 8)
100 loops, best of 3: 3.12 ms per loop
In [1593]: %timeit [x for x in sorted(flist) if 3 <= x < 8]
100 loops, best of 3: 4 ms per loop
In [1594]: %timeit l=sorted(flist); l[bisect.bisect_left(l, 3):bisect.bisect_right(l, 8)]
100 loops, best of 3: 3.36 ms per loop

したがって、フィルタリングしてから並べ替えると優先されます。ventsyn のアルゴリズムは、違いの一部を補っていますが、すべてではありません。しかし、ソートするリストが 1 つしかない場合は、何千回もソートするのではなく、1 回ソートする方が明らかに有利です。

In [1596]: l = sorted(flist)
In [1597]: %timeit l[bisect.bisect_left(l, 3):bisect.bisect_right(l, 8)]
10000 loops, best of 3: 29.2 µs per loop

したがって、同じリストが何度もある場合は、明らかに一度ソートしてください。

それ以外の場合は、実際のデータでテストできますが、数ミリ秒かかるものを最大 22% 削減することについて話しているのです。何千回も実行したとしても、1 秒未満の節約になります。さまざまな実装を入力するコストだけでも、理解、一般化、デバッグ、パフォーマンス テストなどのコストはそれ以上です。

しかし、実際には、数十万の値にまたがる数百万の操作を行っており、速度が重要な場合は、そもそもリストを使用するべきではなく、NumPy配列を使用する必要があります。floatNumPy は、Python オブジェクトとしてボックス化することなく、生の値のみを格納できます。メモリを節約する (およびキャッシュの局所性を向上させる) ことに加えて、これは、たとえば、np.sortの内側のループが の内側のループよりも高速であることを意味sortedします。直接比較します。

そもそも値を配列に格納していると仮定すると、それはどのように積み上げられるでしょうか?

In [1607]: flist = np.random.random(5000) * 10
In [1608]: %timeit a = np.sort(flist); a = a[3 <= a]; a = a[a < 8]
1000 loops, best of 3: 742 µs per loop
In [1611]: %timeit c = b[3 <= b]; d = c[c < 8]
10000 loops, best of 3: 29.8 µs per loop

%timeitしたがって、不格好なアルゴリズムを使用しても、「異なるリスト」の場合のフィルターと並べ替えよりも約 4 倍高速です (最速または最も読みやすいものではなく、1 行に詰め込めるものを探していました…)。そして、「何度も同じリスト」の場合、二分しなくても、二分法とほぼ同じ速さです (もちろん、NumPy でも二分できます)。

于 2014-11-19T22:21:36.473 に答える
1

これにより、必要なソート済みリストが返されます。

flist = [1.9842, 9.8713, 5.4325, 7.6855, 2.3493, 3.3333]

def listclamp(minn, maxn, nlist): 
    return sorted(filter(lambda x: xminn <= x <= maxn, nlist))

print listclamp(3, 8, flist)

リスト内包表記を使用したより高速なアプローチ:

def listclamp2(minn, maxn, nlist): 
    return sorted([x for x in flist if (minn <= and x<=maxn)])

print listclamp2(3, 8, flist)

データによっては、最初にリストをフィルター処理してから並べ替えた方がよい場合があることに注意してください (上記のコードで行ったように)。

パフォーマンスの詳細については、このリンクを参照してください。

于 2014-11-19T22:07:46.287 に答える