python - あるリストから別のリストに番号を移動する最も簡単な方法

Question

リストがあります：

list1=[1,8,2,9,3,8,7,10]

「7」を超えるすべての値を取得して新しいリストに配置する絶対最速の方法を知りたいです。リストに何億もの項目があると時間がかかりすぎる for ループを使用したくありません。

理想的には次のようなものです：

list1=[1,8,2,9,3,8,7,10]
list2=AboveNumber(7,list1)
print list2
>>>[8,9,8,10]

ご提案ありがとうございます。処理時間に感謝！

Answer 1

上で引用したように、最初の解決策は、リストを並べ替えて、興味深い値に続く部分だけを保持することです。ipythonセルtimeitを使用する

data = randint(10,size=2000)

素朴な方法

%%timeit
[ i for i in data if i>7 ]
# 1.8 ms per loop

ソート方法

data2 = sorted(data)
import bisect

%%timeit
data2[bisect.bisect(data2,7):]
# 13.6 us per loop

ただし、一般的に、数値データを処理する必要がある場合は、numpyライブラリを使用することを強くお勧めします。ナイーブな方法では、すでにソート方法とほぼ同じくらい高速です

import numpy as np
adata = np.array(data)

%%timeit
adata[adata>7]
# 28.5 us per loop

ただし、numpy配列でもソート方法を使用できます。

adata.sort()

%%timeit
adata[adata.searchsorted(7):]
# 2.1 us per loop

配列が大きいほど、最適化されたCルーチンに近いnumpy配列のパフォーマンスが向上します（実際には、これらは最適化されたCコードの集まりであり、Pythonラッパーを呼び出すという過負荷を支払うだけです）

編集：

速度の関係はアレイのサイズによって異なることに注意してください。リストのナイーブなnumpyメソッドとsortingメソッドは、およそ5 * 10 ^ 5の要素に対して同じ速度ですが、同じサイズでは、sorted配列を使用したnumpyメソッドは多かれ少なかれ3000倍高速です。

Answer 2

ソートされた順序を維持して使用することについてあまり心配しませんnumpy：

import numpy as np
a = np.arange(50)
print a[a >= 7]

#[ 7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49]

すでにソートされているアイテムがある場合は、bisectモジュールを利用できます (またはnumpy、ソートされたデータを操作するための独自のメソッドがあります)。

import bisect

items = range(50)
index = bisect.bisect_left(items, 7)
print items[index:]
# [7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]

そして、ソートされた順序でアイテムを追加するには:

bisect.insort_left(items, 3)
print items
#[0, 1, 2, 3, 3, 4, 5, .. snip ...]

Answer 3

AboveNumber は魔法のようなものではありません。リストが順序付けされていない場合は、リスト内のすべての項目を実行する必要があります。

これを最適化するには、リストを順番に維持します。つまり、挿入または消去の後にリストが常に順序付けられるようにすることです。

リストが順序付けられている場合、バイナリ検索で「平均」を見つけることができます。これは、すべてのリストを実行するよりもはるかに高速であり、その位置でリストを切り取ります。