在python中旋转列表最有效的方法是什么? 现在我有这样的东西:
>>> def rotate(l, n):
... return l[n:] + l[:n]
...
>>> l = [1,2,3,4]
>>> rotate(l,1)
[2, 3, 4, 1]
>>> rotate(l,2)
[3, 4, 1, 2]
>>> rotate(l,0)
[1, 2, 3, 4]
>>> rotate(l,-1)
[4, 1, 2, 3]
有没有更好的办法?
在python中旋转列表最有效的方法是什么? 现在我有这样的东西:
>>> def rotate(l, n):
... return l[n:] + l[:n]
...
>>> l = [1,2,3,4]
>>> rotate(l,1)
[2, 3, 4, 1]
>>> rotate(l,2)
[3, 4, 1, 2]
>>> rotate(l,0)
[1, 2, 3, 4]
>>> rotate(l,-1)
[4, 1, 2, 3]
有没有更好的办法?
当前回答
我想你想要的是这个:
a.insert(0, x)
其他回答
我不知道这是否“有效”,但它也有效:
x = [1,2,3,4]
x.insert(0,x.pop())
编辑:再次你好,我刚刚发现这个解决方案的一个大问题! 考虑下面的代码:
class MyClass():
def __init__(self):
self.classlist = []
def shift_classlist(self): # right-shift-operation
self.classlist.insert(0, self.classlist.pop())
if __name__ == '__main__':
otherlist = [1,2,3]
x = MyClass()
# this is where kind of a magic link is created...
x.classlist = otherlist
for ii in xrange(2): # just to do it 2 times
print '\n\n\nbefore shift:'
print ' x.classlist =', x.classlist
print ' otherlist =', otherlist
x.shift_classlist()
print 'after shift:'
print ' x.classlist =', x.classlist
print ' otherlist =', otherlist, '<-- SHOULD NOT HAVE BIN CHANGED!'
shift_classlist()方法执行的代码与我的x.insert(0,x.pop())-solution相同,otherlist是一个独立于类的列表。在将otherlist的内容传递给MyClass之后。Classlist列表,调用shift_classlist()也会改变otherlist列表:
控制台输出:
before shift:
x.classlist = [1, 2, 3]
otherlist = [1, 2, 3]
after shift:
x.classlist = [3, 1, 2]
otherlist = [3, 1, 2] <-- SHOULD NOT HAVE BIN CHANGED!
before shift:
x.classlist = [3, 1, 2]
otherlist = [3, 1, 2]
after shift:
x.classlist = [2, 3, 1]
otherlist = [2, 3, 1] <-- SHOULD NOT HAVE BIN CHANGED!
我使用Python 2.7。我不知道这是不是一个错误,但我认为更有可能是我误解了这里的一些东西。
有人知道为什么会这样吗?
这也取决于您是想将列表移到合适的位置(改变它),还是想让函数返回一个新列表。因为,根据我的测试,像这样的东西比你的实现(添加两个列表)至少快20倍:
def shiftInPlace(l, n):
n = n % len(l)
head = l[:n]
l[:n] = []
l.extend(head)
return l
事实上,即使在它的顶部添加l = l[:]来操作传入的列表的副本,速度仍然是原来的两倍。
各种实现,在http://gist.github.com/288272上有一些计时
下面是一个高效的算法,不需要使用任何额外的数据结构:
旋转(nums: List[int], k: int):
k = k%len(nums)
l, r = 0, len(nums)-1
while (l<r):
nums[l], nums[r]= nums[r], nums[l]
l,r=l+1,r-1
l,r = 0, k-1
while (l<r):
nums[l], nums[r]=nums[r], nums[l]
l,r=l+1,r-1
l,r=k,len(nums)-1
while (l<r):
nums[l], nums[r]=nums[r], nums[l]
l,r=l+1,r-1
下面的方法是O(n)到位,辅助内存不变:
def rotate(arr, shift):
pivot = shift % len(arr)
dst = 0
src = pivot
while (dst != src):
arr[dst], arr[src] = arr[src], arr[dst]
dst += 1
src += 1
if src == len(arr):
src = pivot
elif dst == pivot:
pivot = src
请注意,在python中,这种方法与其他方法相比效率非常低,因为它不能利用任何部分的本机实现。
我也对此感兴趣,并将一些建议的解决方案与perfplot(我的一个小项目)进行了比较。
事实证明凯利·邦迪的建议
tmp = data[shift:]
tmp += data[:shift]
在所有轮班中都表现良好。
从本质上讲,perfplot执行增加大型数组的移位并测量时间。以下是调查结果:
Shift = 1:
Shift = 100:
代码重现情节:
import numpy
import perfplot
import collections
shift = 100
def list_append(data):
return data[shift:] + data[:shift]
def list_append2(data):
tmp = data[shift:]
tmp += data[:shift]
return tmp
def shift_concatenate(data):
return numpy.concatenate([data[shift:], data[:shift]])
def roll(data):
return numpy.roll(data, -shift)
def collections_deque(data):
items = collections.deque(data)
items.rotate(-shift)
return items
def pop_append(data):
data = data.copy()
for _ in range(shift):
data.append(data.pop(0))
return data
b = perfplot.bench(
setup=lambda n: numpy.random.rand(n).tolist(),
kernels=[
list_append,
list_append2,
roll,
shift_concatenate,
collections_deque,
pop_append,
],
n_range=[2 ** k for k in range(7, 20)],
xlabel="len(data)",
)
b.show()
b.save("shift100.png")