sirve - programa en python para contar caracteres

¿Qué podría afectar el rendimiento de la comparación de cadenas de Python para cadenas de más de 64 caracteres?

Question

Estoy tratando de evaluar si la comparación de dos cuerdas se hace más lenta a medida que aumenta su longitud. Mis cálculos sugieren que la comparación de cadenas debería llevar un tiempo constante amortizado, pero mis experimentos con Python producen resultados extraños:

Aquí hay un gráfico de la longitud de la cadena (1 a 400) en función del tiempo en milisegundos. La recolección automática de basura está deshabilitada y gc.collect se ejecuta entre cada iteración.

Estoy comparando 1 millón de cadenas aleatorias cada vez, contando las coincidencias de la siguiente manera. El proceso se repite 50 veces antes de tomar el mínimo de todos los tiempos medidos.

for index in range(COUNT):
if v1[index] == v2[index]:
matches += 1
else:
non_matches += 1

¿Qué podría explicar el aumento repentino alrededor de la longitud 64?

Nota : El siguiente fragmento de código se puede usar para intentar reproducir el problema suponiendo que v1 y v2 son dos listas de cadenas aleatorias de longitud n y COUNT es su longitud.

timeit.timeit("for i in range(COUNT): v1[i] == v2[i]",
"from __main__ import COUNT, v1, v2", number=50)

Nota adicional : he realizado dos pruebas adicionales: la comparación de cadenas con en lugar de == elimina el problema por completo, y el rendimiento es de aproximadamente 210 ms / 1M comparaciones. Dado que se ha mencionado la internación, me aseguré de agregar un espacio en blanco después de cada cadena, lo que debería evitar la internación; Eso no cambia nada. ¿Es algo más que internar entonces?

Answer 1

Python puede "internar" cadenas cortas; los almacena en un caché especial y reutiliza los objetos de cadena de ese caché.

Al comparar cadenas, primero se probará si es el mismo puntero (por ejemplo, una cadena internada):

if (a == b) {
switch (op) {
case Py_EQ:case Py_LE:case Py_GE:
result = Py_True;
goto out;
// ...

Solo si la comparación del puntero falla, utiliza una verificación de tamaño y memcmp para comparar las cadenas.

Normalmente, el internado solo se realiza para identificadores (nombres de funciones, argumentos, atributos, etc.), no para valores de cadena creados en tiempo de ejecución.

Otro posible culpable son las constantes de cuerdas; los literales de cadena utilizados en el código se almacenan como constantes en el momento de la compilación y se reutilizan en todo momento; de nuevo, solo se crea un objeto y las pruebas de identidad son más rápidas en esos.

Para los objetos de cadena que no son iguales, Python prueba la misma longitud, los primeros caracteres iguales y luego utiliza la función memcmp() en las cadenas C internas. Si sus cadenas no están internadas o están reutilizando los mismos objetos, todas las demás características de velocidad se reducen a la función memcmp() .

Answer 2

Solo estoy haciendo suposiciones locas, pero me preguntaste "qué podría hacer" en lugar de lo que hace, aquí hay algunas posibilidades:

• El tamaño de la línea de la memoria caché de la CPU es de 64 bytes y las cadenas más largas provocan una falta de memoria caché.
• Python puede almacenar cadenas de 64 bytes en un tipo de estructura y cadenas más largas en una estructura más complicada.
• Relacionado con el último: podría poner a cero las cadenas en una matriz de 64 bytes y puede usar instrucciones vectoriales SSE2 muy rápidas para hacer coincidir dos cadenas.