Y a-t-il un moyen de comparer deux blocs de mémoire et de savoir à quel point ils diffèrent (MEMCMP () ne répond pas à cette exigence)? Je ne voudrais pas exécuter des boucles coûteuses. Merci d'avance.
Cordialement, Neo_B
6 Réponses :
Par rapport à tout ce que vous faites, une boucle est bon marché: le gros coût récupérera les données de RAM (ou du disque!) En premier lieu.
Vous ne pouvez pas éviter la boucle avec la comparaison de la mémoire de plus de quelques octets. Écrivez l'algorithme comme vous pouvez l'imaginer. C'est assez simple et vous pourriez être émerveillé à quel point le compilateur optimise le code comme celui-ci.
std :: Mismatch fera cela pour vous en conjonction std :: Distance .
Vous avez supposé qu'il utilise STL Itérateur et, de plus, il a besoin de savoir à quel point la mémoire diffère.
J'ai eu STD :: Equal Equal Tout d'abord, ce qui était évidemment faux, alors je l'ai corrigé. Les algorithmes fonctionnent très bien avec des pointeurs ainsi que des itérateurs (respectés).
@Doomsday: Char * est un type itérateur et Mismatch renvoie deux itérateurs pointant à la différence. +1
@Doomsday: Pour mieux clarifier ce que les autres commentateurs ont dit, tous les algorithmes stl fonctionnent avec des pointeurs unis, pas seulement des itérateurs.
Euh, mon commentaire initial était sur STD :: égal, pas std :: Mismatch. Je vais bien avec la solution de décalage.
Pour être Nitpicky, le lien est à la DOCS pour le SGI Mismatch , qui est pas std :: Mismatch
MEMCMP fait simplement une "boucle coûteuse", octet pour octet. Par exemple, voici la mise en œuvre de Microsoft:
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;
}
L'octet-per-octet est en effet coûteux. 32 bits int Les opérations peuvent même être plus rapides que leurs homologues 8 bits.
J'ai créé ma propre mise en œuvre (je pensais pouvoir le remplacer par quelque chose d'autre finalement). Mes besoins nécessitent jusqu'à 10 000 000 itérations. Le système gèle parfois, mais cela fonctionne. Il dit également combien d'octets ne correspondent pas après une première octroiement de non-match.
@NEO_B: 10 millions d'itérations ne sont pas que beaucoup - la plupart des systèmes le feront dans un quart de seconde ou moins. Je consulterais votre système de mise en mémoire tampon d'entrée ou envisagerons de repenser comment vous attaquez ce problème. Si vous recherchez des cordes, par exemple, le Boyer Moore Algorithm vous fera probablement mieux que tout ici.
Je vérifie en fait si deux images (ou leurs pièces) sont identiques (pour mon serveur de bureau distant). Pas besoin d'envoyer ce qui n'a pas changé, non? :)
Ne voudriez-vous pas qu'un algorithme qui a renvoyé tous les octets modifiés puis, pas seulement le premier emplacement des octets modifiés?
Vous aurez toujours besoin d'une boucle. Mais vous pouvez republier si la boucle de 4 octets (moulée à int *) ou par 8 octets ( Encore mieux, en fonction de la longueur (disons,> 1kb), vous pouvez dérouler la boucle, ce qui signifie que vous vérifiez par exemple par 8 int / uint64_t et sur une inadéquation d'identification du premier octet différent. La boucle déroulante peut aussi retourner feu, car vous avez toutes ces choses de + n choses là-bas et le i = 8 aussi. Benchmark pour être sûr. PS Vérifiez également l'alignement de la mémoire: Ceci sera le plus rapide lorsque uint64_t ou long long int ) est plus rapide que la solution naïve per-octet. M2 & 0XFF == m2 & 0xFF == 0
Merci pour le conseil, je vais certainement le mettre en œuvre, bien que je ne suis pas tout à fait sûr de ce que M1 & 0XFF == m2 & 0xFF == 0 est censé faire, d'après ce que je sais M1 & 0XFF == M1, n'est-ce pas correct?
Cela sera plus rapide dans certains cas, mais cela pourrait entraîner des problèmes. Tout d'abord, il repose sur votre plate-forme ayant le même alignement pour les entiers 64 bits que pour des personnages, ce qui n'est souvent pas le cas. (Personne ne dit que la base du réseau de caractères doit être sur une limite de 8 octets) Deuxièmement, un intrinsèque intégré ou un assembleur sera probablement plus rapide. Sur X86, la question de l'alignement de la mémoire rendra les choses plus lentes, et sur d'autres architectures, cela entraînera une interruption du processeur.
@NEO_B: m1 & 0xFF == 0 est un test si l'adresse m1 se termine par 00 . @Billy: Bien entendu dans ces types d'optimisations, vous devez jouer un peu avec les limites, de sorte que le premier bloc aligné que vous testez lentement, puis testez autant de blocs que possible rapidement et testez le reste lent. (Comme indiqué que ces choses ne fonctionnent que de manière positive si les blocs sont assez gros) Un intrinsèque intégré ou un assembleur sera probablement plus rapide s'il existe ce qui ne pense pas que ce n'est pas le cas pour le problème à la main.
Oh, à droite, mon erreur (le 0xFF sans zéros avant de vous tromper illogiquement de penser que M1 était un octet).
S'il y avait un meilleur moyen de comparer deux blocs de mémoire, MEMCMP serait réimprimé de le faire.
Cela dit souvent, MEMCMP a une implémentation portable par défaut dans la bibliothèque C Standard C, mais il est souvent mis en œuvre par le compilateur lui-même comme une fonction intégrée. Cette fonction intégrée doit être hautement optimisée pour l'architecture cible.So Prenez la mise en œuvre de la bibliothèque avec une pincée de sel.
Voir aussi Stackoverflow.com/questions/855895/Intrinsic-MemCMP À propos des implémentations MEMCMP optimisées par la CPU. Si vous connaissez la CPU, vous pouvez régler l'une des fonctions __builtin_memcmp () de GCC à vos besoins.
Notez que tout ce que vous avez ici va être mis en œuvre comme une boucle quelque part - il n'y a pas de moyen magique de faire ce que vous voulez ici sans un.