python - hashing - hash table c++
Optimización de la peor complejidad de tiempo de caso para O(1) para dictados de pitón (3)
¿Hay alguna razón por la que le importe el peor rendimiento posible en lugar del rendimiento promedio? Cualquier hashtable razonable le dará el rendimiento promedio de O (N).
Si realmente desea el peor rendimiento de O (1), aquí hay dos enfoques posibles:
Tenga un vector de
max(charCode)-min(charCode)y busque directamente el valor que desea del código de carácter Unicode. Esto funcionará bien si sus claves caen en un rango lo suficientemente compacto como para que pueda caber en la memoria RAM.Utilice un enfoque de fuerza bruta para elegir funciones hash o tamaños de diccionario (usando una implementación personalizada de un diccionario que le permite controlar esto), y siga probando nuevas funciones y / o tamaños hasta que obtenga uno sin colisiones. Espera que esto tome mucho tiempo. No recomiendo esto.
EDITAR:
Supongamos que sabe que el código de carácter mínimo que verá es 1234 y el máximo que verá es 98765. Además, suponga que tiene suficiente RAM para contener 98765-1234 elementos. También asumiré que está dispuesto a usar la biblioteca numpy o alguna otra implementación eficiente de matriz. En ese caso, puede almacenar los valores en el vector de esta manera:
# configuration info
max_value = 98765 # replace with your number
min_value = 1234 # replace with your number
spread = (max_value - min_value)
dtype = object # replace with a primitive type if you want to store something simpler
# create the big vector
my_data = numpy.empty((spread,), dtype=dtype)
# insert elements
my_char_code = ...
my_value_for_my_char_code = ...
assert min_value <= my_char_code < max_value
my_data[my_char_code - min_value] = my_value_for_my_char_code
# extract elements
my_char_code = ...
assert min_value <= my_char_code < max_value
my_value_for_my_char_code = my_data[my_char_code - min_value]
Esto es O (1) porque la búsqueda se implementa usando la aritmética del puntero y no hay dependencia de la cantidad de elementos almacenados en la matriz.
Este enfoque puede ser extremadamente inútil de RAM si la cantidad de elementos que realmente desea almacenar es mucho menor que la spread . Por ejemplo, si el spread es de 4 mil millones (todos UTF32) entonces my_data solo consumirá al menos 4 mil millones * 8 bytes / puntero = 32 GB de RAM (y probablemente mucho más, no sé cuán grandes son las referencias de Python) . Por otro lado, si min_value es 3 mil millones y max_value = min_value + 100 , entonces el uso de memoria será muy pequeño.
Tengo que almacenar 500M caracteres de dos dígitos Unicode en la memoria (RAM).
La estructura de datos que uso debe tener:
Worst Case Space Complexity: O(n)
Worst Case Time Complexity: O(1) <-- insertion, read, update, deletion
Estaba pensando en elegir el dict que es la implementación de hash en python, pero luego el problema es que asegura la complejidad del tiempo de O (1) para las operaciones requeridas solo en casos promedio que en el peor de los casos.
Escuché que si se conoce el número de entradas, la complejidad de tiempo de O (1) se puede lograr en el peor de los casos.
¿Como hacer eso?
En caso de que eso no sea posible en Python, ¿puedo acceder directamente a las direcciones de memoria y a los datos en mi código python? ¿Si es así, entonces cómo?
La mayoría de los golpes de rendimiento (generalmente tomados en una colisión) se amortizan en todas las llamadas. Entonces, para un uso más realista, no obtendrá O(n) para cada llamada. De hecho, el único caso en el que incurrirías en O(n) en cada llamada es en el caso patológico donde el hash de cada tecla colisiona con el valor hash de una clave existente (es decir, el peor uso posible (o desafortunado) de una tabla hash) .
Si, por ejemplo, conoce su conjunto de claves de antemano, y sabe que no tendrán colisiones hash (es decir, todas sus hashes son únicas), entonces no sufrirá casos de colisión. La otra operación principal de O(n) es el cambio de tamaño de hashtable, pero la frecuencia de esto depende de la implementación (factor de expansión / función de hash / esquema de resolución de colisión, etc.) y también variará de ejecutarse según el conjunto de entrada .
En cualquier caso, puede evitar la ralentización repentina del tiempo de ejecución si puede rellenar previamente el dict con todas las teclas. los valores solo se pueden establecer en Ninguno y se pueden rellenar con sus valores reales más adelante. Esto debería causar el único golpe de rendimiento notable al "cebar" el dict con claves inicialmente, y la inserción de valores futuros debería ser constante.
Una pregunta completamente diferente es cómo tiene la intención de leer / consultar la estructura? ¿necesita adjuntar valores separados y tener acceso a ellos a través de una clave? debería ser ordenado? quizás un set podría ser más apropiado que un dict , ya que realmente no se necesita una key:value asignación de key:value .
Actualizar:
Según su descripción en los comentarios, esto comienza a parecerse más a un trabajo para una base de datos, incluso si está trabajando con un conjunto temporal. Puede usar una base de datos relacional en memoria (por ejemplo, con SQLite). Además, puede usar un ORM como SQLAlchemy para interactuar con la base de datos más pythonically y sin tener que escribir SQL.
Incluso suena como si estuvieras leyendo los datos de una base de datos para empezar, ¿entonces quizás puedas aprovechar eso más?
Almacenar / consultar / actualizar una cantidad masiva de registros tipeados con clave única es exactamente para lo que se han especializado los RDBMS con décadas de desarrollo e investigación. Usar una versión en memoria de una base de datos relacional preexistente (como la de SQLite) probablemente sea una opción más pragmática y sostenible.
Intente utilizar sqlite3 módulo sqlite3 incorporado de python y pruebe la versión en memoria proporcionando ":memory:" como la ruta del archivo db en la construcción:
con = sqlite3.connect(":memory:")
El Diccionario tiene técnicamente un peor caso de O (n) pero es muy poco probable que ocurra y probablemente no lo haga en su caso. Trataría de usar el diccionario y solo cambiar a una implementación diferente si eso no es suficiente para lo que quieres hacer.