OPはこれをインプレースで実行したいと考えています。
操作を高速化するための鍵は、リストの作成とリストの短縮/延長を最小限に抑えることです。これは、リストインデックスの割り当てを常に1：1にするように努力する必要があることを意味します。したがって、noL[i:i] = L[a:b]とnoL[a:b] = []です。でループを使用するとinsert、popリストが何度も短くなったり長くなったりするため、さらに悪いことになります。リストを連結することも悪いことです。最初にパーツごとに1つのリストを作成してから、各パーツに1つずつ、ますます大きな連結リストを作成する必要があるからです+。これを「インプレース」で実行するためL[:]、最後に生成されたリストをに割り当てる必要があります。
# items: 0 | 1 2 3 | 4 5 6 7 | 8 9
# a span1 b span2 c
# pos: 1 4 8
# Result:
# 0 | 4 5 6 7 | 1 2 3 | 8 9
# a span2 span2 c
最初に観察してみましょう。、、、およびが挿入位置である場合a = start、実行したい操作は、マーカーでカットし、とを交換することです。ただし、andが挿入位置である場合は、 andも交換します。したがって、この関数では、スワップする必要がある2つの連続するセグメントを処理するだけです。b = end = start + lengthc|span1span2b = startc = endaspan1span2
物を移動しながら重複する値を格納する必要があるため、新しいリストの作成を完全に回避することはできません。ただし、2つのスパンのどちらを一時リストに保存するかを選択することで、リストをできるだけ短くすることができます。
def inplace_shift(L, start, length, pos):
if pos > start + length:
(a, b, c) = (start, start + length, pos)
elif pos < start:
(a, b, c) = (pos, start, start + length)
else:
raise ValueError("Cannot shift a subsequence to inside itself")
if not (0 <= a < b < c <= len(L)):
msg = "Index check 0 <= {0} < {1} < {2} <= {3} failed."
raise ValueError(msg.format(a, b, c, len(L)))
span1, span2 = (b - a, c - b)
if span1 < span2:
tmp = L[a:b]
L[a:a + span2] = L[b:c]
L[c - span1:c] = tmp
else:
tmp = L[b:c]
L[a + span2:c] = L[a:b]
L[a:a + span2] = tmp
コスはタイミングに誤りがあったようですので、引数を修正（とendから計算）した後、コードでそれらをやり直しました。これらは、最も遅いものから最も速いものへの結果です。startlength
Nick Craig-Wood: 100 loops, best of 3: 8.58 msec per loop
vivek: 100 loops, best of 3: 4.36 msec per loop
PaulP.R.O. (deleted?): 1000 loops, best of 3: 838 usec per loop
unbeli: 1000 loops, best of 3: 264 usec per loop
lazyr: 10000 loops, best of 3: 44.6 usec per loop
他のアプローチのいずれかが正しい結果をもたらすことをテストしていません。
これまでに得たものを確認しましょう。
コード
def subshift(L, start, end, insert_at):
'Nick Craig-Wood'
temp = L[start:end]
L = L[:start] + L[end:]
return L[:insert_at] + temp + L[insert_at:]
# (promising but buggy, needs correction;
# see comments at unbeli's answer)
def unbeli(x, start, end, at):
'unbeli'
x[at:at] = x[start:end]
x[start:end] = []
def subshift2(L, start, length, pos):
'PaulP.R.O.'
temp = pos - length
S = L[start:length+start]
for i in range(start, temp):
L[i] = L[i + length]
for i in range(0,length):
L[i + temp] = S[i]
return L
def shift(L,start,n,i):
'vivek'
return L[:start]+L[start+n:i]+L[start:start+n]+L[i:]
ベンチマーク:
> args = range(100000), 3000, 2000, 60000
> timeit subshift(*args)
100 loops, best of 3: 6.43 ms per loop
> timeit unbeli(*args)
1000000 loops, best of 3: 631 ns per loop
> timeit subshift2(*args)
100 loops, best of 3: 11 ms per loop
> timeit shift(*args)
100 loops, best of 3: 4.28 ms per loop
私はPythonの部分文字列でそれを行います
def subshift(L, start, end, insert_at):
temp = L[start:end]
L = L[:start] + L[end:]
return L[:insert_at] + temp + L[insert_at:]
print subshift(['a','b','c','d','e','f','g','h'], 2, 5, 4)
startend切り出す部分文字列の位置を参照します (end は、通常の python スタイルでは非排他的です。 部分文字列が切り出された後insert_atに、部分文字列を再び挿入する位置を参照します。
適切に最適化された C コードが大変な作業を行っているため、部分文字列の長さが 1 文字または 2 文字を超える場合、これは反復を伴うどのソリューションよりも高速になると思います。
別のインプレース ソリューションを次に示します。
def movesec(l,srcIndex,n,dstIndex):
if srcIndex+n>dstIndex: raise ValueError("overlapping indexes")
for i in range(n):
l.insert(dstIndex+1,l.pop(srcIndex))
return l
print range(10)
print movesec(range(10),3,2,6)
出力：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # orginal
[0, 1, 2, 5, 6, 7, 3, 4, 8, 9] # modified
>>> L = ['a','b','c','d','e','f','g','h']
>>> L[7:7] = L[2:5]
>>> L[2:5] = []
>>> L
['a', 'b', 'f', 'g', 'c', 'd', 'e', 'h']
def shift(L,start,n,i):
return L[:start]+L[start+n:i]+L[start:start+n]+L[i:]