map :: lower_bound（）等价于python的dict类吗？

我正在写一些代码，要求我获取密钥的下界（为了简单起见，忽略位于集合中最小密钥下方的密钥）。在C++中，使用std :: map（作为最可比较的数据类型），我只是简单地使用lower_bound（）来返回迭代器。map :: lower_bound（）等价于python的dict类吗？

我Pythonfoo不是很大，但我猜测，（如果Python中还没有这样做的一种方式），这将是一个良好的使用lambda函数的...

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

如果问题是过于抽象，这是我真正想要做的事：

我有一个Python字典按日期索引。我希望能够使用日期来查找字典，并返回与指定键的下边相关联的值。

摘录如下：

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

我真的不希望遍历键，寻找第一个关键< =提供关键的，除非有没有更好的选择......

来源

2012-02-18 Homunculus Reticulli

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

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

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

来源

2012-02-18 18:18:20 alexis

Python的dict类没有此功能;你需要自己写。如果密钥已经被排序，肯定会很方便，不是吗？所以你可以对它们进行二分搜索，避免迭代它们？在这方面，我会看看blist包中的sorteddict类。 http://pypi.python.org/pypi/blist/

来源

2012-02-18 18:24:58 kindall

如果你有日期以某种方式超载，它可以比较东西看看bisect module。

最小整数编码例：

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

来源

2014-06-24 15:44:18 Alex

当我想要的东西，类似于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 []

来源

2017-02-23 19:24:13 MatrixManAtYrService

map :: lower_bound（）等价于python的dict类吗？

回答

相关问题