3

我有一个字典'vcomments'，其中的键是非顺序整数。在遍历键时，我需要按排序或反向排序的顺序进行。目前我使用

for key_pt in sorted(self.view.vcomments.iterkeys()):

但我还需要找到超出或之前某个数字的那些键（或下一个键）：

    if direction == 'down':
        sorted_pts = (key_pt for key_pt in sorted(self.view.vcomments.iterkeys()) if key_pt > curr_pt)
    else:
        sorted_pts = (key_pt for key_pt in reversed(sorted(self.view.vcomments.iterkeys())) if key_pt < curr_pt)
    try:
        next_pt = sorted_pts.next()
    except StopIteration:

  1. 我是否可以创建一个迭代器类（使用迭代器协议）来存储字典并使我能够以正向或反向顺序循环它们？我假设/猜测我可能需要首先分配一个属性值，该值将指示下一个循环是否应该是正向/反向。

  2. 我可以在我的迭代器类中包含一个生成器函数（嵌套），这将使我能够检索下一个键吗？也就是说，超出或之前提供的整数？

  3. 同样，我是否有办法提供起点和终点并检索落在这些值之间的所有键（按排序顺序）？

对于提出三个（尽管相关）问题，我深表歉意——第一个问题的答案会给我一个开始。而且我并没有粗鲁地期待一个完整的解决方案，只是表明这些对我来说是否是可行的目标。

补充：我仍然需要能够通过其键检索单个特定的字典项。

4

4 回答 4

4

我认为满足您需求的最佳数据结构是跳过列表。我从来没有实现过——一直想要——但在我看来，它拥有你需要的所有东西。

  1. 跳过列表按排序顺序存储其项目。使基本列表成为双向链表将允许在 O(n) 中进行正向和反向迭代。

  2. 跳过列表允许 O(log n) 的插入、修改、删除和搜索。这不像字典那么快，但在我看来，如果你需要按排序顺序存储的项目，字典会给你带来麻烦——甚至是OrderedDict，除非你很少添加键。

  3. 通过上面维基百科文章中描述的一些修改，即使是索引访问也可以在 O(log n) 中实现。

这里有一个 Python 实现——可能还有其他实现。

但是，您的一些评论表明您可能满足于简单地迭代字典的排序副本，而您只是试图清理上面的代码。所以这是一种解决方法。这很幼稚，但这是一个起点。这假设你对 O(n) 搜索时间和 O(n log n) 迭代时间完全没问题，这都是次优的......

>>> class SortIterDict(dict):
...     def __iter__(self):
...         return iter(sorted(super(SortIterDict, self).__iter__()))
...     def __reversed__(self):
...         return reversed(tuple(iter(self)))
...     def get_next(self, n):
...         return next((x for x in iter(self) if x > n), None)
...     def get_prev(self, n):
...         return next((x for x in reversed(self) if x < n), None)
... 
>>> d = SortIterDict({'d':6, 'a':5, 'c':2})
>>> list(d)
['a', 'c', 'd']
>>> list(reversed(d))
['d', 'c', 'a']
>>> d.get_next('b')
'c'
>>> d.get_prev('b')
'a'
于 2012-04-26T23:02:20.753 回答
2

首先，你应该注意到你需要一个更好的数据结构。Python dicts 根本没有顺序，OrderedDict只是保持插入顺序（因此您需要在每次键更改时重新排序）。一个排序的字典blist.sorteddict，甚至一个排序的列表，blist.sortedlist可能更适合您的需求。

我是否可以创建一个迭代器类（使用迭代器协议）来存储字典并使我能够以正向或反向顺序循环它们？我假设/猜测我可能需要首先分配一个属性值，该值将指示下一个循环是否应该是正向/反向。

您在这里不需要单独的迭代器类。您可以通过内置reversed函数获得免费的前向迭代和后向迭代：

for key in mydict:
  # do something

for key in reversed(mydict.keys()):
  # do something

我可以在我的迭代器类中包含一个生成器函数（嵌套），这将使我能够检索下一个键吗？也就是说，超出或之前提供的整数？

当然，itertools有很多功能可以让你做这样的事情：

from itertools import dropwhile, takewhile
# find next key beyond 4
next(dropwhile(lambda x: x <= 4, mydict))
# find last key before 20
next(dropwhile(lambda x: x >= 20, reversed(mydict.keys()))

您还可以将其打包成一个函数：

def first_beyond(pivot, seq):
  next(dropwhile(lambda x: x <= pivot, seq))

first_beyond(4, mydict)
first_beyond(20, reversed(mydict.keys()))

同样，我是否有办法提供起点和终点并检索落在这些值之间的所有键（按排序顺序）？

您可以轻松地为此构建一个通用工具：

from itertools import dropwhile, takewhile
def between(begin, end, seq):
  return takewhile(lambda x: x <= end, 
                   dropwhile(lambda x: x < begin, seq))

像这样使用：

>>> list(between(4, 30, [1,2,4,8,16,32]))
[4, 8, 16]

编辑：如果您只需要偶尔检查排序的键，您可以将它们转换为排序列表并使用它们。成语和上面一样：

keys = sorted(mydict)

# forward and backward iteration
for k in keys:
  # ...
for k in reversed(keys):
  # ...

# function that returns a forward or backward iterator based on an argument
def forward_or_backward(seq, forward=True):
  for x in (iter if forward else reversed)(seq):
    yield x

# random access inside a loop
for i, key in enumerate(keys):
  # next element
  key[i+1]

# the between and first_beyond functions above also work for lists

您的其余功能可以从这些部分粘合在一起。请注意，创建一个特殊的类是不明智的，因为我们可以以一种足够通用的方式编写函数，以便它们适用于任何可迭代的对象，而不仅仅是您的键列表。

于 2012-04-26T22:26:42.267 回答
1

在这种情况下，我倾向于以两种不同的方式存储部分数据。

如果您保留在您的 dict 周围，但添加了一个由 int 索引的列表，该列表会显示您的 dict 的键（r 值？）？这将为您提供您可能需要的随机访问（我假设您有 dict 是有原因的），以及您似乎需要添加的前后行为。

如果你走这条路，你可能会将它全部包装在一个类中，这样你就不会在你的代码中分散双重更新。

采用 treap 或红黑树实现，并对其进行修改以让您指定一个键，并在下一个或前一个键处取回键、值对，这可能是可行的。如果您经常插入或删除值，则其中之一可能会更好。

于 2012-04-26T22:17:03.523 回答
0

似乎一个有序的字典可能会给你你想要的。文档在这里。

于 2012-04-26T22:33:24.907 回答