时间戳

首页 > 解决方案 > 我可以通过匹配键作为前缀在字典中保留新单词吗

python - 我可以通过匹配键作为前缀在字典中保留新单词吗

问题描述

我有一本字典说，

stringToListDict = {'foo' : [], 'bar' : []}

现在让我们说我们做

+foofoo

stringToListDict = {'foo' : ['foofoo'], 'bar' : []}

+barbar

stringToListDict = {'foo' : ['foofoo'], 'bar' : ['barbar']}

+foobarbar

stringToListDict = {'foo' : ['foofoo', 'foobarbar'], 'bar' : ['barbar']}

+notMatchingAnyKey

Simply discard this new string.

如您所见，添加的字符串通过匹配键作为前缀进行。

我可以通过一个一个地遍历字典中的每个键来做到这一点，直到我得到一个匹配的前缀。但是还有其他优雅或有效的方法吗？您不必担心边缘情况，例如在以下情况下会发生什么：

stringToListDict = {'foo' : ['foofoo'], 'foobar' : [], 'bar' : ['barbar']}

then +foobarbar

仅供参考，这不是任务。

标签： pythonalgorithmdictionaryoptimization

解决方案

如果您使用的是字典，那么是的，您将必须迭代所有键以找到任何匹配项。字典是建立在哈希表上的，哈希函数没有任何“开始于”或“关闭”的概念可以利用（事实上，它们专门设计用于为关闭输入提供非常不同的输出）。

做你想做的事一点都不难：

for k, v in d.items():
    if s.startswith(k):
        v.append(s)
        break
else:
    # whatever you want to do if no prefix exists

但是如果 dict 很大，效率会很低，因为你在做线性搜索。

您可以使其与键的长度成线性关系，而不是 dict 的长度（这在您的测试用例中实际上会更慢，但在大多数性能重要的情况下可能会更快）：

for i in range(len(s), 0, -1):
    try:
        d[k[:i]].append(s)
        break
    except KeyError:
        pass
else:
    # whatever you want to do if no prefix exists

但是，如果您需要最佳效率，则需要查看对数数据结构，例如平衡二叉搜索树、b-tree、skiplist、trie，甚至只是按排序顺序保存的普通旧列表。您可以在 PyPI 或 ActiveState 配方存储库上找到的大多数此类类型的实现都将具有一种按排序顺序查找键的插入位置的方法。或者，如果您使用的是普通的旧列表，只需使用标准库中的bisect模块。只需在该插入位置之前检查密钥，它要么从您的密钥开始，要么什么都不做。

例如，使用sortedcontainers.SortedDict：

i = d.bisect(s)
if d.iloc[i].startswith(s):
    d[d.iloc[i]].append(s)
else:
    # whatever you want to do if no prefix exists

如果您有大量、密集的键集并且您正在执行大量查询和插入操作，那么前缀树可能是最有效的。但是对于不同的特征，其他人可能会胜出。所以，如果这很重要，你会想尝试一些并进行测试。

推荐阅读