Last element in OrderedDict

问题:

I have od of type OrderedDict. I want to access its most recently added (key, value) pair. od.popitem(last = True) would do it, but would also remove the pair from od which I don't want.

What's a good way to do that? Can /should I do this:

class MyOrderedDict(OrderedDict):
  def last(self):
    return next(reversed(self))

回答1:

Using next(reversed(od)) is a perfect way of accessing the most-recently added element. The class OrderedDict uses a doubly linked list for the dictionary items and implements __reversed__(), so this implementation gives you O(1) access to the desired element. Whether it is worthwhile to subclass OrderedDict() for this simple operation may be questioned, but there's nothing actually wrong with this approach.

回答2:

A little magic from timeit can help here...

from collections import OrderedDict
class MyOrderedDict1(OrderedDict):
  def last(self):
    k=next(reversed(self))
    return (k,self[k])

class MyOrderedDict2(OrderedDict):
  def last(self):
     out=self.popitem()
     self[out[0]]=out[1]
     return out

class MyOrderedDict3(OrderedDict):
  def last(self):
     k=(list(self.keys()))[-1]
     return (k,self[k])

if __name__ == "__main__":
  from timeit import Timer

  N=100

  d1=MyOrderedDict1()
  for i in range(N): d1[i]=i

  print ("d1",d1.last())

  d2=MyOrderedDict2()
  for i in range(N): d2[i]=i

  print ("d2",d2.last())

  d3=MyOrderedDict3()
  for i in range(N): d3[i]=i

  print("d3",d3.last())



  t=Timer("d1.last()",'from __main__ import d1')
  print ("OrderedDict1",t.timeit())
  t=Timer("d2.last()",'from __main__ import d2')
  print ("OrderedDict2",t.timeit())
  t=Timer("d3.last()",'from __main__ import d3')
  print ("OrderedDict3",t.timeit())

results in:

d1 (99, 99)
d2 (99, 99)
d3 (99, 99)
OrderedDict1 1.159217119216919
OrderedDict2 3.3667118549346924
OrderedDict3 24.030261993408203

(Tested on python3.2, Ubuntu Linux).

As pointed out by @SvenMarnach, the method you described is quite efficient compared to the other two ways I could cook up.

回答3:

Your idea is fine, however the default iterator is only over the keys, so your example will only return the last key. What you actually want is:

class MyOrderedDict(OrderedDict):
    def last(self):
        return list(self.items())[-1]

This gives the (key, value) pairs, not just the keys, as you wanted.

Note that on pre-3.x versions of Python, OrderedDict.items() returns a list, so you don't need the list() call, but later versions return a dictionary view object, so you will.

Edit: As noted in the comments, the quicker operation is to do:

class MyOrderedDict(OrderedDict):
    def last(self):
        key = next(reversed(self))
        return (key, self[key])

Although I must admit I do find this uglier in the code (I never liked getting the key then doing x[key] to get the value separately, I prefer getting the (key, value) tuple) - depending on the importance of speed and your preferences, you may wish to pick the former option.