Alternative à la Boucle Imbriquée Pour la Comparaison

Je suis en train d'écrire un programme qui a besoin de comparer chaque fichier dans une liste de tableaux de taille variable. Maintenant, la façon dont je le fais c'est par le biais d'un code imbriqué boucle:

         if(tempList.size()>1){
            for(int i=0;i<=tempList.size()-1;i++)
                //Nested loops.  I should feel dirty?
                for(int j=i+1;j<=tempList.size()-1;j++){
                    //*Gets sorted.
                    System.out.println(checkBytes(tempList.get(i), tempList.get(j)));
                }
            }

J'ai lu quelques divergences d'opinion sur la nécessité de boucles imbriquées, et je me demandais si quelqu'un avait une alternative plus efficace.

En un clin d'œil, chaque comparaison est besoin de le faire, de toute façon, de sorte que la performance devrait être assez stable, mais je suis moyennement convaincu, il y a une manière plus propre de le faire. Les pointeurs?

EDIT:: Ce n'est qu'une partie de la fonction, pour plus de clarté. Les fichiers ont été comparés et mis dans des seaux en fonction de la longueur - après la carte de l'ensemble, et de trouver un seau qui est supérieure à une longueur, il s'exécute. Donc, - ce sont tous les fichiers de la même taille. Je vais faire une comparaison de la somme de contrôle avant d'en arriver à d'octets en tant que bien, mais pour l'instant je suis juste en train de nettoyer la boucle.

Aussi, ah la vache, ce site répond rapidement. Merci, les gars.

EDIT2:: Désolé, pour plus de précisions: La gestion des fichiers de la partie j'ai un décent comprendre, je pense - tout d'abord, j'ai comparer et les trier par taille, par la somme de contrôle, puis en octets - le problème que j'ai est de savoir comment traiter correctement avoir besoin de comparer tous les fichiers dans la liste de tableaux efficacement, en supposant qu'ils ont tous besoin d'être comparés. Si une boucle imbriquée est suffisant pour ce faire, c'est cool, je voulais juste vérifier que c'était une méthode appropriée, la convention-sage.

Je voudrais garder de cette façon. Je ne vois pas le moyen le plus propre de faire les n(n-1)/2 comparaisons.
Il semble que vous peut-être de chaque comparaison, deux fois, depuis checkBytes(a,b) est la même que checkBytes(b,a).
Il n'y a vraiment rien de mal avec l'aide de boucles imbriquées, si vous avez vraiment besoin d'eux. La comparaison de paires de arraylist devrait certainement être un de ces cas. Votre code ne peut pas vraiment être amélioré, sans peut-être davantage de connaissance de l'checkBytes fonction.
Non, parce qu'il a la borne inférieure de l'intérieur de la boucle de droite.
@Jack et @Donal Boursiers réponses déjà l'adresse de "EDIT2" partie de votre question. Ce que vous ne comprenez pas?

OriginalL'auteur KGVT | 2010-04-23

3

Ma réponse à votre EDIT2 question est en deux parties

La partie est que si vous avez un petit nombre de fichiers, puis votre boucle imbriquée à l'approche doit être fine. La performance est O(N**2) et la solution optimale est O(N). Toutefois, si N est assez petit, il ne fera pas beaucoup de différence de l'approche que vous utilisez. Vous avez seulement besoin d'envisager une solution alternative si vous êtes sûr que N peut être grande.

La deuxième partie décrit un algorithme qui exploite les hachages de fichier pour obtenir un O(N) solution pour la détection des doublons. C'est ce que les réponses précédentes a fait allusion.
1. Créer un FileHash classe pour représenter fichier de valeurs de hachage. Ce doit définir equals(Object) et hashCode() méthodes qui implémentent octet-sage de l'égalité des hachages de fichier.
2. Créer un HashMap<FileHash, List<File>> carte instance.
3. Pour chaque File dans votre entrée ArrayList:
  1. Calculer la valeur de hachage du fichier, et de créer un FileHash objet.
  2. La recherche de la FileHash sur la carte:
  3. Si vous avez trouvé une entrée, d'effectuer un byte-sage de la comparaison de votre fichier actuel avec chacun des fichiers dans la liste que vous avez obtenu à partir de la carte. Si vous trouvez un fichier en double dans la liste, BINGO! Sinon ajouter un fichier à la liste.
  4. Si vous n'avez pas trouvé une entrée, créer une nouvelle entrée de la table avec le "FileHash" comme la touche, et le fichier en cours comme le premier élément de la liste de valeurs.
(À noter que la carte ci-dessus est vraiment un multi-carte, et qu'il y a de la 3e partie implémentations disponibles; par exemple, dans Apache commons collections et Google collections. J'ai présenté l'algorithme dans le formulaire ci-dessus pour des raisons de simplicité.)

Certains problèmes de performances:
- Si vous utilisez une bonne fonction de hachage cryptographique pour générer votre fichier de tables de hachage, alors les chances de trouver une entrée dans 3.3 qui a plus d'un élément dans la liste sont extrêmement petite, et les chances que le byte-sage de la comparaison des fichiers ne pourront pas dire que les fichiers sont égaux est également extrêmement petite. Cependant, le coût de calcul de la crypto de hachage sera plus élevé que le coût de calcul d'une baisse de la qualité de hachage.
- Si vous utilisez une diminution de la qualité de hachage, vous pouvez réduire le coût potentiel de comparer plusieurs fichiers en regardant la taille des fichiers avant que vous ne le byte-sage de comparaison. Si vous faites cela, vous pouvez faire le type de carte HashMap<FileHash, List<FileTuple>> où FileTuple est une classe qui possède à la fois un File et sa longueur.
- Vous pourrait potentiellement réduire le coût de hachage en utilisant une table de hachage de juste (dire), le premier bloc de chaque fichier. Mais cela augmente la probabilité que deux fichiers ont le même hash, mais encore être différentes; par exemple, dans le 2e bloc. Si c'est significatif dépend de la nature des fichiers. (Mais par exemple, si vous venez de somme les 256 premiers octets d'une collection de fichiers de code source, vous pourriez obtenir un grand nombre de collisions ... en raison de la présence de l'identique le droit d'auteur têtes!)
OriginalL'auteur Stephen C
3

Une bonne optimisation serait de calculer la première de toutes les valeurs de hachage des fichiers et ensuite faire une boucle sur la liste.

Ce essentiellement parce que vous aurez de toute façon à vérifier chaque paire de fichiers de votre liste, mais cela signifie juste un O(1) de la complexité pour chaque paire au lieu que le calcul de beaucoup de choses, pour chacun, vous allez vérifier.

Vous pouvez aller quelque chose comme:
```
HashSet<YourFile> fileSet = new HashSet<YourFile>();
ArrayList<YourFile> files = new ArrayList<YourFile>();

class YourFile
{
  int hashcode = -1;

  public int hashCode()
  {
     //override it to provide an hashcode based on file contents
     //you can also cache it to avoid recalculating anything

     if (hashcode == -1)
       hashcode = calculateIt();

     return hashcode;
  }
}

//fill up files
files.add(...);

//do comparisons
for (YourFile f : files)
{
  if (fileSet.contains(f))
    //f and fileSet.get(f) are equal: this is a tricky utilization of the hashCode() method so be careful about it!
  else
  {
    fileSet.put(f);
    //since there's not a file with same hashcode you just add this one
  }
}
```
Ce sera fait tomber la boucle interne, car lorsque vous utilisez hashSet.contains il va vérifier toutes les déjà les fichiers ajoutés, mais avec un O(1) de la complexité.

Comme indiqué à partir de doublep vous devez être prudent sur les spectacles, car lorsque vous simplement vérifier les octets de vous arrêter dès que vous trouvez deux octets différents lors du calcul de la valeur de hachage aurez besoin de vérifier l'ensemble du fichier. Cela fonctionne bien lorsque vous avez de nombreux fichiers ou lorsque le fichier sont plutôt petits.. la meilleure chose à faire serait de comparer les deux approches et de voir si il y a des différences notables.

Cet algorithme est un peu mal. Votre code n'est pas de traiter le cas où la hashCode pour les deux fichiers sont identiques, mais les fichiers ne sont pas égaux. Puisque vous utilisez hashCode qui renvoie uniquement 2**32 valeurs distinctes, la probabilité de ce qui se passe ne peut pas être ignoré.
Selon le paradoxe d'anniversaire, vous aurez besoin d'au moins 2*(2**16) les fichiers d'avoir une collision avec une grande probabilité. Étant donné toutefois que dans la pratique, vous finirez par avoir une faible quantité d'entre eux (ou, au moins, je suppose que nous ne parlons pas des millions de fichiers), nous pouvons vous suffit de cocher les fichiers à l'aide d'une approche normale si elles résultent de l'égalité. Ne pas tuer la performance.

OriginalL'auteur Jack
2

Selon ce exactement que vous faites, vous pourriez obtenir une considérable accélération et de ne jamais comparer des fichiers de différentes tailles. Parmi les dossiers de la même taille que de comparer ceux ayant le même hash (quel que soit l'algorithme), comme suggéré dans d'autres réponses.

EDIT:

De calcul du hachage peut être conunterproductive, cependant. Tout d'abord, ne jamais faire si vous comparez le fichier seulement l'un contre l'autre: vous avez besoin de lire le fichier entièrement pour construire une table de hachage, et de lire est déjà assez à des fins de comparaison, de sorte que vous ne gagnez rien.

Deuxième, si vous rarement s'attendre à un match et en fait des fichiers diffèrent considérablement (au début), le calcul de la valeur de hachage peut être contre-productif, peu importe le nombre de fichiers à comparer. C'est parce que l'échec de la comparaison dans une telle situation va échouer tôt (c'est à dire ne pas lire le fichier entier), alors que pour un hachage bâtiment, vous aurez besoin d'un accès complet en lecture. Alternativement, vous pouvez construire "partielle" de hachage (par exemple, une valeur de hachage de la première tranche de 10 ko d'un fichier), mais n'oubliez pas d'utiliser l'égalité des morceaux de tous les fichiers.

OriginalL'auteur doublep
1

Comparaison de tout avec tout le reste comme c'est lié à O(n2). Mais il y a des trucs que vous pouvez essayer. La principale est de faire des comparaisons moins cher, ce qui peut être fait en générant un code de hachage pour chaque fichier et en les comparant à ceux de la première, qui permettra au moins d'éviter la majorité des comparaisons (utiliser un assez bon algorithme et vous éviter pratiquement tous). Vous pouvez aussi accélérer les choses si vous n'avez pas besoin de conserver des informations sur les fichiers qui sont égaux; produire un Set de hashcodes de chaque fichier et à la fin du test pour voir si la taille de la série est la même que la taille de la liste de fichiers.

Notez que je suis en supposant que vous êtes comparaison pour l'égalité entre les hommes. Si non, et vous ne pouvez pas capturer l'essence de ce que vous êtes en comparant dans une table de hachage, alors vous avez déjà obtenu le meilleur algorithme de base.
Selon le contenu des fichiers, ce qui peut être plus lent (donc quand ils sont très longs et le contenu aléatoire). Parce que les comparaisons peuvent mettre un terme plus tôt alors qu'un typique hashCode() de la mise en œuvre serait de regarder la totalité du fichier. Bien sûr, vous pourriez hachage une partie du fichier, mais alors vous pouvez obtenir un bon nombre de collisions et la comparaison ne doit pas nécessairement être séquentielle.

OriginalL'auteur Donal Fellows
1

Un petit nettoyage serait de retirer de la taille initiale de test - si la taille est inférieure à 2, il va tout simplement tomber sans avoir fait aucun comparaisons. Une meilleure adhérence à Java conventions de codage, de boucles, de comparer i < tempList.size() au lieu de i <= tempList.size() - 1 - qui va simplement rendre votre code plus facile pour d'autres programmeurs à comprendre. Aucune de ces modifications a tout impact sur les performances.
```
for (int i = 0; i < tempList.size(); i++)
    for (int j = i + 1; j < tempList.size(); j++) {
        //*Gets sorted.
        System.out.println(checkBytes(tempList.get(i), tempList.get(j)));
    }
```
Merci, c'était un peu idiot de moi.
Subquestion: Cette fonction exécute plusieurs fois au cours du programme, et je m'attends à la plupart des ArrayLists produits pour être de taille 1, étant donné que ce programme est en train de vérifier les fichiers dupliqués, et la plupart des fichiers seront (je l'espère) être unique - la suppression de l'instruction if signifie qu'il vérifie et entre dans la première boucle for, et puis des contrôles et de l'échec de la deuxième boucle, le sens qu'il a effectué deux comparaisons au lieu d'un. Il est relativement mineur, mais est-ce encore une bonne action à prendre? Ou ne s'attendait à une échouent la plupart du temps, nier le besoin de la changer?
Je ne crois pas que cela peut faire une différence mesurable sur tout système moderne. Oui, techniquement, c'est une comparaison supplémentaire dans le cas le plus courant, mais c'est juste pas assez grand à la matière. Si votre programme est trop lent, l'instrument et de trouver les goulots d'étranglement; je ne crois pas que ce sera l'un d'eux.
La première boucle devrait avoir la condition i < tempList.size() - 1, ou la dernière fois à travers la première boucle de la deuxième boucle ne serait jamais exécuter.
Il n'y a pas de mal à une boucle de zéro fois.

OriginalL'auteur Carl Manaster

Vous devez vous connecter pour publier un commentaire.