Могу ли я сохранить новые слова в словаре, сопоставив ключ в качестве префикса

Question

У меня в словаре сказано:

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

К вашему сведению, это не задание.

Answer 1

Вы можете попробовать:

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

def _add(_str):
    for _key in _dict.keys(): # loop _dict keys
        if _str.startswith(_key): # check if _str starts with _dict _key
            _dict[_key].append(_str) # append _str to _dict based on _key

_add("foofoo")
_add("barbar")
_add("foobarbar")
_add("notMatchingAnyKey")

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

---

Ideone Demo

Answer 2

Если вы используете dict, то да, вам придется перебирать все ключи, чтобы найти любой, который соответствует.Dicts построены на хеш-таблицах, а хеш-функции не имеют никакого понятия «начинается с» или «закрывается», чтобы использовать их в своих интересах (фактически, они специально разработаны, чтобы давать очень разные выходные данные для близких входов).

Совсем не сложно делать то, что вы хотите:

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

Но неэффективно, если диктат большой, потому что вы выполняете линейный поиск.

---

Вы можете сделать его линейным по длине ключа, а не по длине слова (который на самом деле будет медленнее в вашем тестовом примере, но, вероятно, быстрее в большинстве случаев).случаи, когда производительность имеет значение):

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-дерево, skiplist,три или даже простой старый список, сохраненный в отсортированном порядке.Большинство реализаций таких типов, которые вы можете найти в PyPI или хранилище рецептов ActiveState, имеют метод для поиска места вставки для ключа в отсортированном порядке.Или, если вы используете простой старый список, просто используйте модуль bisect в stdlib.Просто проверьте ключ перед тем местом вставки, и он либо начинается с вашего ключа, либо ничего не делает.

Например, с 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

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

Answer 3

Вы можете выполнить сопоставление префиксов с помощью функции, подобной:

Код:

def append_longest_prefix(data_dict, to_append):
    for i in range(1, len(to_append)):
        if to_append[:-i] in data_dict:
            data_dict[to_append[:-i]].append(to_append)
            return

Тестовый код:

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

append_longest_prefix(data, 'foofoo')
append_longest_prefix(data, 'barbar')
append_longest_prefix(data, 'foobarbar')
append_longest_prefix(data, 'notMatchingAnyKey')

print(data)

data = {'foo' : ['foofoo'], 'foobar' : [], 'bar' : ['barbar']}
append_longest_prefix(data, 'foobarbar')
print(data)

Результат:

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

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