¿Hay alguna forma de comparar dos bloques de memoria y saber en qué punto difieren (memcmp() no cumple este requisito)? No me gustaría realizar bucles costosos. Gracias por adelantado.Comparación de memoria (con posición diferente)
Saludos, Neo_b
En comparación con cualquier otra cosa que está haciendo, un bucle es barato: el gran costo será recuperar los datos de la memoria RAM en el primer lugar (o disco!).
No se puede evitar el bucle con la comparación de memoria de más de unos pocos bytes. Escribe el algoritmo como puedas imaginarlo. Es lo suficientemente simple y es posible que se sorprenda de lo bien que el compilador optimiza el código de esta manera.
std::mismatch lo haremos para usted junto con std::distance.
Supone que está usando el iterador STL, y además necesita saber en qué punto difiere la memoria. – Doomsday
Tenía std :: igual primero, lo cual era obviamente incorrecto así que lo he corregido. Los algoritmos funcionan muy bien con punteros y con iteradores (completos). –
@Doomsday: 'char *' * es * un tipo de iterador, y 'desajuste' devuelve dos iteradores que apuntan a la diferencia. +1 – Potatoswatter
memcmp simplemente hace un "bucle costoso", byte para el byte. Por ejemplo, aquí está la implementación de Microsoft:
EXTERN_C int __cdecl memcmp(const void *Ptr1, const void *Ptr2, size_t Count)
{
INT v = 0;
BYTE *p1 = (BYTE *)Ptr1;
BYTE *p2 = (BYTE *)Ptr2;
while(Count-- > 0 && v == 0) {
v = *(p1++) - *(p2++);
}
return v;
}
La mayoría de las otras implementaciones hacen exactamente lo mismo. Para sus necesidades, podría hacer algo como esto:
long my_memcmp(const void *Ptr1, const void *Ptr2, size_t Count)
{
INT v = 0;
long pos = 0;
BYTE *p1 = (BYTE *)Ptr1;
BYTE *p2 = (BYTE *)Ptr2;
while(Count-- > 0 && v == 0)
{
v = *(p1++) - *(p2++);
if (v == 0)
pos++;
else
break;
}
return pos;
}
byte-por-byte es de hecho costoso. Las operaciones 'int' de 32 bits pueden incluso ser más rápidas que sus contrapartes de 8 bits. – mvds
Creé mi propia implementación (pensé que podría reemplazarla eventualmente por otra cosa). Mis necesidades requieren hasta 10 000 000 de iteraciones. El sistema se congela a veces, pero funciona. También dice cuántos bytes no coinciden después de una primera ocurrencia no coincidente. –
@Neo_b: 10 millones de iteraciones no es mucho, la mayoría de los sistemas lo harán en un cuarto de segundo o menos. Estaría mirando su esquema de búfer de entrada, o considerando repensar cómo está atacando este problema. Si está buscando cadenas, por ejemplo, el algoritmo de Boyer Moore probablemente lo hará mejor que nada aquí. –
Siempre necesitará un bucle. Pero podría comparar si el bucle en 4 bytes (conversión a int *) o en 8 bytes (uint64_t o long long int) es más rápido que la solución ingenua por byte.
Mejor aún, dependiendo de la longitud (digamos,> 1kb) puede desenrollar el bucle, lo que significa que debe marcar, por ejemplo, por 8 int/uint64_t y en una discrepancia, señale el primer byte diferente.
uint64_t *bigsteps1 = (uint64_t*)m1;
uint64_t *bigsteps2 = (uint64_t*)m2;
int steps = min(m1_len,m2_len)/sizeof(uint64_t);
int i;
for (i=0; i<steps; i+=8)
{
if (bigsteps1[i] != bigsteps2[i]
|| bigsteps1[i+1] != bigsteps2[i+1]
/// ....
|| bigsteps1[i+7] != bigsteps2[i+7]) break;
}
// i<steps tells if we found a difference
// end game is trivial, left as an excercise to the reader.
El desenróllese bucle también puede ser contraproducente, para que tenga todos estos N + cosas allí y la i + = 8 así. Benchmark para estar seguro.
ps también comprobar la alineación de memoria: esto será más rápido cuando m1&0xff == m2&0xff == 0
Gracias por el consejo, ciertamente lo implementaré, aunque no estoy del todo seguro de qué se supone que m1 & 0xff == m2 & 0xff == 0, por lo que sé m1 & 0xff == m1, ¿no es así? –
Esto será más rápido en algunos casos, pero podría ocasionar algunos problemas. En primer lugar, se basa en que su plataforma tenga la misma alineación para enteros de 64 bits que para los caracteres, lo que a menudo no es el caso. (Nadie dice que la base de la matriz de caracteres tiene que estar en un límite de 8 bytes) En segundo lugar, un ensamblador o intrínseco incorporado probablemente sea más rápido. En x86, el problema de alineación de memoria hará que las cosas sean más lentas, y en otras arquitecturas, provocará que el procesador genere una interrupción. –
@Neo_b: 'm1 & 0xff == 0' es una prueba si la dirección' m1' termina con '00'. @Billy: Por supuesto, en este tipo de optimizaciones debe juguetear un poco con los límites, por lo que hasta el primer bloque alineado pruebe lento, luego pruebe la mayor cantidad de bloques posible, y pruebe el resto lentamente. (como se dijo, estas cosas solo funcionan positivamente si los bloques son lo suficientemente grandes). Un ensamblador o intrínseco incorporado probablemente sea más rápido * si existiera *, lo cual no es el caso para el problema en cuestión. – mvds
Si había una mejor manera de comparar dos bloques de memoria, memcmp serían Reimplementado de hacer eso.
Habiendo dicho eso a menudo, memcmp tiene una implementación portátil predeterminada en la biblioteca estándar de C, pero a menudo el compilador la implementa como una función integrada. Esta función incorporada debe estar altamente optimizada para la arquitectura de destino. Por lo tanto, tome la implementación de la biblioteca con una pizca de sal.
ver también http://stackoverflow.com/questions/855895/intrinsic-memcmp acerca de las implementaciones de memcmp optimizadas por CPU. Si conoce la CPU, puede sintonizar una de las funciones de __builtin_memcmp() de gcc según sus necesidades. – mvds
Tenga en cuenta que todo lo que tiene aquí se implementará como un bucle * en algún lugar * - no hay una forma mágica de hacer lo que quiera aquí sin uno. –