12

整数のソートされたリスト L があり、L の順序が維持されるようにリストに挿入したい値 X があります。同様に、X の最初のインスタンスをすばやく見つけて削除したいと考えています。

質問:

  1. 可能であれば、bisect モジュールを使用して最初の部分を実行するにはどうすればよいですか?
  2. L.remove(X) は、2 番目の部分を実行する最も効率的な方法でしょうか? Python はリストがソートされたことを検出し、対数除去プロセスを自動的に使用しますか?

コードの試行例:

i = bisect_left(L, y)

L.pop(i)                 #works
del L[bisect_left(L, i)] #doesn't work if I use this instead of pop
4

2 に答える 2

18

  1. bisect.insort()関数を使用します：

    bisect.insort(L, X)

  2. L.remove(X)が見つかるまでリスト全体をスキャンしますX。del L[bisect.bisect_left(L, X)]代わりに使用してください (実際Xに にある場合L)。

リストの途中から削除しても、その位置以降の要素はすべて 1 ステップ左にシフトする必要があるため、コストがかかることに注意してください。バイナリ ツリーがパフォーマンスのボトルネックになる場合は、より良いソリューションになる可能性があります。

于 2013-06-27T16:23:43.393 に答える
2

Raymond Hettinger のIndexableSkiplistを使用できます。O(ln n)時間内に 3 つの操作を実行します。

  • 値を挿入
  • 値を削除
  • ランクによるルックアップ値
import skiplist
import random
random.seed(2013)

N = 10
skip = skiplist.IndexableSkiplist(N)
data = range(N)
random.shuffle(data)
for num in data:
    skip.insert(num)

print(list(skip))
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

for num in data[:N//2]:
    skip.remove(num)

print(list(skip))
# [0, 3, 4, 6, 9]
于 2013-06-27T16:37:35.287 に答える