Поиск ключей словаря python

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

Если вам нужно найти только ключи, начинающиеся с префикса, вы можете использовать бинарный поиск. Что-то вроде этого выполнит эту работу:

import bisect
words = sorted("""
a b c stack stacey stackoverflow stacked star stare x y z
""".split())
n = len(words)
print n, "words"
print words
print
tests = sorted("""
r s ss st sta stack star stare stop su t
""".split())
for test in tests:
    i = bisect.bisect_left(words, test)
    if words[i] < test: i += 1
    print test, i
    while i < n and words[i].startswith(test):
        print i, words[i]
        i += 1

Вывод:

12 words
['a', 'b', 'c', 'stacey', 'stack', 'stacked', 'stackoverflow', 'star', 'stare',
'x', 'y', 'z']

r 3
s 3
3 stacey
4 stack
5 stacked
6 stackoverflow
7 star
8 stare
ss 3
st 3
3 stacey
4 stack
5 stacked
6 stackoverflow
7 star
8 stare
sta 3
3 stacey
4 stack
5 stacked
6 stackoverflow
7 star
8 stare
stack 4
4 stack
5 stacked
6 stackoverflow
star 7
7 star
8 stare
stare 8
8 stare
stop 9
su 9
t 9

Нет. Единственный способ найти строку в словарных ключах — просмотреть каждый ключ. Что-то вроде того, что вы предложили, - единственный способ сделать это со словарем.

filteredKeys = (key for key in myDict.keys() if userInput in key)
for key in filteredKeys:
    doSomething()

EDIT: Если, как вы говорите, вас не волнуют разовые затраты, используйте базу данных. SQLite должен делать то, что вы хотите, почти идеально.

Я провел несколько тестов, и, к моему удивлению, наивный алгоритм на самом деле в два раза быстрее, чем версия, использующая понимание списков, и в шесть раз быстрее, чем версия, управляемая SQLite. В свете этих результатов мне пришлось бы пойти с @Mark Byers и порекомендовать Trie. Я разместил тест ниже, на случай, если кто-то захочет попробовать.

import random, string, os
import time
import sqlite3

def buildDict(numElements):
    aDict = {}
    for i in xrange(numElements-10):
        aDict[''.join(random.sample(string.letters, 6))] = 0

    for i in xrange(10):
        aDict['log'+''.join(random.sample(string.letters, 3))] = 0

    return aDict

def naiveLCSearch(aDict, searchString):
    filteredKeys = [key for key in aDict.keys() if searchString in key]
    return filteredKeys

def naiveSearch(aDict, searchString):
    filteredKeys = []
    for key in aDict:
        if searchString in key: 
            filteredKeys.append(key)
    return filteredKeys

def insertIntoDB(aDict):
    conn = sqlite3.connect('/tmp/dictdb')
    c = conn.cursor()
    c.execute('DROP TABLE IF EXISTS BLAH')
    c.execute('CREATE TABLE BLAH (KEY TEXT PRIMARY KEY, VALUE TEXT)')
    for key in aDict:
        c.execute('INSERT INTO BLAH VALUES(?,?)',(key, aDict[key]))
    return conn

def dbSearch(conn):
    cursor = conn.cursor()
    cursor.execute("SELECT KEY FROM BLAH WHERE KEY GLOB '*log*'")
    return [record[0] for record in cursor]

if __name__ == '__main__':
    aDict = buildDict(400000)
    conn = insertIntoDB(aDict)
    startTimeNaive = time.time()
    for i in xrange(3):
        naiveResults = naiveSearch(aDict, 'log')
    endTimeNaive = time.time()
    print 'Time taken for 3 iterations of naive search was', (endTimeNaive-startTimeNaive), 'and the average time per run was', (endTimeNaive-startTimeNaive)/3.0

    startTimeNaiveLC = time.time()
    for i in xrange(3):
        naiveLCResults = naiveLCSearch(aDict, 'log')
    endTimeNaiveLC = time.time()
    print 'Time taken for 3 iterations of naive search with list comprehensions was', (endTimeNaiveLC-startTimeNaiveLC), 'and the average time per run was', (endTimeNaiveLC-startTimeNaiveLC)/3.0

    startTimeDB = time.time()
    for i in xrange(3):
        dbResults = dbSearch(conn)
    endTimeDB = time.time()
    print 'Time taken for 3 iterations of DB search was', (endTimeDB-startTimeDB), 'and the average time per run was', (endTimeDB-startTimeDB)/3.0


    os.remove('/tmp/dictdb')

Для справки, мои результаты были такими:

Time taken for 3 iterations of naive search was 0.264658927917 and the average time per run was 0.0882196426392
Time taken for 3 iterations of naive search with list comprehensions was 0.403481960297 and the average time per run was 0.134493986766
Time taken for 3 iterations of DB search was 1.19464492798 and the average time per run was 0.398214975993

Все время указано в секундах.

Вы можете объединить все ключи в одну длинную строку с подходящим символом-разделителем и использовать метод find строки. Это довольно быстро.

Возможно, этот код будет полезен для вас. Метод search возвращает список значений словаря, ключи которых содержат подстроку key.

class DictLookupBySubstr(object):
    def __init__(self, dictionary, separator='\n'):
        self.dic = dictionary
        self.sep = separator
        self.txt = separator.join(dictionary.keys())+separator

    def search(self, key):
        res = []
        i = self.txt.find(key)
        while i >= 0:
            left = self.txt.rfind(self.sep, 0, i) + 1
            right = self.txt.find(self.sep, i)
            dic_key = self.txt[left:right]
            res.append(self.dic[dic_key])
            i = self.txt.find(key, right+1)
        return res

dpath может легко решить эту проблему.

http://github.com/akesterson/dpath-python

$ easy_install dpath
>>> for (path, value) in dpath.util.search(MY_DICT, "glob/to/start/{}".format(userinput), yielded=True):
>>> ...    # (do something with the path and value)

Вы можете передать eglob ('path//to//something/[0-9a-z]') для расширенного поиска.

Возможно, использование has_key также решит эту проблему.

http://docs.python.org/release/2.5.2/lib/typesmapping.html