La búsqueda de Claves del Diccionario de python

Quiero saber cómo puedo realizar algún tipo de índice de claves de un diccionario de python. El diccionario contiene aprox. 400.000 artículos, así que estoy tratando de evitar una búsqueda lineal.

Básicamente, estoy tratando de encontrar si el userinput está dentro de cualquiera de los dict claves.

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

Que sería un ejemplo de lo que estoy tratando de hacer. Es allí una manera de buscar en una forma más directa, sin necesidad de un bucle ? o lo que sería una forma más eficiente.

Aclaración: La userinput no es exactamente lo que la clave será, por ejemplo, la userinput podría ser log, mientras que la clave es logfile

Edición: cualquier lista/creación de la caché, pre-procesamiento o la organización de que se puede hacer antes de la búsqueda es aceptable. La única cosa que necesita ser rápida es la búsqueda de la clave.

Cuando todos los disponibles (y viable) algoritmos han inaceptable complejidad, es el momento de replantear el problema de la estructura de datos utilizada. Hay (relativamente exóticos) estructuras de datos fuzzy cadena coincidente, aunque no sé si hay alguna para abritary subcadenas.
Pero es el userinput siempre al principio de la clave?
¿cómo es de malo? El uso de plural ‘claves’ es confuso, pero 'foo' in 'foobar' is True. Parece correcto para mí.
Todavía me pregunto si userinput es siempre un prefijo, como en el ‘registro’/’archivo de registro’ ejemplo, o si userinput es arbitraria subcadena, como en ‘archivo’/’longfilename’. Esto hace una gran diferencia.
subcadena 🙂 necesitan la flexibilidad

OriginalEl autor Trent | 2011-03-02

6 respuestas

  1. 6

    Si sólo necesita para encontrar las claves que comienzan con un prefijo y, a continuación, puede utilizar un trie. Estructuras de datos más complejas que existen para encontrar claves que contienen una subcadena dentro de ellos, pero ocupan mucho más espacio para almacenar por lo que es un espacio-tiempo de trade-off.

    Ah, “trie” — supongo que la palabra que yo quería para mi comentario anterior. +1
    No la construcción de la “trie” ser en sí muy costoso? Usted todavía tiene que recorrer todo el diccionario, y en ese punto, no va a ser sustancialmente mejor que el ingenuo solución, y podría ser peor para el caso promedio.
    Kanchi, sería costoso al principio, pero usted sólo tiene que hacerlo una vez, ¿verdad? Todos los futuros prefijo búsquedas iba a ser rápido, porque se vería en el trie para un partido o de los partidos. (Es de suponer que a usted le presente una lista de posibles coincidencias si hay más de uno en el trie, o tiene algún otro algoritmo para la selección de uno de ellos.) Además, el trie podría ser construido en avance y en escabeche; y si el dict cambios, podría ser actualizado fácilmente & escabeche de nuevo en la salida del programa.
    No importa, he publicado que antes de ver el post actualizado por el OP.

    OriginalEl autor Mark Byers

  2. 3

    Si sólo necesita para encontrar las claves que comienzan con un prefijo y, a continuación, puede utilizar una búsqueda binaria. Algo como esto hará el trabajo:

    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

    De salida:

    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
    +1: enfoque Agradable.

    OriginalEl autor John Machin

  3. 3

    No. La única manera de buscar una cadena en el diccionario de claves es buscar en cada tecla. Algo parecido a lo que he sugerido es la única manera de hacerlo con un diccionario.

    Sin embargo, si usted tiene 400.000 registros y desea acelerar su búsqueda, me gustaría sugerir el uso de una base de datos SQLite. A continuación, puede simplemente decir SELECT * FROM TABLE_NAME WHERE COLUMN_NAME LIKE '%userinput%';. Consulte la documentación de Python sqlite3 módulo aquí.

    Otra opción es utilizar un generador de expresión, ya que estos son casi siempre más rápido que el equivalente para los bucles.

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

    EDICIÓN: Si, como usted dice, que no se preocupan por los costos, el uso de una base de datos. SQLite debe hacer lo que quieres maldito cerca de la perfección.

    Hice algunos puntos de referencia, y para mi sorpresa, el ingenuo algoritmo en realidad es dos veces tan rápido como una versión de la lista de comprensión y seis veces tan rápido como una SQLite-impulsado por la versión. A la luz de estos resultados, tendría que ir con @Mark Byers y recomendar un Trie. He publicado el punto de referencia a continuación, en caso de que alguien quiera darle una oportunidad.

    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')

    Para el registro, mis resultados fueron:

    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

    Todas las horas están en segundos.

    Acorto la “sin Embargo, si usted tiene 400.000 registros, el uso de una base de datos.”
    “Otra opción es utilizar la lista de comprensión, ya que estos son casi siempre más rápido que el equivalente de bucles.” Fuente?
    No sé la fuente, pero creo que Chinmay es correcto, simplemente basado en la experiencia.
    wiki.python.org/moin/PythonSpeed/PerformanceTips . Mira en la sección sobre los nudos.
    Prefiero dejarlo ahí, como me parece que hace el código más evidentes en cuanto a su intención. Me doy cuenta de que no es necesario, aunque.

    OriginalEl autor Chinmay Kanchi

  4. 1

    Podría unir todas las claves en una cadena larga con un adecuado carácter separador y el uso de la find método de la cadena. Que es bastante rápido.

    Quizás este código es útil para usted. El search método devuelve una lista de diccionario cuyos valores claves contienen la subcadena 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

    OriginalEl autor Janne Karila

  5. 1

    dpath pueden resolver fácilmente.

    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)

    Se puede pasar un eglob (‘ruta//a//algo/[0-9a-z]’) para la búsqueda avanzada.

    OriginalEl autor Andrew Kesterson

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *