Iterable of integers except specific value

数値計算の実装を行っていると、ある特定の数値を除外した数列を生成したくなることがあります。行列の特定の行や列を除いた要素を処理する際、例えば枢軸演算を行う場合がこれにあたります。

Pythonで簡単に実装すると以下となります。

for i in range(N):
    if i == n:
        continue
    # Process with integer i. i is in [0, N) except value n.

Nを10、nを5とした場合は、以下の整数群に対して処理を行うことになります。

# Integer i is in [0, N) except value 5.
0 1 2 3 4 6 7 8 9

Pythonではタプル、リスト、リスト内包表記、ジェネレータ等を用いて様々なアプローチを取ることが出来ます。上述の実装を含め、一時間ほどで思いついた13種類を実装し、ベンチマークを取ってみました。全て、Python3.1にて記述しています。

まずは本エントリ初めに記載した、forとifによる実装です。これをfor_ifと名付けます。

# for_if
for i in range(N):
    if i == n:
        continue
    # Process with integer i.

この実装では、除外する値nが範囲[0, N)に入っていない場合でも動作するため、続く実装群もそれに習うことにします。

二番目の実装ではリスト内包表記を用いました。リスト内包表記はコンパクトな記述を可能にするだけではなく、関数呼び出しを抑えるため動作速度も速くなるそうです。Pythonの内包表記はなぜ速い?に大変分かりやすくまとめられています。

こちらの実装は、list_comprehensionと名付けます。

# list_comprehension
for i in [i for i in range(N) if i != n]:
    # Process with integer i.

三番目の実装ではリスト内包表記の替わりにジェネレータ表現を用いました。generator_expressionと名付けます。

ジェネレータは遅延実行されますので、予め数列を生成しません。リストを生成してから反復を開始するリスト内包表記に比べ、要素数が大きくなった場合にメモリのオーバーヘッドを押さえることが出来るよう期待出来ます。

# generator_expression
for i in (i for i in range(N) if i != n):
  # Process with integer i.

Pythonでは+演算子を用いて、タプル同士、またリスト同士の結合が可能です。四番目の実装は、nより前とnより後の整数列をタプルとして生成し、+演算子を用いて合成したものです。tuple_concatと名付けます。

タプルを2つ生成した後にそれらを結合した新しいタプルを生成するため、要素数が大きくなった場合に要素のコピーがオーバーヘッドとなるよう予想出来ます。

# tuple_concat
if 0 <= n < N:
    it = tuple(range(n)) + tuple(range(n+1, N))
else:
    it = range(N)
for i in it:
    # Process with integer i.

次の実装はtuple_concatとほぼ同様ですが、タプルの代わりにリストを用いました。list_concatと名付けます。

要素の変更を行わない場合は、リストよりも効率のよいタプルを用いることが推奨されています。tuple_concatと比較することで、タプルに対するリストのオーバーヘッドを知ることが出来ます。

# list_concat
if 0 <= n < N:
    it = list(range(n)) + list(range(n+1, N))
else:
    it = range(N)
for i in it:
    # Process with integer i.

六番目の実装では変更可能なリストの性質を利用しています。一先ず[0, N)の整数列を生成し、n番目の数値を削除するアプローチです。list_delと名付けます。

# list_del
if 0 <= n < N:
    it = list(range(N))
    it[n:n+1] = []
else:
    it = range(N)
for i in it:
    # Process with integer i.

七番目の実装ではnより前、nより後の整数列をrangeオブジェクトで遅延生成し、さらにitertools.chainを用いて遅延結合するというアプローチを取りました。range_chainと名付けます。

関数rangeはrangeオブジェクトを生成します。rangeオブジェクトはジェネレータとして実装されています。数列だけに反復毎の処理およびメモリに保持するデータは軽量でしょう。

また、先にも記述したように、itertools.chainもジェネレータとして実装されています。そのため、要素のコピーも発生しないでしょうし、メモリに最も負担をかけない実装であるように思います。

# range_chain
import itertools
if 0 <= n < N:
    it = itertools.chain(range(n     ),
                         range(n+1, N))
else:
    it = range(N)
for i in it:
    # Process with integer i.

八番目の実装では、ビルトインのfilter関数を用いました。builtin_filterと名付けます。

filterは大変便利な関数ですが、一回の反復に付き一回の関数呼び出しを伴います。それだけにオーバーヘッドが高そうです。

# builtin_filter
for i in filter(lambda i: i != n, range(N)):
    # Process with integer i.

次の実装は、builtin_filterとほとんど変わりません。filterの代わりにitertools.filterfalseを用い、関数の真偽条件を反転しています。filterfalseと名付けます。

# filterfalse
import itertools
for i in itertools.filterfalse(lambda i: i == n, range(N)):
    # Process with integer i.

十番目の実装では、nより前の整数列をitertools.takewhileで、またnより後の整数列をitertools.dropwhileで遅延生成し、さらにitertools.chainで遅延合成させました。Haskellの書籍を読んでいて湧いたアイデアです。これを、takewhile_dropwhile_chainと名付けます。

一回の反復に付き一回の関数呼び出しを伴いますし、nが大きくなればなるほどitertools.dropwhileが整数列をドロップしている間の処理が無駄となります。rangeオブジェクトが用意されているPythonでは有用な実装であるように思えません。

# takewhile_dropwhile_chain
import itertools
for i in itertools.chain(itertools.takewhile(lambda x: x <  n, range(N)),
                         itertools.dropwhile(lambda x: x <= n, range(N))):
    # Process with integer i.

次の実装にはPython3.1にて追加されたitertools.compressを用いています。itertools.compressは2つのiterableなオブジェクトを受け取り、セレクタが真のデータを返すジェネレータを返す関数です。

>>> import itertools
>>> itertools.compress('ABCDEF', [1,0,1,0,1,1])
['A', 'C', 'E', 'F']

今回はセレクタとして整数値のリストを用いた実装とブール値のリストを用いた実装を行いました。PythonSpeed - PythonInfo Wikiによると、無限ループの実装にはwhile 1:を用いたほうがwhile True:を用いるよりも速い、という記述がなされていたため、型の違いによる性能差を計ることも目的としました。

セレクタを併用することによる自由度は高く、より汎用的な実装を行える潜在能力を備えているよう思います。

まずセレクタとして整数値を用いたものを実装しました。compress_with_intと名付けます。

# compress_with_int
if 0 <= n < N:
    selectors = [1] * N
    selectors[n] = 0
    it = itertools.compress(range(N), selectors)
else:
    it = range(N)
for i in it:
    # Process with integer i.

次の実装は、セレクタにブール値を用いたものです。compress_with_boolと名付けます。

# compress_with_bool
if 0 <= n < N:
    selectors = [True] * N
    selectors[n] = False
    it = itertools.compress(range(N), selectors)
else:
  it = range(N)
for i in it:
    # Process with integer i.

最後にitertools.compressそのもののアイデアを、zipを併用したジェネレータ表現として実装しました。generator_expression_with_selectorと名付けます。

# generator_expression_with_selector
if 0 <= n < N:
    selectors = [1] * N
    selectors[n] = 0
    it = (i for i, selector in zip(range(N), selectors) if selector)
else:
    it = range(N)
for i in it:
    # Process with integer i.

さて、以下がベンチマークの結果です。計測にはtimeit.Timerオブジェクトを用い、数列の大きさNを1、10、100、1000、10000、100000および1000000と増やしつつ、それぞれ100回の反復を行い、時間を計測しました。

除外する数nはN // 2として算出しています。takewhile_dropwhile_chainはn / Nが1.0に近づけば近づくほど性能が悪くなりますが、今回は考慮していません。

表中の単位は秒です。また、Nが1、10の場合は全ての実装において0.01秒未満であったため、表から省いています。

Method	N=100	1000	10000	100000	1000000
for_if	0.01	0.07	0.67	8.24	89.98
list_comprehension	0.01	0.08	0.79	10.25	113.22
generator_expression	0.01	0.10	1.00	11.69	123.34
tuple_concat	0.01	0.05	0.48	6.80	77.87
list_concat	0.01	0.05	0.48	6.82	80.09
list_del	0.01	0.05	0.47	6.48	75.62
range_chain	0.01	0.05	0.47	6.23	73.27
builtin_filter	0.01	0.14	1.33	14.95	170.46
filterfalse	0.01	0.13	1.27	14.45	168.86
takewhile_dropwhile_chain	0.01	0.13	1.26	14.28	166.01
compress_with_int	0.01	0.05	0.50	6.51	80.80
compress_with_bool	0.01	0.05	0.48	6.50	80.51
generator_expression_with_selector	0.01	0.07	0.65	8.09	99.35

以下は計測結果をプロットしたものです。横軸は要素の数、縦軸は計測時間を示し、双方共に対数表示しています。

図では線が混み合っており個々の区別がつきませんが、計測速度を元に5つのグループに分けられそうです。計測速度が短い順に、AからEまで分類してみました。

Group A
- tuple_concat
- list_concat
- list_del
- range_chain
- compress_with_int
- compress_with_bool
Group B
- for_if
- generator_expression_with_selector
Group C
- list_comprehension
Group D
- generator_expression
Group E
- builtin_filter
- filterfalse
- takewhile_dropwhile_chain

Group AとBを分けている要因は、一回の反復に付きifを一回評価していることでしょうか。また、一回の反復に付き一回関数を呼び出しているGroup EはGroup Aと比較して2倍ほど速度が遅い結果となりました。関数呼び出しのオーバーヘッドは予想以上に大きいようです。

意外なことに、Group C、Dとしたリスト内包表記とジェネレータ表現による実装は思っていたほど高速ではありませんでした。

range_chainは省メモリな実装であると予想していたのですが、動作速度の点でも最も速かったため、正直驚きました。

tuple_concatとlist_concatを比べると、確かにタプルの生成はリストの生成よりも効率的であることが分かります。といっても、tuple_concatはlist_delよりも低速です。要素のコピーはやはりコストの高い操作のようです。

整数値とブール値の比較では、ブール値のほうが若干高速でした。

また、itertools.compressがよい性能を出しているのも嬉しい結果です。反復のオーバーヘッドをそれほど考慮する必要がないようなので、セレクタの生成を工夫すれば、様々な実装に対応出来る潜在能力を備えていると言えるのではないでしょうか。

例えば除外する数値が複数個ある場合でも、以下のように実装すれば目的を達せます。反復部分の速度自信は変わらないことに注目してください。

# compress_with_bool_that_excludes_multile_values
selectors = [True] * N
for n in ns:
    if 0 <= n < N:
        selectors[n] = False
for i in itertools.compress(range(N), selectors):
    # Process with integer i.