Поиск словарных ключей python

Я хочу знать, как я могу выполнить какой-то индекс для ключей из словаря python. Словарь содержит ок. 400 000 элементов, поэтому я стараюсь избегать линейного поиска.

В основном, я пытаюсь найти, если userinput находится внутри любой из клавиш dict.

for keys in dict:
    if userinput in keys:
        DoSomething()
        break

Это будет пример того, что я пытаюсь сделать. Есть ли способ искать более прямой путь, без цикла? или что было бы более эффективным способом.

Разъяснение: userinput не является тем, чем будет ключ, например userinput может быть log, тогда как ключ logfile

Изменить: любое создание списка/кешей, предварительная обработка или организация, которые могут быть выполнены до поиска, приемлемы. Единственное, что нужно быстро, это поиск ключа.

Ответы

Ответ 1

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

Ответ 2

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

Однако, если у вас 400 000 записей, и вы хотите ускорить поиск, я бы предложил использовать базу данных SQLite. Тогда вы можете просто сказать SELECT * FROM TABLE_NAME WHERE COLUMN_NAME LIKE '%userinput%';. Посмотрите документацию для модуля Python sqlite3 здесь.

Другой вариант - использовать выражение генератора, поскольку они почти всегда быстрее, чем эквивалент для циклов.

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

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

Ответ 3

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

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

Ответ 4

Вы можете объединить все ключи в одну длинную строку с подходящим символом разделителя и использовать метод 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

Ответ 5

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 ('путь//в//something/[0-9a-z]') для расширенного поиска.