Более эффективный способ поиска значений словаря, ключи которых начинаются с того же префикса

Question

У меня есть словарь, ключи которого входят в наборы с одинаковым префиксом, например так:

d = { "key1":"valA", "key123":"valB", "key1XY":"valC",
      "key2":"valD", "key2-22":"valE" }

Учитывая строку запроса, мне нужно найти все значения, связанные с ключами, которые начинаются с этого префикса, например, для query="key1" мне нужно получить ["valA", "valB", "valC"]

Моя реализация ниже работает, но слишком медленно для большого количества запросов, так как словарь d имеет около 30 000 ключей, и большинство ключей имеют длину более 20 символов:

result = [d[s] for s in d.keys() if s.startswith(query)]

Есть ли более быстрый / более эффективный способ реализовать это?

Answer 1

Вы можете избежать создания промежуточного списка, созданного dict.keys() (в Python 2.x):

result = [d[key] for key in d if key.startswith(query)]

Но вы, скорее всего, захотите использовать дерево вместо словаря, поэтому вы можете найти все значения, связанные с ключом с общим префиксом (дерево похоже на дерево, основанное на префиксах).

Здесь вы можете найти несколько разных реализаций попыток.

Трия для клавиш "A", "to", "tea", "ted", "ten", "i", "in" и "inn". (источник википедии)

---

Давайте сравним время для разных решений:

# create a dictionary with 30k entries
d = {str(x):str(x) for x in xrange(1, 30001)}
query = '108'

# dict with keys()
%timeit [d[s] for s in d.keys() if s.startswith(query)]

    100 loops, best of 3: 8.87 ms per loop

---

# dict without keys()
%timeit [d[s] for s in d if s.startswith(query)]

    100 loops, best of 3: 7.83 ms per loop

# 11.72% improvement

---

# PyTrie (https://pypi.python.org/pypi/PyTrie/0.2)
import pytrie
pt = pytrie.Trie(d)

%timeit [pt[s] for s in pt.iterkeys(query)]

    1000 loops, best of 3: 320 µs per loop

# 96.36% improvement

---

# datrie (https://pypi.python.org/pypi/datrie/0.7)
import datrie
dt = datrie.Trie('0123456789')
for key, val in d.iteritems():
    dt[unicode(key)] = val

%timeit [dt[s] for s in dt.keys(unicode(query))]

    10000 loops, best of 3: 162 µs per loop

# 98.17% improvement

Answer 2

Вы можете использовать дерево суффиксов:

#!/usr/bin/env python2
from SuffixTree import SubstringDict # $ pip install https://github.com/JDonner/SuffixTree/archive/master.zip

d = { "key1":"valA", "key123":"valB", "key1XY":"valC",
      "key2":"valD", "key2-22":"valE" }

a = '\n' # anchor
prefixes = SubstringDict()
for key, value in d.items(): # populated the tree *once*
    prefixes[a + key] = value # assume there is no '\n' in key

for query in ["key1", "key2"]: # perform queries
    print query, prefixes[a + query]

Выход

key1 ['valC', 'valA', 'valB']
key2 ['valE', 'valD']

Answer 3

sortedContainers В lib есть реализация SortedDict, после того как вы отсортировали dict, вы можете использовать bisect_left, чтобы найти, с чего начать, bisect_right, чтобы найти последнюю позицию, а затем использовать irange, чтобы получить ключи в диапазоне:

from sortedcontainers import SortedDict
from operator import itemgetter
from itertools import takewhile


d = { "key1":"valA", "key123":"valB", "key1XY":"valC",
  "key2":"valD", "key2-22":"valE","key3":"foo" }

key = "key2"
d = SortedDict(sorted(d.items(), key=itemgetter(0)))
start = d.bisect_left(key)
print([d[key] for key in takewhile(lambda x: x.startswith("key2"), d.irange(d.iloc[start]]))
['valD', 'valE']

Как только вы поддерживаете sorteddict с помощью sorteddict, это намного эффективнее:

In [68]: l = ["key{}".format(randint(1,1000000)) for _ in range(100000)] 
In [69]: l.sort()    
In [70]: d = SortedDict(zip(l,range(100000)))

In [71]: timeit [d[s] for s in d.keys() if s.startswith("key2")]
10 loops, best of 3: 124 ms per loop

In [72]: timeit [d[s] for s in d if s.startswith("key2")]
10 loops, best of 3: 24.6 ms per loop

In [73]: %%timeit
key = "key2"
start = d.bisect_left(key)
l2 =[d[k] for k in takewhile(lambda x: x.startswith("key2"),d.irange(d.iloc[start]))]
   ....: 

100 loops, best of 3: 5.57 ms per loop