如果它是任何其他键中的子字符串,请删除字典键

Question

我正在学习Python.我遇到了性能问题.对于单个字典,我想删除密钥if

• a键是另一个键中的子字符串

如果,我不想删除密钥

• 关键子串本身就是

我的密钥是唯一的字符串,大多数长度在3-50个字符之间.我正在使用的词典有100,000个或更多的项目,进行了数十亿次比较.由于这是一个O(n ^ 2)问题,我应该停止尝试优化此代码吗？还是有空间在这里取得进展？

字典是可取的,但我对其他类型开放.

例如:'hello'包含'he'和'ell'.我想在保持'你好'的同时删除'he'和'ell'键.我想在其他键的中间删除前缀,后缀和键子串.

密钥一个接一个地生成并添加到字典中.然后reduce_dict(dictionary)运行.我的假设是:在将它们添加到字典中时进行的测试与后面的函数测试一样慢,如下面的代码所示.

def reduce_dict(dictionary):
    reduced = dictionary.copy()
    for key in dictionary:
        for key2 in dictionary:
            if key != key2:
                if key2 in key:
                    reduced.pop(key2, 0)
    return reduced

Answer 1

我认为您可以以稍微优化的方式创建一个“好”键列表（=那些不是其他键的子字符串）：

# keys = yourDict.keys(), e.g.
keys = ['low', 'el', 'helloworld', 'something', 'ellow', 'thing', 'blah', 'thingy']

# flt is [[key, is_substring],...] sorted by key length reversed
flt = [[x, 0] for x in sorted(keys, key=len, reverse=True)]

for i in range(len(flt)):
    p = flt[i]
    if p[1]:  # already removed
        continue
    for j in range(i + 1, len(flt)): # iterate over shorter strings
        q = flt[j]
        if not q[1] and q[0] in p[0]: # if not already removed and is substring
            q[1] = 1  # remove

goodkeys = set(x[0] for x in flt if not x[1])
print goodkeys # e.g ['helloworld', 'something', 'thingy', 'blah']

现在删除是微不足道的：

newdict = {k:olddict[k] for k in goodkeys}