a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3
rotate(a, n) # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ
↑このような関数 rotate(=配列(リスト)a の内容を n だけずらす関数)を書いてください
def rotate(a, n):
for b in range(n):
a.append(a.pop(0))
return a
a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3
rotate(a, n) # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
解説:
pop
して最後尾に append
、を n
回繰り返すコード。a.pop(0)
が)def rotate(a, n):
return a[n:] + a[:n]
a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3
rotate(a, n) # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
解説:
n
番目以降・n
番目より前をそれぞれスライスして、それを連結するコード。a
は変更されない)。def rotate(a, n):
b = list(a)
l = len(a)
for i in range(l):
if i < n:
b[i] = a[i + n]
else:
b[i] = a[i + n - l]
return b
a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3
rotate(a, n) # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
解説:
l
を len(a)
とする↓と、(特に後者は)毎回リストの長さを計算するのでよろしくない。# よろしくない例
def rotate(a, n):
b = list(a)
for i in range(len(a)):
if i < n:
b[i] = a[i + n]
else:
b[i] = a[i + n - len(a)]
return b
def rotate(a, n):
b = list(a)
l = len(a)
for i in range(len(a)):
b[i] = a[(i + n) % l]
return b
a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3
rotate(a, n) # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
解説:
if
〜else
で分岐する代わりに、剰余演算を利用if
〜else
よりはパフォーマンス向上def rotate(a, n):
l = len(a)
return [a[(i + n) % l] for i in range(l)]
a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3
rotate(a, n) # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
解説:
def rotate(a, n):
l = len(a)
s = 0
while n:
g = l - n
for i in range(s, g):
# a[i], a[i+n] = a[i+n], a[i]
t = a[i]
a[i] = a[i + n]
a[i + n] = t
n = (s - g) % n
s = g
return a
a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3
rotate(a, n) # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
解説:
l
に対して最大でも l-1
回 の スワップ で完了。def rotate(a, n):
from fractions import gcd
l = len(a)
g = gcd(l, n)
for s in range(g):
t = a[s]
for i in range(1, l / g):
a[(s + (i - 1) * n) % l] = a[(s + i * n) % l]
a[(s - n) % l] = t
return a
a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3
rotate(a, n) # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
# ↑コレ
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
解説:
l/gcd(l,n)
個 ずつの入替(巡回置換)に差し替えた例。from collections import deque
d = deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
d
deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
d.rotate(-3)
d
deque([3, 4, 5, 6, 7, 8, 9, 0, 1, 2])
解説:
deque
(双方向キュー)を利用したrotate
の例。pop(0)
相当の処理も)パフォーマンスは良い。