map :: lower_bound()等效于python的dict类？

Question

我正在编写一些代码,要求我获取键的下限(为简单起见,忽略位于集合中最小键下方的键).

在C++中,使用std :: map(作为最具可比性的数据类型),我只需使用lower_bound()来返回迭代器.

我的Pythonfoo不是那么好,但我猜测(如果Python还没有办法做到这一点),这将是一个很好的使用lambda函数...

检索给定索引的下界键的Pythonic方法是什么？

如果问题太抽象,这就是我实际上要做的事情:

我有一个按日期索引的Python dict.我希望能够使用日期查找dict,并返回与指定键的下限关联的值.

片段如下:

mymap = { datetime.date(2007, 1, 5): 'foo',
          datetime.date(2007, 1, 10): 'foofoo',
          datetime.date(2007, 2, 2): 'foobar',
          datetime.date(2007, 2, 7): 'foobarbar' }

mydate = datetime.date(2007, 1, 7)

# fetch lbound key for mydate from mymap
def mymap_lbound_key(orig):
    pass # return the lbound for the key 

我真的不想循环键,寻找第一个键<=提供键,除非没有更好的选择......

Answer 1

Python的dict类没有这个功能; 你需要自己写.如果键已经排序了肯定会很方便,不是吗,所以你可以对它们进行二进制搜索并避免迭代它们全部？在这种情况下,我将看一下包中的sorteddict类blist.http://pypi.python.org/pypi/blist/

Answer 2

如果您因某种原因而超载日期，它可以比较事物，则进入bisect模块。

最小整数编码示例：

from bisect import bisect_left

data = {
    200 : -100,
    -50 : 0,
    51 : 100,
    250 : 200
}

keys = list(data.keys())

print data[  keys[ bisect_left(keys, -79) ]  ]

Answer 3

当我想要类似于 C++ 映射的东西时，我使用 SortedDict。您可以使用它irange来获取大于给定键的项目的迭代器——我认为这就是std::lower_bound工作原理。

代码：

from sortedcontainers import SortedDict
sd = SortedDict()
sd[105] = 'a'
sd[102] = 'b'
sd[101] = 'c'

#SortedDict is sorted on insert, like std::map
print(sd)

# sd.irange(minimum=<key>) returns an iterator beginning with the first key not less than <key>
print("min = 100", list(sd.irange(minimum=100)))
print("min = 102", list(sd.irange(minimum=102)))
print("min = 103", list(sd.irange(minimum=103)))
print("min = 106", list(sd.irange(minimum=106)))

输出：

SortedDict(None, 1000, {101: 'c', 102: 'b', 105: 'a'})
min = 100 [101, 102, 105]
min = 102 [102, 105]
min = 103 [105]
min = 106 []

Answer 4

仍然不确定“下限”是什么：查询日期之前/之后的最新日期？

无论如何，由于字典不会对其键强加固有的顺序，因此您需要不同的结构。将您的密钥存储在某种结构中，以保持它们排序并允许快速搜索。

最简单的解决方案是将排序的日期存储在（日期，值）列表中，然后进行二分搜索以放大所需的区域。如果您需要/想要更好的性能，我认为 B 树就是您所需要的。