def make_list_foo_only(size):
"""
foo+初期インデックスを生成:foo0, foo1, ..., fooX
"""
l = list("foo{:97d}".format(x) for x in range(size))
return l
def make_list_bar_only(size):
"""
bar+初期インデックスを生成: bar0, bar1, ..., barX
"""
l = list("bar{:97d}".format(x) for x in range(size))
return l
def make_list_alternate_foo_bar(size):
"""
foo,bar+初期インデックスが交互を生成: foo0, bar1, ..., fooX or barX
"""
l = list("bar{:97d}".format(x) if x % 2 else "foo{:97d}".format(x) for x in range(size))
return l
def make_list_bar50_foo50(size):
"""
前半をbar+初期インデックス、後半foo+初期インデックスを生成: bar0, bar1, ..., fooX
"""
l = list("bar{:97d}".format(x) if x < size / 2 else "foo{:97d}".format(x) for x in range(size))
return l
def make_list_foo50_bar50(size):
"""
前半をfoo+初期インデックス、後半bar+初期インデックスを生成: foo0, foo1, ..., barX
"""
l = list("foo{:97d}".format(x) if x < size / 2 else "bar{:97d}".format(x) for x in range(size))
return l
def list_remove(l):
"""
公式ドキュメントの方法で、スライスによる一時コピー有り。
e.startswith("f")以外の条件で削除しないケースが有る場合はNG
シンプルだけど項目数が増えると糞遅くなる。
"""
for i, e in enumerate(l[:]):
if e.startswith("f"):
# あれこれ
l.remove(e)
return l
def list_del_reversed(l):
"""
末尾から削除、スライスによる一時コピーは不要。
あれこれ処理するのが後ろからになる事が許容できるならこれが良好。
"""
for i in reversed(range(len(l))): # xrangeは3でrangeに要置換なので使用せず
e = l[i]
if e.startswith("f"):
# あれこれ
del l[i]
return l
def list_del_offset(l):
"""
リスト先頭から処理が必要な場合の妥協案。
スライスによる一時コピー有り。
"""
offset = 0 # オフセット用カウンタ(削除で-1,追加で+1)
for i, e in enumerate(l[:]):
if e.startswith("f"):
# あれこれ
del l[i + offset] # 追加削除によるズレを補正して消す。
offset -= 1
return l
"""
i = 0
while i < len(l):
e = l[i]
if e.startswith("f"):
# あれこれ
del l[i]
else:
i += 1
return l
def list_alt_for(l):
"""
lの要素数をベースにオフセット計算してforで回す。
posがi相当になっているが、若干保守性が落ちるかも。
l[:]による、スライスによる一時コピーは不要。
"""
offset = 0 # オフセット用カウンタ(削除で-1,追加で+1)
for i in range(len(l)): # xrangeは3でrangeに要置換なので使用せず
pos = i + offset # 追加/削除により現在読むべきインデックスを計算
e = l[pos]
if e.startswith("f"):
# あれこれ
del l[pos]
offset -= 1
return l
def list_make_newlist1(l):
"""
番外。新規リスト作成して入れ替え。
安定して高速。
"""
tmp = [] # 新規リスト
for i, e in enumerate(l):
if e.startswith("f"):
pass # あれこれ
else:
tmp.append(e)
l = tmp
return l
def list_make_newlist2(l):
"""
番外。新規リスト作成して入れ替え。
i不要なら取るとより高速化する。
"""
tmp = [] # 新規リスト
for e in l:
if e.startswith("f"):
pass # あれこれ
else:
tmp.append(e)
l = tmp
return l
if __name__ == "__main__":
TEST_NUM = 1
TEST_SIZE = 100000
print("size={0}".format(TEST_SIZE))
for f in test_func:
for s in test_dataset:
print(f, s, timeit.repeat(f + "(l)", "from __main__ import {0},make_list_{1};l=make_list_{1}({2})".format(f, s, TEST_SIZE), number=TEST_NUM))
駄目っです。リファレンス参照どぞ (スコア:1)
[:]でコピー作らないと駄目よー
詳しくはリファレンス参照:2.6 [python.org] 3だけど日本語化されてる。中身は同じ [python.org]
Re: (スコア:-1)
l[i]を削除した時点でlと[:]でiがズレますよ。
Re: (スコア:0)
そのとおり。リファレンス参照は関係ない話で、原因は 「iがズレますよ。」ですね
"foo bar baz"で[:]を使うと動くように見えるのはタダの勘違いです
"foo bar baz"ならもとのコードでも[:]でもどちらでも bar baz と
正しくうごいているようにみえます
別コメントにあるように"foo foo foo"で試せば[:]でもエラーがでます
Re: (スコア:1)
"foo bar baz"ならもとのコードでも[:]でもどちらでも bar baz と
正しくうごいているようにみえます
今回のテストデータでは正しくうごいているようにみえるだけです。
"foo foo bar"というテストデータでテストすれば解りますが、
for中に要素数が変わると"foo bar"と2個目のfで始まる奴が残ります。
私がリンクしたリファレンスのNote(注釈)を読まないから「厄介なバグ」を見逃したり、作りこみます。
iがズレるのは、
del l[i]
を
l.remove(e)
みたいにiに依存しない形で変更する事で回避可能です。
もしくはオフセットを持たすか、whileで手動でカウントアップするか。
removeの場合は意図的に残したみたいなパターンで重複が有り得る場合は破綻しますけど。
例えば1個目のfooは残す場合、foo,foo,barな場合、1個目が消えちゃいます
Re: (スコア:0)
要素を一意にしてからチェックするのは処理時間的に無駄な気がする
Re: (スコア:1)
要素を一意にしてからチェックするのは処理時間的に無駄な気がする
他の要因、例えば別のリストが居てそっちの内容も影響するとか等、
条件判定でeを残すパターンが有るとかなければ一意でなくても良いです。
remove(e)ですが、処理的にリスト内の探索の時間が無駄になります。
ですが、それが問題にならないくらい途中を削除する事がNGです。
削除する度に内部で削除した以降の要素を手前に持ってくる移動処理をして、リストが再構築されてると思わしき挙動なのでめちゃ重です。
リストが一万件越えて大半を削除する事になると体感できるぐらいになってくるかと。
実測してみた。 (スコア:1)
要素を一意にしてからチェックするのは処理時間的に無駄な気がする
# ちゃんと計測したことないけど、新規リスト作って、最後に入れ替えた方が早いと思う。
気になったのでちょろっと書いた糞コードと実測結果晒しておきます。
ちゃんとデバッグしてないからバグってたり、動かなかったらごめんなさい。
Python使いが見たら罵倒されると思う。
# coding: utf-8
import timeit
def make_list_foo_only(size):
"""
foo+初期インデックスを生成:foo0, foo1, ..., fooX
"""
l = list("foo{:97d}".format(x) for x in range(size))
return l
def make_list_bar_only(size):
"""
bar+初期インデックスを生成: bar0, bar1, ..., barX
"""
l = list("bar{:97d}".format(x) for x in range(size))
return l
def make_list_alternate_foo_bar(size):
"""
foo,bar+初期インデックスが交互を生成: foo0, bar1, ..., fooX or barX
"""
l = list("bar{:97d}".format(x) if x % 2 else "foo{:97d}".format(x) for x in range(size))
return l
def make_list_bar50_foo50(size):
"""
前半をbar+初期インデックス、後半foo+初期インデックスを生成: bar0, bar1, ..., fooX
"""
l = list("bar{:97d}".format(x) if x < size / 2 else "foo{:97d}".format(x) for x in range(size))
return l
def make_list_foo50_bar50(size):
"""
前半をfoo+初期インデックス、後半bar+初期インデックスを生成: foo0, foo1, ..., barX
"""
l = list("foo{:97d}".format(x) if x < size / 2 else "bar{:97d}".format(x) for x in range(size))
return l
def list_remove(l):
"""
公式ドキュメントの方法で、スライスによる一時コピー有り。
e.startswith("f")以外の条件で削除しないケースが有る場合はNG
シンプルだけど項目数が増えると糞遅くなる。
"""
for i, e in enumerate(l[:]):
if e.startswith("f"):
# あれこれ
l.remove(e)
return l
def list_del_reversed(l):
"""
末尾から削除、スライスによる一時コピーは不要。
あれこれ処理するのが後ろからになる事が許容できるならこれが良好。
"""
for i in reversed(range(len(l))): # xrangeは3でrangeに要置換なので使用せず
e = l[i]
if e.startswith("f"):
# あれこれ
del l[i]
return l
def list_del_offset(l):
"""
リスト先頭から処理が必要な場合の妥協案。
スライスによる一時コピー有り。
"""
offset = 0 # オフセット用カウンタ(削除で-1,追加で+1)
for i, e in enumerate(l[:]):
if e.startswith("f"):
# あれこれ
del l[i + offset] # 追加削除によるズレを補正して消す。
offset -= 1
return l
def list_del_while(l):
"""
whileでループ。多分アルゴリズムとしては定番。
スライスによる一時コピーが不要。
"""
i = 0
while i < len(l):
e = l[i]
if e.startswith("f"):
# あれこれ
del l[i]
else:
i += 1
return l
def list_alt_for(l):
"""
lの要素数をベースにオフセット計算してforで回す。
posがi相当になっているが、若干保守性が落ちるかも。
l[:]による、スライスによる一時コピーは不要。
"""
offset = 0 # オフセット用カウンタ(削除で-1,追加で+1)
for i in range(len(l)): # xrangeは3でrangeに要置換なので使用せず
pos = i + offset # 追加/削除により現在読むべきインデックスを計算
e = l[pos]
if e.startswith("f"):
# あれこれ
del l[pos]
offset -= 1
return l
def list_make_newlist1(l):
"""
番外。新規リスト作成して入れ替え。
安定して高速。
"""
tmp = [] # 新規リスト
for i, e in enumerate(l):
if e.startswith("f"):
pass # あれこれ
else:
tmp.append(e)
l = tmp
return l
def list_make_newlist2(l):
"""
番外。新規リスト作成して入れ替え。
i不要なら取るとより高速化する。
"""
tmp = [] # 新規リスト
for e in l:
if e.startswith("f"):
pass # あれこれ
else:
tmp.append(e)
l = tmp
return l
if __name__ == "__main__":
TEST_NUM = 1
TEST_SIZE = 100000
test_func = ["list_remove", "list_del_reversed", "list_del_offset", "list_del_while", "list_alt_for", "list_make_newlist1", "list_make_newlist2"]
test_dataset = ["foo_only", "bar_only", "foo50_bar50", "bar50_foo50", "alternate_foo_bar"]
print("size={0}".format(TEST_SIZE))
for f in test_func:
for s in test_dataset:
print(f, s, timeit.repeat(f + "(l)", "from __main__ import {0},make_list_{1};l=make_list_{1}({2})".format(f, s, TEST_SIZE), number=TEST_NUM))
size=10000
('list_remove', 'foo_only', [0.0202849, 0.020381, 0.020325000000000003])
('list_remove', 'bar_only', [0.0020605000000000068, 0.0020545999999999898, 0.0020540000000000003])
('list_remove', 'foo50_bar50', [0.016058599999999992, 0.01571679999999999, 0.015870699999999988])
('list_remove', 'bar50_foo50', [0.2739176, 0.2705252, 0.27289700000000006])
('list_remove', 'alternate_foo_bar', [0.14674729999999991, 0.15636780000000017, 0.14641890000000002])
('list_del_reversed', 'foo_only', [0.0032707000000000708, 0.0030402000000000484, 0.003187599999999957])
('list_del_reversed', 'bar_only', [0.0020439000000000984, 0.0020807999999998827, 0.0020431999999999118])
('list_del_reversed', 'foo50_bar50', [0.011159499999999989, 0.0121595000000001, 0.0116676])
('list_del_reversed', 'bar50_foo50', [0.0026223999999999137, 0.0025556999999998276, 0.002904100000000076])
('list_del_reversed', 'alternate_foo_bar', [0.006996100000000061, 0.00716490000000003, 0.0065614000000000505])
('list_del_offset', 'foo_only', [0.020691999999999933, 0.02100360000000001, 0.02136249999999995])
('list_del_offset', 'bar_only', [0.0020555999999998242, 0.002150699999999839, 0.0020561999999999525])
('list_del_offset', 'foo50_bar50', [0.016197499999999865, 0.015592199999999945, 0.015897099999999886])
('list_del_offset', 'bar50_foo50', [0.0066973999999999645, 0.006717500000000154, 0.006721999999999895])
('list_del_offset', 'alternate_foo_bar', [0.01131329999999986, 0.011483899999999991, 0.012075199999999953])
('list_del_while', 'foo_only', [0.020963800000000088, 0.021134399999999998, 0.020529699999999984])
('list_del_while', 'bar_only', [0.0029015999999999487, 0.0029175999999999647, 0.002899000000000207])
('list_del_while', 'foo50_bar50', [0.016644699999999624, 0.01669070000000028, 0.016268100000000008])
('list_del_while', 'bar50_foo50', [0.007319100000000134, 0.007477799999999757, 0.007421399999999689])
('list_del_while', 'alternate_foo_bar', [0.013268700000000244, 0.011585800000000201, 0.014191899999999702])
('list_alt_for', 'foo_only', [0.022350900000000173, 0.024382099999999962, 0.020842599999999933])
('list_alt_for', 'bar_only', [0.002456300000000411, 0.0024375999999999287, 0.0026652999999998706])
('list_alt_for', 'foo50_bar50', [0.016613400000000222, 0.0162555000000002, 0.018212899999999976])
('list_alt_for', 'bar50_foo50', [0.007888899999999754, 0.007264599999999621, 0.007129799999999964])
('list_alt_for', 'alternate_foo_bar', [0.011618600000000257, 0.012027300000000185, 0.011729700000000065])
('list_make_newlist1', 'foo_only', [0.002018199999999748, 0.002092900000000064, 0.0020531999999997552])
('list_make_newlist1', 'bar_only', [0.002883500000000261, 0.003221399999999708, 0.0028548999999999936])
('list_make_newlist1', 'foo50_bar50', [0.0026148000000003613, 0.0024256000000000277, 0.0024545999999996404])
('list_make_newlist1', 'bar50_foo50', [0.0025102999999999653, 0.0024207000000000534, 0.002571000000000101])
('list_make_newlist1', 'alternate_foo_bar', [0.0031476999999999755, 0.002491599999999927, 0.0028844999999999565])
('list_make_newlist2', 'foo_only', [0.0018306000000003486, 0.0018204000000001663, 0.0017616999999998662])
('list_make_newlist2', 'bar_only', [0.002636299999999814, 0.003360400000000041, 0.0026668999999999166])
('list_make_newlist2', 'foo50_bar50', [0.0038399999999998435, 0.0031262999999999153, 0.002441899999999997])
('list_make_newlist2', 'bar50_foo50', [0.002208100000000268, 0.0024860000000002103, 0.002416600000000102])
('list_make_newlist2', 'alternate_foo_bar', [0.0025965000000001126, 0.0022554000000001295, 0.002659500000000037])
size=100000
('list_remove', 'foo_only', [2.3781085, 2.3154822000000004, 2.3531180000000003])
('list_remove', 'bar_only', [0.02569079999999957, 0.02269420000000011, 0.023082200000000164])
('list_remove', 'foo50_bar50', [1.8456037999999992, 1.8647428000000001, 1.8239116000000006])
('list_remove', 'bar50_foo50', [35.3315298, 32.625142000000004, 33.73005069999999])
('list_remove', 'alternate_foo_bar', [28.2709988, 27.90501309999999, 27.3124526])
('list_del_reversed', 'foo_only', [0.03402810000000045, 0.0337351999999953, 0.03443970000000718])
('list_del_reversed', 'bar_only', [0.02264560000000415, 0.027116699999993443, 0.026550200000002633])
('list_del_reversed', 'foo50_bar50', [1.2540036000000043, 1.2013052000000073, 1.2021094000000119])
('list_del_reversed', 'bar50_foo50', [0.02913470000001439, 0.02952349999998205, 0.027568999999999733])
('list_del_reversed', 'alternate_foo_bar', [0.5289622999999892, 0.5407769999999914, 0.538366400000001])
('list_del_offset', 'foo_only', [2.3119306999999765, 2.3620076999999924, 2.3551582999999994])
('list_del_offset', 'bar_only', [0.026474900000010848, 0.023044700000014018, 0.022622599999976956])
('list_del_offset', 'foo50_bar50', [1.8633136000000263, 1.8391096999999945, 1.8299241999999936])
('list_del_offset', 'bar50_foo50', [0.5447789000000114, 0.5351112000000171, 0.5290412999999887])
('list_del_offset', 'alternate_foo_bar', [1.1755692000000124, 1.192382500000008, 1.1726249999999823])
('list_del_while', 'foo_only', [2.3462406000000158, 2.356452599999983, 2.3107861999999955])
('list_del_while', 'bar_only', [0.03096239999999284, 0.03048860000001241, 0.033044200000006185])
('list_del_while', 'foo50_bar50', [1.8132867000000203, 1.8996553000000063, 1.8552423000000147])
('list_del_while', 'bar50_foo50', [0.5358114, 0.5344815999999923, 0.5388564000000144])
('list_del_while', 'alternate_foo_bar', [1.201421900000014, 1.1926640000000077, 1.1781591000000162])
('list_alt_for', 'foo_only', [2.3044445999999823, 2.3335447999999985, 2.333316100000019])
('list_alt_for', 'bar_only', [0.02627970000000346, 0.028554499999984273, 0.02565900000001875])
('list_alt_for', 'foo50_bar50', [1.8423765000000003, 1.8294257000000016, 1.809911999999997])
('list_alt_for', 'bar50_foo50', [0.5486015999999836, 0.5312174999999684, 0.5550561999999672])
('list_alt_for', 'alternate_foo_bar', [1.1886122999999884, 1.171997900000008, 1.1716663000000267])
('list_make_newlist1', 'foo_only', [0.020871999999997115, 0.021223100000042905, 0.021266700000012406])
('list_make_newlist1', 'bar_only', [0.032357900000022255, 0.034126899999989746, 0.03134740000001557])
('list_make_newlist1', 'foo50_bar50', [0.026914199999964694, 0.027299200000015844, 0.02582200000000512])
('list_make_newlist1', 'bar50_foo50', [0.028417799999999716, 0.025918500000045697, 0.02772540000000845])
('list_make_newlist1', 'alternate_foo_bar', [0.027546199999960663, 0.02815689999999904, 0.026722099999972215])
('list_make_newlist2', 'foo_only', [0.01880399999998872, 0.018749899999988884, 0.018445199999973738])
('list_make_newlist2', 'bar_only', [0.02815370000001849, 0.02831250000002683, 0.02752510000004804])
('list_make_newlist2', 'foo50_bar50', [0.02322569999995494, 0.022848199999998542, 0.03971059999997806])
('list_make_newlist2', 'bar50_foo50', [0.023367500000006203, 0.023758100000009108, 0.023692100000005212])
('list_make_newlist2', 'alternate_foo_bar', [0.029836999999986347, 0.024861500000042724, 0.025187099999982365])
所感:
解ってた事だけど、10万件でのremove(e)(list_remove)が遅すぎて笑える。
使い捨てとか、夜間バッチで1万件流すみたいな用途なら十分だろうけど。
後ろから(list_del_reversed)がやはり優秀で、削除すべきデータが先頭に固まってるパターン(foo50_bar50)でも速い。
オフセット計算してdelしていくパターン(list_del_offset)もそこそこ速いが、
スライスによる一時コピーなしの(list_del_while)とあまり差が無い。
Pythonのwhileはforより遅いと聞いてたけど、list_del_whileよりも無駄に回るlist_alt_forの方が速い?。誤差かもしれないけど。
結果、オフセット計算してdelしていくパターン(list_del_offset)と、元リストの数だけforで回す(list_alt_for)処理時間の差はあまりなさそう。
むしろ一時コピー不要な分優秀?
当然だけど、追記するだけの新しいリスト作るパターン(list_make_newlist1,2)が安定して速い。