0

我有一个字典，其中包含键的 unix 纪元时间戳，如下所示：

lookup_dict = {
    1357899: {} #some dict of data
    1357910: {} #some other dict of data
}

除了，你知道，数以百万计的条目。我想一遍又一遍地对这个字典进行子集化。理想情况下，我希望能够在 R 中写出我能写的东西，比如：

lookup_value = 1357900
dict_subset = lookup_dict[key >= lookup_value]
# dict_subset now contains {1357910: {}}

但我承认，我找不到任何实际证据证明 Python 可以做到这一点，而无需以一种或另一种方式遍历每一行。如果我正确理解 Python（我可能不会），表单的键查找key in dict使用二进制搜索，因此非常快；有什么方法可以在字典键上进行二进制搜索？

4

2 回答 2

2

要在不迭代的情况下执行此操作，您将需要按排序顺序排列的键。然后你只需要对第一个进行二分搜索>= lookup_value，而不是检查每个>= lookup_value.

如果您愿意使用第三方库，那里有很多。首先想到的两个是bintrees（使用红黑树，如 C++、Java 等）和blist（使用 B+Tree）。例如，使用bintrees，它就像这样简单：

dict_subset = lookup_dict[lookup_value:]

这将与您希望的一样高效——基本上，它O(log N)在使用该子集的任何成本之上添加了一个搜索。（当然通常你想要对那个子集做的是迭代整个事情，无论如何最终都是 O(N) ......但也许你正在做一些不同的事情，或者这个子集可能只是 1000000 个中的 10 个键。）

当然有一个权衡。对基于树的映射的随机访问是 O(log N) 而不是“通常是 O(1)”。此外，您的密钥显然需要完全排序，而不是可散列（而且自动检测和引发漂亮的错误消息要困难得多）。

如果你想自己构建它，你可以。你甚至不一定需要一棵树。只是一个排序list旁边的键dict。正如 JonClements 建议的那样，您可以使用 stdlib 中list的模块来维护。bisect您可能想要完成bisect一个排序列表对象——或者，更好的是，获取 ActiveState 或 PyPI 上的一个食谱来为您完成。然后，您可以将排序列表和dict一起包装到一个对象中，这样您就不会在不更新另一个的情况下意外更新一个。bintrees然后，如果您愿意，您可以将界面扩展为与 一样好。

于 2013-02-15T01:27:40.510 回答
0

使用以下代码将解决

some_time_to_filter_for = # blah unix time
# Create a new sub-dictionary
sub_dict = {key: val for key, val in lookup_dict.items() 
            if key >= some_time_to_filter_for}

基本上我们只是遍历字典中的所有键并给定时间过滤掉，因为我们将所有大于或等于该值的键放入我们的新字典中

于 2013-02-15T00:54:55.020 回答