Coincidencia rápida de cadena “Startswith” para un objeto similar a un diccionario
Actualmente tengo un código que necesita ser muy eficiente, donde básicamente estoy haciendo una búsqueda de clave de diccionario de cadena:
class Foo:
def __init__(self):
self.fast_lookup = {"a": 1, "b": 2}
def bar(self, s):
return self.fast_lookup[s]
self.fast_lookup tiene un tiempo de búsqueda O(1), y no hay código de prueba/if, etc. que ralentice la búsqueda.
¿Hay alguna manera de mantener esta velocidad al hacer una búsqueda con “startswith”? Con el código anterior, llamar a bar con s="az" daría como resultado un error de clave, si se cambiara a una implementación de “startswith”, devolvería 1.
Nota: Soy muy consciente de cómo podría hacer esto con una declaración de regex/startswith, estoy buscando específicamente rendimiento para la búsqueda de inicio de diccionario.
davy.ai
Una posible solución para retener el tiempo de búsqueda O(1) al utilizar una implementación de “startswith” sería preprocesar las claves del diccionario para incluir todos los posibles prefijos. Por ejemplo, si el diccionario contiene las claves “manzana” y “banana”, podríamos preprocesarlas para crear las claves “a”, “ma”, “man”, “manz”, “manza”, “manzan”, “manzana”, “b”, “ba”, “ban”, “bana” y “banan”. Luego, al realizar una búsqueda con “startswith”, podríamos verificar si la cadena de consulta existe en las claves preprocesadas y, de ser así, devolver el valor correspondiente del diccionario.
Este paso de preprocesamiento podría hacerse una vez al inicializar la clase y solo necesitaría actualizarse si el diccionario subyacente cambia. La memoria adicional necesaria para almacenar las claves preprocesadas dependería del tamaño y la distribución de las claves originales del diccionario.