6
votes

Comparer les données parewise de manière efficace (avec C ++)

Y a-t-il un moyen plus efficace de comparer les données byTewise que d'utiliser la comparaison Opérateur du conteneur de liste C ++?

Je dois comparer [grand? 10 KBYTE

Par conséquent, j'ai lu des fichiers parewise et stockez les valeurs dans une liste des caractères non signés. Les récurrences de cette liste sont gérées par un Shared_ptr , afin que je puisse le transmettre Dans le programme sans la nécessité de s'inquiéter de la taille de la liste xxx

Ceci est fait deux fois, car il y a toujours deux copies du fichier. Le contenu de ces deux fichiers doit être comparé et lancer une exception si une inadéquation est trouvée xxx

mon problème est la suivante:

Avec une taille de fichier croissante, la comparaison des listes devient très lente. Travailler avec des tailles de fichiers d'environ 100 KBYTE, il prendra jusqu'à deux secondes pour comparer le contenu. Augmenter et diminuer avec la taille du fichier ....

existe-t-il un moyen plus efficace de faire cette comparaison? Est-ce un problème du conteneur utilisé?


5 commentaires

Si la fonction compare simplement deux fichiers sans indiquer ce qui diffère, vous devez peut-être retourner une valeur booléenne au lieu de jeter une exception. Cela ferait beaucoup plus de sens.


Pourquoi stockez-vous des blobs de mémoire dans listes ? Et pourquoi sur Terre allouons-vous ces listes dynamiquement ?


S'il y a un missminchère entre deux fichiers, cela est considéré comme une erreur grave par le logiciel. Toutes les opérations de course seront arrêtées et le programme ne peut pas être poursuivi. Il n'est pas acceptable que toutes les différences se produisent dans le contenu du fichier


@zitironeneis: Bien sûr. Mais ne serait-il pas plus propre si l'objectif de la fonction était de comparer deux fichiers et de donner un résultat booléen? Ensuite, selon ce résultat, vous pouvez lancer une exception si nécessaire. De cette façon, vous pouvez réutiliser votre fonction si vous en avez déjà.


@zitronis: Vous ne pouvez pas parler d'efficacité et utiliser une liste d'octets, c'est incompatible.


7 Réponses :


8
votes

N'utilisez pas de std :: Liste Utilisez un std :: vecteur .

std :: liste est une liste liée, éléments ne sont pas garantis pour être stockés contiguës.

std :: vecteur d'autre part semble bien mieux adapté à la tâche spécifiée (stocker des octets contigus et comparer de grandes morceaux de données).

Si vous devez comparer plusieurs fichiers plusieurs fois et ne vous souciez pas de l'emplacement des différences, vous pouvez également calculer un hachage de chaque fichier et comparer les hachages. Ce serait encore plus rapide.


6 commentaires

Cette. Un tableau est le conteneur de stockage le plus rapide de miles si vous ne modifiez pas les éléments au milieu.


Changer la mise en œuvre sur STD :: Vector a totalement résolu le problème de la comparaison lente. Merci beaucoup!


@Deadmg: (D'accord, ceci est pédant -) mais les modifier va bien, c'est l'insertion ou la suppression de ce qui est la performance sucer :) +1 pour répondre.


@Billy: Tu as raison, je n'étais pas très clair. Vous pouvez changer les éléments tout ce que vous aimez, ne faites rien de vous en commander.


@Deadmg: la réorganisation est fine (en utilisant échange ) Il insère / en retrait (en dehors de la fin) qui n'est pas.


Un homme sage pourrait également trouver la taille des fichiers à l'avance et utiliser la méthode .Reserve ( sur le vecteur pour prélever l'espace nécessaire.



1
votes

S'il n'y a rien d'autre à faire avec le contenu de ces fichiers (on dirait que vous allez les laisser être supprimés par Shared_PTR à la fin de la portée du comparateur () de comparaison), pourquoi ne pas comparer les fichiers à l'aide d'itérateurs, Ne crée pas de conteneurs du tout?

Voici un morceau de mon code qui compare deux fichiers byTewise: xxx

modifier: Si vous do ont besoin Pour garder le contenu, je pense que std :: deque peut être légèrement plus efficace que std :: vecteur pour les raisons expliquées dans GOTW # 54 .. ou non - le profilage va dire. Et toujours, il y aurait le besoin de seulement l'un des deux fichiers identiques à charger en mémoire - j'aurais lu une dans une dent et comparer avec l'autre fichier Istreambuf_iterator.


9 commentaires

Belle solution. Cependant, si il doit comparer le même fichier à d'autres fichiers (plusieurs fois). Cette solution ne le force pas à relire le fichier à chaque fois?


Compte tenu de la taille de données des fichiers qu'ils pourraient tous être tenus dans la RAM pendant la durée. Dépend du nombre total de fichiers.


@ cerneon: OP a dit Il y a toujours deux copies du fichier


En fait, ce n'est qu'un extrait de mon code. Dans mon programme, il existe une base de données d'objets de test lorsque des modèles de contenu sont stockés pour référence future. Merci quand même!


@Cubbi: Peut-être que je ne comprends-je pas bien, mais ce n'est-il pas strongé mon point?


@ cerne: vous pouvez toujours lire le premier fichier dans un std :: vecteur une fois et utiliser le même code std :: égal pour le comparer à tous les fichiers.


Quoi qu'il en soit, cela suppose que les fichiers sont de la même longueur. Est-ce le cas?


@ cerneon: Je veux dire, je l'ai lu comme "il y a une copie" filea "et une copie" FileB ", et ces deux doivent être comparés parewise, et il y en a toujours deux." Quoi qu'il en soit, comme ils doivent être stockés en mémoire de toute façon, il est discutable.


J'aimerais souligner que cet article est extrêmement vieux. Il y a de nouvelles installations de vecteur (comme vecteur :: strink_to_fit) et les implémentations auront légèrement évolué au cours des quinze dernières années (l'article référencements MSVC 5, nous sommes maintenant sur MSVC 10).



0
votes

STD :: La liste est monumentalement inefficace pour un élément de caractère - il y a des frais généraux pour chaque élément de faciliter l'insertion et l'enlèvement de O (1), ce qui n'est vraiment pas ce que votre tâche nécessite.

Si vous devez utiliser STL, STD :: Vecteur ou l'approche itératrice suggérée serait préférable à STD :: Liste, mais pourquoi pas simplement lire les données dans un char * enveloppé dans un pointeur intelligent de votre choix et d'utiliser memcmp?


2 commentaires

S'il le fait C ++, pourquoi utiliserait-il des fonctions C et non la STL? std :: vecteur est parfaitement conçu pour cette tâche.


"Pourquoi pas simplement lire les données dans un char * enveloppé dans un pointeur intelligent de votre choix ...?" Parce que cela n'aurait aucun avantage sur std :: vecteur , mais aurait des inconvénients.



0
votes

Il est fou d'utiliser autre chose que MEMCMP pour la comparaison. (Sauf si vous le souhaitez même plus rapidement, auquel cas vous voudrez peut-être le coder en langage de montage.)


22 commentaires

Je m'attendrais à ce que je stands std :: égal (égal (égal () à utiliser std :: memcmp () si c'est le jeûne. Je ne m'attends pas à avoir à décider que moi-même et à adapter ce code chaque fois que je modifie le type de données ou le port vers une nouvelle plate-forme.


@sbi: Mais std :: égal (égal () est uniquement fourni avec des itérateurs et non des références au conteneur lui-même. Comment peut-il optimiser d'utiliser memcmp () ?


@Oli Charlesworth: Rien ne dit que les itérateurs ne peuvent pas faire référence à leur conteneur parent. Plus au point, au moins pour les vecteurs, vous pouvez obtenir le bloc de mémoire sous-jacent basé sur les itérateurs eux-mêmes. ( std :: égal peut être modèle spécialisé pour std :: vecteur :: itérateur et amis)


@Billy: Je perdais juste à l'intérieur de la mise en œuvre de la mise en œuvre de GNU Vector et n'a trouvé aucune spécialisation pour égal . Je comprends ce que vous dites, mais il semble que cela ne soit pas fait dans la pratique ...


@Oli: 1. Il existe de nombreuses autres mises en œuvre stl que celles de GCC. 2. Même si ce n'est pas le cas, je doute sérieusement memcmp et std :: égal en fonction d'une implémentation naïf différerait de la performance. Ce n'est pas comme si la fonction est complexe.


@Oli: Il pourrait y avoir une mise en œuvre spéciale pour les itérateurs de std :: vecteur des cas de pods. Ce n'est pas particulièrement difficile à découvrir.


@Billy: 3. Un tel code spécial serait trouvé dans la mise en œuvre des algorithmes, pas dans les conteneurs. (Ce serait la même chose pour les pointeurs et pour std :: vecteur <> :: itérateur .)


@SBI: J'ai regardé dans stl_algobase.h aussi, et ne peut rien trouver. Je vais essayer de compiler quelque chose et de voir où il se résout à ...


@Billy: Il y a bien d'autres implémentations! Mais GCC est un joli majeur. J'imagine que l'assembleur optimisé pour MEMCMP (qui utilise des boucles de chaîne X86 et des comparaisons longues) sera un peu plus rapide qu'une comparaison de caractère par caractère. Mais je n'ai pas profilé ...


@Oli: J'attendrais toujours que ma mise en œuvre gère cela pour moi, même si je dois admettre que cela pourrait ne pas le faire. :) mais si tel est le cas, la version suivante pourrait faire. Et même si la prochaine version échoue aussi, je toujours ne pas encombrer mon code avec de tels détails de bas niveau (vous modifiez le type d'élément du conteneur et avez soudainement reçu un non-pod que vous ne devriez pas ne pas devoir Utilisez std :: memcmp () sur dans une partie complètement différente de votre code), jusqu'à ce que le profilage montre qu'un appel particulier à std :: égal () < / Code> est trop lent et que les performances augmentent effectivement en utilisant std :: memcmp () à la place.


@Oli: Fwiw, j'ai examiné la norme Lib de VC9 (de Dinkumware) et j'ai constaté qu'il appelle std :: memcmp () à partir de std :: égal () Pour ( signé Char * ou non signé Char * ) et des itérateurs d'accès aléatoire. Il fera toutefois recourir à sa propre boucle pour Char * . Pourquoi cela fait-il cela, je ne saurais pas et je ne suis pas intéressé non plus. (J'ai déjà dit que je m'attendais à ce que ma mise en œuvre s'occupe de cela.)


@sbi: Je prends ton point. Cependant, si le profilage montre que c'est vraiment le point chaud de l'application, je dirais que cela justifierait le remplacement par un appel à MemCMP () s'il apporte une vitesse significative, quel que soit le coût du coût clarté. Donc, je suppose que nous sommes d'accord! (FWIW, j'ai couru objdump sur un exemple trivial compilé contre la bibliothèque GNU, et il ne résout pas à memcmp () ).


@Oli: Oui, dans ce que nous sommes d'accord. Cependant, cela semble un coup long de "c'est fou d'utiliser autre chose que MemCMP pour la comparaison", à laquelle je m'oppose.


Tu es tout fou! MEMCMP est une fonction parfaitement respectable. C'est rapide et c'est portable. C'est tout ce que vous avez besoin de savoir, n'est-ce pas?


@Tony: Je comprends où vous venez, mais std :: memcmp () n'est pas très c ++. Ce n'est pas un type de type, vous devez le dire manuellement combien de temps les tableaux sont (en octets) et ne s'étendent pas aux types de conteneurs arbitraires.


Là nous l'avons. 'N'est pas très c ++'. Est-ce que c'est comme républicain en nom seulement? Ce n'est pas un problème religieux, c'est un problème de vitesse.


@Tony: Ce n'est pas simplement "religieux". La sécurité de type, etc. Sont toutes bonnes choses. Vous ne devriez pas les sacrifier sauf si vous êtes certain que memcmp () vous offre un boost de vitesse significatif.


La loi d'Amdahl. Vous êtes vraiment un homme de façon.


Arguments en faveur de l'utilisation de MemCMP pour comparer les tableaux d'octets: 1. C'est rapide. 2. C'est portable. 3. Il est facile à utiliser. Arguments contre l'utilisation de MemCMP pour comparer les tableaux d'octets: 1. Ce n'est pas très C ++. 2. Ce n'est pas sécurisé si vous ne comparez pas de tableaux d'octets. 3. Il tire la loi d'Amdahl.


@Tony: Ce n'est pas très c ++ parce que Ce n'est pas le ta type de sécurité, générique ou encapsulé. Il ne "touche" pas la loi d'Amdahl; Le point est que l'optimisation prématurée qui conduit à de sacrifier l'une de ces réponses ci-dessus est en effet "la lune".


@Tonyk: Parfois, quand toute une communauté semble être en désaccord, il est sage d'écouter. Si vous ne pouvez pas voir la différence entre C et C ++ , vous ne maîtrisez probablement aucun d'entre eux. Véritables arguments contre memcmp : std :: égal est aussi rapide, aussi portable et encore plus facile à utiliser. De plus, cela rend votre code C ++ cohérent et responsable.


OK, j'ai écrit un programme de référence afin que nous puissions l'évaluer objectivement. Cela ne conviendrait pas dans un commentaire, alors j'ai posté une autre réponse. Il s'avère que sur mon système, STD :: EMAL est un peu plus lent que MEMCMP, mais l'opérateur == est tout aussi rapide. Que se passe-t-il sur votre système?



2
votes

Mon premier conseil serait de Profil de votre code .

La raison pour laquelle je dis que c'est que, peu importe la ralentissement de votre code de comparaison, je soupçonne que votre fichier E / S est nain. Vous ne voulez pas perdre de jour à essayer d'optimiser une partie de votre code qui ne prend que 1% de votre runtime tel quel.

Cela pourrait même être qu'il y ait quelque chose d'autre que vous n'avez pas remarqué avant de causer la lenteur. Vous ne saurez pas avant de profiler.


10 commentaires

Comme je suis normalement accepté de ces conseils, lisez des blobs binaires dans listes liées d'octets très suscitait probablement une performance inférieure, même je ne me dérangerais pas à mesurer.


Convenu sur le profilage. Cependant, dans le cas, en utilisant une liste liée au lieu d'une liste contiguë est un problème algorithmique en soi.


Je ne suis pas aussi shru que tu veux dire par profilage. Mais je pense que j'ai fait une chose semblable, et c'est la raison pour laquelle je suis venu la question. Je vais loger chaque opération avec un niveau d'abscordement pour la méthode qui a écrit l'entrée du journal. J'ai donc découvert que la très petite méthode de comparaison causait l'ensemble du programme de ralentir, car c'est une partie essentielle du programme et elle est appelée très réglementaire.


@zitironeneis: Vous obtenez un excellent conseil ici. De plus, si vous n'êtes pas sûr de ce que l'on entend par profilage, vous devriez obtenir sûr. Voici ce que je fais ( Stackoverflow.com/Questtions/375913/... ). Si vous êtes étudiant, vous n'avez probablement pas entendu parler de cela, mais toutes les lignes de code, que ce soit ou non un appel de fonction, est responsable d'un certain pourcentage du temps total, de sorte que si ce n'était pas là, ce temps ne serait pas dépensé. Pendant ce temps, c'est sur la pile pour vous de voir.


@Mike Dunlavey - Votre méthode a l'air plus simple et plus rapide que ce que j'ai fait jusqu'à présent (utilisez un enregistreur avec des horodatages et des niveaux de débogage différents, numérisant le fichier journal avec mes yeux pour trouver des méthodes inefficaces). Va l'essayer sur mon programme. Merci pour le conseil


@zitironeneis: C'est une méthode qui a été découverte de manière indépendante par certaines personnes, comme dans Stackoverflow.com/Questtions/2473666/... et Stackoverflow.com/questions/266373/... . J'ai fait de mon mieux pour diffuser le mot: Stackoverflow.com/questions/2624667/... et Stackoverflow.com/questions/1777556/alternatives-a-gProf/.../a>


@Mike Dunlavey - Curieusement, mon objection à cette méthode est exactement le contraire de celui que vous avez rejeté: souvent, je trouve que le débogueur arrête les choses est pas aléatoire. Il y a des choses certianes (par exemple: des appels système) que vous n'interrompez jamais avec le débogueur. Néanmoins, il y aura des moments où cela vous dirigera directement au problème. Bien mieux que deviner.


@Ted: Oui, si vous le mettez en pause lors d'un appel système, il devrait s'arrêter lorsque cet appel revient, c'est donc aussi bon car il indique où il dit où dans votre code (qui est tout ce que vous pouvez éditer) était à ce moment-là. Ce qui est utilisé pour gelée, c'est quand cela retarderait la pause jusqu'au prochain message Windows. Homme, c'était fâché!


@Mike Dunlavey - Ouais, le vieux débogueur Sunos avait l'habitude de faire la chose équivalente pour moi. Je suppose que c'est là que je l'ai eu dans ma tête que je ne pouvais pas l'utiliser comme une technique de profilage. Je devrais vraiment faire confiance à un débogueur avant que je le faisais à nouveau. Pour profilage, si je ne peux pas totalement confiance à mes résultats, il est essentiellement sans valeur pour moi.


#zitironeneis: @ t.e.d: hier, j'ai reçu une vitesse de 24% dans un programme de simulation, en deux correctifs. Le premier était dû à certains changements récents que j'avais faits, ce que je ne pensais pas serait une performance touchée. La seconde était dans une routine générale pour opérer sur des matrices à Lapack qui passaient trop de temps à classer ses arguments. Il a fallu environ 10 piles pour les trouver.



0
votes

Dans l'intérêt de l'objectivité dans le débat MEMCMP-VS-EGAE, je propose le programme de référence suivant, de sorte que vous puissiez voir pour vous-même qui, le cas échéant, est plus rapide sur votre système. Il teste également l'opérateur ==. Sur mon système (Borland C ++ 5.5.1 pour Win32):

STD :: EQUAL: 1375 Ticks
Opérateur ==: 1297 Ticks d'horloge
MEMCMP: 1297 Coques d'horloge p>

Que se passe-t-il sur votre système? P>

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

static char* buff ;
static vector<char> v0, v1 ;

static int const BufferSize = 100000 ;

static clock_t StartTimer() ;
static clock_t EndTimer (clock_t t) ;

int main (int argc, char** argv)
  {
  // Allocate a buffer
  buff = new char[BufferSize] ;

  // Create two vectors
  vector<char> v0 (buff, buff + BufferSize) ;
  vector<char> v1 (buff, buff + BufferSize) ;

  clock_t t ;

  // Compare them 10000 times using std::equal
  t = StartTimer() ;
  for (int i = 0 ; i < 10000 ; i++)
    if (!equal (v0.begin(), v0.end(), v1.begin()))
      cout << "Error in std::equal\n", exit (1) ;
  t = EndTimer (t) ;
  cout << "std::equal: " << t << " clock ticks\n" ;

  // Compare them 10000 times using operator==
  t = StartTimer() ;
  for (int i = 0 ; i < 10000 ; i++)
    if (v0 != v1)
      cout << "Error in operator==\n", exit (1) ;
  t = EndTimer (t) ;
  cout << "operator==: " << t << " clock ticks\n" ;

  // Compare them 10000 times using memcmp
  t = StartTimer() ;
  for (int i = 0 ; i < 10000 ; i++)
    if (memcmp (&v0[0], &v1[0], v0.size()))
      cout << "Error in memcmp\n", exit (1) ;
  t = EndTimer (t) ;
  cout << "memcmp: " << t << " clock ticks\n" ;

  return 0 ;
  }

static clock_t StartTimer()
  {
  // Start on a clock tick, to enhance reproducibility
  clock_t t = clock() ;
  while (clock() == t)
    ;
  return clock() ;
  }

static clock_t EndTimer (clock_t t)
  {
  return clock() - t ;
  }


4 commentaires

@ Tonyk: Votre repère me donne ---------------------------------- STD :: égal: 437 Ticks - ---------- Opérateur ==: 453 Coques d'horloge -------------C ecclips :---------- (Utilisation de GCC 4.4.0 avec mingw). Résultant très intéressant. Heureux, je suis allé avec l'opérateur == et je n'ai pas soumis à MEMCMP


FYI: Dans la bibliothèque GNU au moins, std :: vecteur :: opérateur == enveloppe essentiellement un appel à std :: égal . Si je cours sous GCC en utilisant -O2 , la boucle autour de memcmp est optimisée, ce qui rend difficile la comparaison des résultats ...


@zitironeneis: C'est vraiment intéressant! J'ai appris quelque chose à ce sujet! Et vous avez votre réponse. (J'ai essayé de déboguer le programme, de voir ce que le compilateur de Borland faisait - mais dans la version de débogage, les variantes C ++ prennent quatre fois plus de plus, même avec -O2. Le synchronisation MEMCMP est inchangé.)


BCB pourrait ne pas être intégré en mode de débogage.



1
votes

Comme vous écrivez, vous comparez le contenu de deux fichiers. Ensuite, vous pouvez utiliser les mappe_files de Boost. Vous n'avez vraiment pas besoin de lire le fichier entier. Vous pouvez lire à la volée (de manière optimisée que Boost Soot) et arrêtez-vous lorsque vous trouvez le premier octet inégal ...

Tout comme la solution très élégante de la réponse de Cubbi ici: http://www.cplusplus.com/forum/general/94032/ Notez que juste en dessous, il ajoute également quelques points de repère qui clairement Montrer c'est le moyen le plus rapide. Je vais simplement réécrire un peu sa réponse et ajouter une vérification de taille de fichier zéro qui jette une exception autrement et joignez le test dans une fonction pour bénéficier des retours précoce: P>

#include <iostream>
#include <algorithm>
#include <boost/iostreams/device/mapped_file.hpp>
#include <boost/filesystem.hpp>

namespace io = boost::iostreams;
namespace fs = boost::filesystem;

bool files_equal(const std::string& path1, const std::string& path2)
{
    fs::path f1(path1);
    fs::path f2(path2);

    if (fs::file_size(f1) != fs::file_size(f2))
        return false;

    // zero-sized files cannot be opened with mapped_file_source
    // hence we consider all zero-sized files equal
    if (fs::file_size(f1) == 0)
        return true;

    io::mapped_file_source mf1(f1.string());
    io::mapped_file_source mf2(f1.string());
    return std::equal(mf1.data(), mf1.data() + mf1.size(), mf2.data());
}

int main()
{
    if (files_equal("test.1", "test.2"))
        std::cout << "The files are equal.\n";
    else
        std::cout << "The files are not equal.\n";
}


0 commentaires