Нет.Единственный способ поиска строки в словарных ключах - это поиск по каждому ключу.Что-то вроде того, что вы предложили, - единственный способ сделать это с помощью словаря.
Однако, если у вас 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()
РЕДАКТИРОВАТЬ: Если, как вы говорите, вам не нужны разовые расходы, используйте базу данных.SQLite должен делать то, что вы хотите, черт возьми, почти идеально.
Я сделал несколько тестов, и, к моему удивлению, наивный алгоритм на самом деле в два раза быстрее, чем версия, использующая списки и six * 1018.* в разы быстрее, чем версия на основе 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
Часовой пояс в секундах.