Альтернатива вложенному циклу для сравнения

Хорошей оптимизацией было бы сначала вычислить все хэши файлов, а затем выполнить один цикл по списку.

Это в основном потому, что вам все равно придется проверять каждую пару файлов в вашем списке, но это будет означать только O (1) сложность для каждой пары вместо того, чтобы вычислять много вещей для каждого файла, который вы собираетесь проверить. .

Вы можете ввести что-то вроде:

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
  }
}

Это фактически отбросит внутренний цикл, поскольку при использовании hashSet.contains он проверит все уже добавленные файлы, но со сложностью O (1) .

Как указано в doublep, вы должны быть осторожны с производительностью, так как при простой проверке байтов вы остановитесь, как только обнаружите два разных байта, при вычислении хэша вам нужно будет проверить весь файл. Это будет хорошо работать, когда у вас много файлов или когда файл довольно мал ... Лучше всего протестировать оба подхода и посмотреть, есть ли заметные различия.

В зависимости от того, что именно вы делаете, вы можете получить значительное ускорение, никогда не сравнивая файлы разных размеров. Среди файлов одинакового размера сравнивайте только файлы с одинаковым хешем (по любому алгоритму), как это предлагается в других ответах.

РЕДАКТИРОВАТЬ:

Однако вычисление хэша может быть весьма продуктивным. Во-первых, никогда не делайте этого, если вы сравниваете файл только друг с другом: вам нужно полностью прочитать файл, чтобы построить хэш, и одного чтения уже достаточно для сравнения, поэтому вы ничего не получите.

Во-вторых, если вы редко ожидаете совпадения, а на самом деле файлы будут значительно отличаться (на ранней стадии), вычисление хэша может быть контрпродуктивным независимо от количества файлов для сравнения. Это связано с тем, что неудачное сравнение в такой ситуации завершится ошибкой раньше (т. Е. Не будет прочитан весь файл), в то время как для построения хэша вам потребуется полное чтение. В качестве альтернативы вы можете создать «частичный» хеш (например, хеш первых 10 КБ файла), но затем не забудьте использовать одинаковые фрагменты всех файлов.

Сравнение всего со всем остальным, как это, обязательно будет O (n²). Но есть уловки, которые можно попробовать. Главный из них - удешевить сравнения; это можно сделать, сгенерировав хэш-код для каждого файла и сначала сравнив их, что позволит, по крайней мере, избежать большинства сравнений (используйте достаточно хороший алгоритм, и вы избежите практически каждого). Вы также можете ускорить процесс, если вам не нужно сохранять информацию о том, какие файлы равны; создайте набор хэш-кодов для каждого файла и в конце проверьте, совпадает ли размер набора с размером списка файлов.

Одна крошечная очистка заключается в удалении теста начального размера - если размер меньше 2, он просто выпадет без каких-либо сравнений. Лучшее соблюдение соглашений о кодировании Java в циклах будет заключаться в сравнении i вместо i <= tempList.size () - 1 - это будет просто сделайте ваш код более понятным для других программистов. Ни одно из этих изменений не влияет на производительность.

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)));
    }