Voy a tener un pequeño diccionario (entre 5 y 20 claves) al que se hará referencia hasta cien veces más o menos para una carga de página en python 2.5.Nombrar claves dict para una búsqueda rápida en python
Estoy empezando a nombrar las teclas que buscará y me preguntaba si existe una convención de nombres clave que pueda seguir para ayudar a los tiempos de búsqueda.
tuve que probar ;-)
usando
1"one""aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"como uno de las teclas en un diccionario de longitud 4. Iterar 10,000,000 tiempos y medir los tiempos. Consigo este resultado:
<function f1 at 0xb779187c>
f1 3.64
<function f2 at 0xb7791bfc>
f2 3.48
<function f3 at 0xb7791bc4>
f3 3.65
es decir no hay diferencia ...
Mi code
... pero lo que estoy viendo podría ser el efecto del almacenamiento en caché ... –
Así que, básicamente, estoy reuniéndome ... no se preocupe, especialmente para un dict pequeño y un número relativamente bajo de búsquedas. – adam
porque la cadena de Python itera función de hash más de los caracteres (al menos si this sigue siendo aplicable), me gustaría optar por cortas cadenas.
Los almacena en caché, vea string_hash (PyStringObject * a) en [stringobject.c] (http://svn.python.org/projects/python/trunk/Objects/stringobject.c). Posiblemente lo hizo desde siempre. Considere que esa página solo da la idea de los algoritmos escritos en Python, no la implementación exacta. – delnan
@delnan: Gracias por la información, no estoy realmente interesado en Python. Pero dado que el hash tiene que computarse al menos una vez, de todos modos, en forma reducida sigue siendo válido. Edité en consecuencia. – Waldheinz
Es un bucle muy ajustado que solo procesa números escritos en C compilados por un compilador moderno. Es poco probable que una iteración promedio tome más de unos pocos ciclos. Este es el nivel donde no se puede medir ninguna diferencia a menos que ejecute un millón de bucles con un millón de iteraciones cada uno. Afeitar a un personaje probablemente solo hará una diferencia de unos pocos nanosegundos. **EN ABSOLUTO**. No creo que este sea un buen consejo. – delnan
There may sean nombres razonables para ellos que simplemente producen nombres cuyos hashes no están en conflicto. Sin embargo, los dictos de CPython ya son una de las estructuras de datos más optimizadas en el universo conocido, producen pocas colisiones para la mayoría de las entradas, funcionan bien con los esquemas hash de otros tipos integrados, resuelven choques muy rápido, etc. Es extremadamente poco probable que ' Veremos cualquier beneficio, incluso si ha encontrado algo, especialmente dado que cientos de búsquedas no son realmente tantas.
Tomemos, por ejemplo, esta referencia timeit ejecuta en mi máquina de escritorio 4 años de edad (luciendo un laughablely de bajo presupuesto de la CPU de doble núcleo con 3,1 GHz):
...>python -mtimeit --setup="d = {chr(i)*100: i for i in range(15)};\
k = chr(7)*100" "d[k]"
1000000 loops, best of 3: 0.222 usec per loop
Y esas cadenas son una docena de veces más grande que todo lo que es remotamente sensible para escribir manualmente como un nombre de variable. Reducir la longitud de 100 a 10 conduce a 0.0778 microsegundos por búsqueda. Ahora mida la velocidad de carga de su página y compárelos (alternativamente, solo reflexione sobre cuánto tiempo llevará el trabajo que está haciendo realmente al construir la página); y tenga en cuenta el almacenamiento en caché, la sobrecarga del marco y todas estas cosas.
Nada de lo que haga en este sentido puede marcar la diferencia en términos de rendimiento, punto y punto.
Los diccionarios de Python tienen una ruta rápida para las claves de cadena, así que úselas (en lugar de, digamos, tuplas). El valor hash de una cadena se almacena en caché en esa cadena, por lo que es más importante que las cadenas sigan siendo las mismas que su valor real; las constantes de cadena (es decir, las cadenas que aparecen literalmente en el programa y no son el resultado de un cálculo) siempre permanecen exactamente igual, por lo que siempre que las use, no hay necesidad de preocuparse.
Para añadir otro aspecto:
muy pequeños diccionarios y las limitaciones de tiempo pesados, el tiempo para calcular hashes podría ser una fracción sustancial del tiempo total. Por lo tanto, para (digamos) 5 elementos, podría ser más rápido usar una matriz y una búsqueda secuencial (por supuesto, envuelta en algún objeto MiniDictionary), tal vez incluso aumentada mediante una búsqueda binaria. Esto podría encontrar el elemento con 2-3 comparaciones, que puede o no ser más rápido que el cálculo de hash más uno comparar.
El punto de equilibrio depende de la velocidad de dispersión, el número promedio de elementos y el número de colisiones hash a esperar, por lo que se requieren algunas medidas, y no hay una respuesta "talla única".
No si esa búsqueda está escrita en Python. – delnan
Si se puede conformar con claves enteras - que será más rápido que las cuerdas. (De ser así, probablemente solo puedas usar una lista.) –
@Sven Marnach, ¿es así? ¿La función hash requiere un entero más rápido que una cadena? Si es así, esa es información interesante, ¿tienes una referencia? – juanchopanza
@juanchopanza: enteros hash a sí mismos (al menos aquellos en el rango del tipo entero utilizado para los valores hash). Las cadenas tendrán que repetirse al menos una vez. – delnan