Geek asks and answers

O (1) indexable deque of integers in Python

what are my options? I need to call a lot append(on the right) and popleft(naturally, from the left end), but also read from the middle of the repository, which will grow steadily, by the nature of the algorithm. I would like to have all these operations in O(1).

I could implement it in C quite easily in an array with a circular address (what is this word?), Which would automatically increase when it is populated; but what about python? Pointers to other languages ​​are also appreciated (I understand that the “collection” tag is more oriented to Java, etc., and he would appreciate the comparison, but as a secondary goal).

I came from the background of Lisp and was amazed to learn that in Python, removing the head element from the list is an operation O(n). A dequemay be the answer, except for the documentation according to which access is O(n)in the middle. Is there anything else pre-built?

+5
source share
3 answers

You can get the cushioned O (1) data structure using two python lists, one of which contains the left half of deque and the other contains the right half. The front half is stored in reverse order, so the left end of the deck is at the end of the list. Something like that:

class mydeque(object):

  def __init__(self):
    self.left = []
    self.right = []

  def pushleft(self, v):
    self.left.append(v)

  def pushright(self, v):
    self.right.append(v)

  def popleft(self):
    if not self.left:
      self.__fill_left()
    return self.left.pop()

  def popright(self):
    if not self.right:
      self.__fill_right()
    return self.right.pop()

  def __len__(self):
    return len(self.left) + len(self.right)

  def __getitem__(self, i):
    if i >= len(self.left):
      return self.right[i-len(self.left)]
    else:
      return self.left[-(i+1)]

  def __fill_right(self):
    x = len(self.left)//2
    self.right.extend(self.left[0:x])
    self.right.reverse()
    del self.left[0:x]

  def __fill_left(self):
    x = len(self.right)//2
    self.left.extend(self.right[0:x])
    self.left.reverse()
    del self.right[0:x]

I am not 100% sure if the interaction between this code and the amortized performance of python lists actually results in O (1) for each operation, but my gut says so.

+7

lisp O (n).

Python list - , (popping tail - ).

, , () ; , datastructure list, , , .

- .

+3

The Python queue module can help you, although I'm not sure what access is O(1).

0
source

More articles:


All Articles