有序字典中的最后一个元素

Question

我有一个类型为OrderedDict的od。我想访问它最近添加的(key, value)对。od.popitem(last=True)可以做到这一点，但会从od中删除该对，这不是我想要的。

有什么好的方法来实现这个目的？我能/应该这样做吗:

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

- max

Answer 1

使用next(reversed(od))是访问最近添加的元素的完美方式。类OrderedDict使用双向链表来存储字典项并实现了__reversed__()，因此这种实现方式可以以O(1)的时间复杂度访问所需的元素。是否值得为此简单操作子类化OrderedDict()可能会有争议，但这种方法实际上没有任何问题。

- Sven Marnach

---

@hobs: 是的，它只会给你键。如何根据键获取值留给读者练习。 :) - Sven Marnach

就此而言，O(2)和O(1)在渐近意义下是等价的。 - matt

在Python 3.5中，您可以使用next(reversed(od.values()))来获取最后一个值。 - UXkQEZ7

请注意，如果您想获取第一个元素，应使用next(iter(od))。 - BlackBear

难怪在Python 3.5中，你可以使用next(reversed(od.items()))来获取最后一个(key, value)对。 - mmj

Answer 2

天啊，我希望这一切都是内置功能...

这里有些东西可以节省你宝贵的时间。在 Python 3.7 中测试过。 od 是你的 OrderedDict。

# Get first key
next(iter(od))

# Get last key
next(reversed(od))

# Get first value
od[next(iter(od))]

# Get last value
od[next(reversed(od))]

# Get first key-value tuple
next(iter(od.items()))

# Get last key-value tuple
next(reversed(od.items()))

- Hubert Grzeskowiak

---

好的例子，只有一个观察值，不需要使用keys方法。 - Lucas Vazquez

所有这些操作的时间复杂度都是 O(1) 吗？ - KnightKnight

@KnightKnight，由于没有涉及排序或比较，并且大多数Python的集合方法应该是惰性的，我敢打赌是的。但在面试中不要只听我的话。 - Hubert Grzeskowiak

这对我来说应该是被接受的答案 ^^ - Nam G VU

Answer 3

timeit的一点小魔法可以在这里提供帮助...

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())

导致结果如下：

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

(在Python3.2和Ubuntu Linux上测试通过)

正如@SvenMarnach所指出的那样，你所描述的方法相比我能够想到的另外两种方法要高效得多。

- mgilson

Answer 4

你的想法很好，但默认的迭代器仅遍历键(key)，因此你的例子只会返回最后一个键。你实际想要的是：

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

这将提供(key, value)对，而不仅仅是你想要的键。

请注意，在Python 3.x之前的版本中，OrderedDict.items()返回一个列表，因此您不需要list()调用，但是较新版本返回字典视图对象，所以您需要。

编辑：如评论中所述，更快的操作是执行：

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

虽然我必须承认我在代码中发现这样更加丑陋（我从来不喜欢先获取键，然后分别获取值x[key]，我更喜欢获取(key, value)元组）- 取决于速度的重要性和您的喜好，您可能希望选择前一种选项。

- Gareth Latty

---

当然，这将是O(n)的操作。最好使用原始实现来获取键，并通过正常的字典访问获取值。(并且当你必须构建一个列表时，[-1]比next(reversed(...))更容易。) - Sven Marnach

你说得很对，已经更正了。太容易陷入一种解决问题的方式中。 - Gareth Latty