Efficient way to rotate a list in python

Question

What is the most efficient way to rotate a list in python   Right now I have something like this    gt  gt  gt  def rotate l  n           return l n     l  n        gt  gt  gt  l    1 2 3 4   gt  gt  gt  rotate l 1   2  3  4  1   gt  gt  gt  rotate l 2   3  4  1  2   gt  gt  gt  rotate l 0   1  2  3  4   gt  gt  gt  rotate l -1   4  1  2  3    Is there a better way

User · Answer

Another alternative   def move arr  n       return  arr  idx-n    len arr   for idx   in enumerate arr

User · Answer

Simplest way I can think of                                           a append a pop 0

User · Answer

I think you ve got the most efficient way  def shift l n       n   n   len l        return l -U     l  -U

User · Answer

I have similar thing  For example  to shift by two     def Shift  args       return args len args -2   args  len args -2

User · Answer

def solution A  K       if len A     0          return A      K   K   len A       return A -K     A  -K     use case A    1  2  3  4  5  6  K   3 print solution A  K     For example  given  A    3  8  9  7  6  K   3   the function should return  9  7  6  3  8   Three rotations were made    3  8  9  7  6  - gt   6  3  8  9  7   6  3  8  9  7  - gt   7  6  3  8  9   7  6  3  8  9  - gt   9  7  6  3  8    For another example  given  A    0  0  0  K   1   the function should return  0  0  0   Given  A    1  2  3  4  K   4   the function should return  1  2  3  4

User · Answer

The following method is O n  in place with constant auxiliary memory   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   Note that in python  this approach is horribly inefficient compared to others as it can t take advantage of native implementations of any of the pieces

User · Answer

What is the use case  Often  we don t actually need a fully shifted array --we just need to access a handful of elements in the shifted array    Getting Python slices is runtime O k  where k is the slice  so a sliced rotation is runtime N  The deque rotation command is also O k   Can we do better    Consider an array that is extremely large  let s say  so large it would be computationally slow to slice it   An alternative solution would be to leave the original array alone and simply calculate the index of the item that would have existed in our desired index after a shift of some kind    Accessing a shifted element thus becomes O 1     def get shifted element original list  shift to left  index in shifted         back calculate the original index by reversing the left shift     idx original    index in shifted   shift to left    len original list      return original list idx original   my list    1  2  3  4  5   print get shifted element my list  1  2  ---- gt  outputs 4  print get shifted element my list  -2  3  ----- gt  outputs 2

User · Answer

I think you are looking for this   a insert 0  x

User · Answer

If you just want to iterate over these sets of elements rather than construct a separate data structure  consider using iterators to construct a generator expression   def shift l n       return itertools islice itertools cycle l  n n len l     gt  gt  gt  list shift  1 2 3  1    2  3  1

User · Answer

Possibly a ringbuffer is more suitable  It is not a list  although it is likely that it can behave enough like a list for your purposes   The problem is that the efficiency of a shift on a list is O n   which becomes significant for large enough lists   Shifting in a ringbuffer is simply updating the head location which is O 1

User · Answer

A collections deque is optimized for pulling and pushing on both ends  They even have a dedicated rotate   method    from collections import deque items   deque  1  2   items append 3           deque     1  2  3  items rotate 1           The deque is now   3  1  2  items rotate -1          Returns deque to original state   1  2  3  item   items popleft     deque     2  3

User · Answer

What about just using pop 0       list pop  i        Remove the item at the given position in the list  and return it  If   no index is specified  a pop   removes and returns the last item in   the list   The square brackets around the i in the method signature   denote that the parameter is optional  not that you should type square   brackets at that position  You will see this notation frequently in   the Python Library Reference

User · Answer

Just some notes on timing   If you re starting with a list  l append l pop 0   is the fastest method you can use  This can be shown with time complexity alone    deque rotate is O k   k number of elements  list to deque conversion is O n  list append and list pop are both O 1    So if you are starting with deque objects  you can deque rotate   at the cost of O k   But  if the starting point is a list  the time complexity of using deque rotate   is O n   l append l pop 0  is faster at O 1    Just for the sake of illustration  here are some sample timings on 1M iterations   Methods which require type conversion    deque rotate with deque object  0 12380790710449219 seconds  fastest  deque rotate with type conversion  6 853878974914551 seconds np roll with nparray  6 0491721630096436 seconds np roll with type conversion  27 558452129364014 seconds   List methods mentioned here    l append l pop 0    0 32483696937561035 seconds  fastest   shiftInPlace   4 819645881652832 seconds       Timing code used is below     collections deque  Showing that creating deques from lists is O n    from collections import deque import big o  def create deque from list l        return deque l   best  others   big o big o create deque from list  lambda n  big o datagen integers n  -100  100   print best    -- gt  Linear  time   -2 6E-05   1 8E-08 n   If you need to create deque objects   1M iterations   6 853878974914551 seconds  setup deque rotate with create deque       from collections import deque import random l    random random   for i in range 1000        test deque rotate with create deque       dl   deque l  dl rotate -1      timeit timeit test deque rotate with create deque  setup deque rotate with create deque    If you already have deque objects   1M iterations   0 12380790710449219 seconds  setup deque rotate alone       from collections import deque import random l    random random   for i in range 1000   dl   deque l       test deque rotate alone      dl rotate -1      timeit timeit test deque rotate alone  setup deque rotate alone    np roll  If you need to create nparrays  1M iterations   27 558452129364014 seconds  setup np roll with create npa       import numpy as np import random l    random random   for i in range 1000        test np roll with create npa       np roll l -1    implicit conversion of l to np nparray       If you already have nparrays   1M iterations   6 0491721630096436 seconds  setup np roll alone       import numpy as np import random l    random random   for i in range 1000   npa   np array l       test roll alone       np roll npa -1      timeit timeit test roll alone  setup np roll alone     Shift in place   Requires no type conversion  1M iterations   4 819645881652832 seconds  setup shift in place     import random l    random random   for i in range 1000   def shiftInPlace l  n       n   n   len l      head   l  n      l  n           l extend head      return l      test shift in place     shiftInPlace l -1       timeit timeit test shift in place  setup shift in place    l append l pop 0    Requires no type conversion  1M iterations   0 32483696937561035  setup append pop     import random l    random random   for i in range 1000        test append pop     l append l pop 0       timeit timeit test append pop  setup append pop

User · Answer

I was looking for in place solution to this problem  This solves the purpose in O k     def solution self  list  k       r len list -1     i   0     while i lt k          temp   list 0          list 0 r    list 1 r 1          list r    temp         i  1     return list

User · Answer

For a list X     a    b    c    d    e    f   and a desired shift value of shift less than list length  we can define the function list shift   as below  def list shift my list  shift       assert shift  lt  len my list      return my list shift     my list  shift    Examples    list shift X 1  returns   b    c    d    e    f    a   list shift X 3  returns   d    e    f    a    b    c

User · Answer

I don t know if this is  efficient   but it also works   x    1 2 3 4  x insert 0 x pop      EDIT  Hello again  I just found a big problem with this solution  Consider the following code   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    lt -- SHOULD NOT HAVE BIN CHANGED     The shift classlist   method executes the same code as my x insert 0 x pop   -solution  otherlist is a list indipendent from the class  After passing the content of otherlist to the MyClass classlist list  calling the shift classlist   also changes the otherlist list   CONSOLE OUTPUT   before shift       x classlist    1  2  3       otherlist    1  2  3  after shift       x classlist    3  1  2       otherlist    3  1  2   lt -- 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   lt -- SHOULD NOT HAVE BIN CHANGED    I use Python 2 7  I don t know if thats a bug  but I think it s more likely that I missunderstood something here   Does anyone of you know why this happens

User · Answer

I also got interested in this and compared some of the suggested solutions with perfplot  a small project of mine   It turns out that for   in range n       data append data pop 0    is by far the fastest method for small shifts n  For larger n  data n     data  n   isn t bad  Essentially  perfplot performs the shift for increasing large arrays and measures the time  Here are the results  shift   1   shift   100    Code to reproduce the plot  import numpy import perfplot import collections   shift   100   def list append data       return data shift     data  shift    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       for   in range shift           data append data pop 0       return data   perfplot save       quot shift100 png quot       setup lambda n  numpy random rand n  tolist        kernels  list append  roll  shift concatenate  collections deque  pop append       n range  2    k for k in range 7  20        xlabel  quot len data  quot

User · Answer

Numpy can do this using the roll command    gt  gt  gt  import numpy  gt  gt  gt  a numpy arange 1 10   Generate some data  gt  gt  gt  numpy roll a 1  array  9  1  2  3  4  5  6  7  8    gt  gt  gt  numpy roll a -1  array  2  3  4  5  6  7  8  9  1    gt  gt  gt  numpy roll a 5  array  5  6  7  8  9  1  2  3  4    gt  gt  gt  numpy roll a 9  array  1  2  3  4  5  6  7  8  9

User · Answer

For an immutable implementation  you could use something like this   def shift seq  n       shifted seq          for i in range len seq            shifted seq append seq  i-n    len seq        return shifted seq  print shift  1  2  3  4   1

User · Answer

I take this cost model as a reference   http   scripts mit edu  6 006 fall07 wiki index php title Python Cost Model  Your method of slicing the list and concatenating two sub-lists are linear-time operations  I would suggest using pop  which is a constant-time operation  e g    def shift list  n       for i in range n          temp   list pop           list insert 0  temp

User · Answer

This also depends on if you want to shift the list in place  mutating it   or if you want the function to return a new list   Because  according to my tests  something like this is at least twenty times faster than your implementation that adds two lists   def shiftInPlace l  n       n   n   len l      head   l  n      l  n           l extend head      return l   In fact  even adding a l   l    to the top of that to operate on a copy of the list passed in is still twice as fast   Various implementations with some timing at http   gist github com 288272

User · Answer

If efficiency is your goal   cycles  memory   you may be better off looking at the array module  http   docs python org library array html  Arrays do not have the overhead of lists     As far as pure lists go though  what you have is about as good as you can hope to do

User · Answer

Following function copies sent list to a templist  so that pop function does not affect the original list    def shift lst  n  toreverse False       templist          for i in lst  templist append i      if toreverse          for i in range n    templist    templist pop    templist     else          for i in range n    templist   templist  templist pop 0       return templist   Testing    lst    1 2 3 4 5  print  lst    lst  print  shift by 1    shift lst 1   print  lst    lst  print  shift by 7    shift lst 7   print  lst    lst  print  shift by 1 reverse    shift lst 1  True   print  lst    lst  print  shift by 7 reverse    shift lst 7  True   print  lst    lst    Output   lst   1  2  3  4  5  shift by 1   2  3  4  5  1  lst   1  2  3  4  5  shift by 7   3  4  5  1  2  lst   1  2  3  4  5  shift by 1 reverse   5  1  2  3  4  lst   1  2  3  4  5  shift by 7 reverse   4  5  1  2  3  lst   1  2  3  4  5

User · Answer

It depends on what you want to have happen when you do this    gt  gt  gt  shift  1 2 3   14    You might want to change your   def shift seq  n       return seq n   seq  n    to   def shift seq  n       n   n   len seq      return seq n     seq  n

User · Answer

I m  quot old school quot  I define efficiency in lowest latency  processor time and memory usage  our nemesis are the bloated libraries   So there is exactly one right way      def rotatel nums           back   nums pop 0          nums append back          return nums

User · Answer

Jon Bentley in Programming Pearls  Column 2  describes an elegant and efficient algorithm for rotating an n-element vector x left by i positions      Let s view the problem as transforming the array ab into the array   ba  but let s also assume that we have a function that reverses the   elements in a specified portion of the array  Starting with ab  we   reverse a to get arb  reverse b to get   arbr  and then reverse the whole   thing to get  arbr r    which is exactly ba  This results in the following code for   rotation   reverse 0  i-1  reverse i  n-1  reverse 0  n-1     This can be translated to Python as follows   def rotate x  i       i    len x      x  i    reversed x  i       x i     reversed x i        x      reversed x      return x   Demo    gt  gt  gt  def rotate x  i           i    len x          x  i    reversed x  i           x i     reversed x i            x      reversed x          return x       gt  gt  gt  rotate list  abcdefgh    1    b    c    d    e    f    g    h    a    gt  gt  gt  rotate list  abcdefgh    3    d    e    f    g    h    a    b    c    gt  gt  gt  rotate list  abcdefgh    8    a    b    c    d    e    f    g    h    gt  gt  gt  rotate list  abcdefgh    9    b    c    d    e    f    g    h    a

[python] Efficient way to rotate a list in python

Examples related to python

Examples related to list