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

Question

В настоящее время я пишу программу, которая должна сравнивать каждый файл в ArrayList переменного размера. Прямо сейчас я делаю это через цикл вложенного кода:

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

Я прочитал несколько разных мнений о необходимости вложенных циклов, и мне было интересно, есть ли у кого-нибудь более эффективная альтернатива.

На первый взгляд, каждое сравнение должно быть выполнено в любом случае, поэтому производительность должна быть достаточно стабильной, но я в некоторой степени убежден, что есть более чистый способ сделать это. Есть указатели?

EDIT :: Это только часть функции, для ясности. Файлы были сравнены и помещены в сегменты на основе длины - после просмотра карты набора и нахождения блока, длина которого превышает один, выполняется это. Итак, это все файлы одинакового размера. Я буду делать сравнение контрольной суммы, прежде чем доберусь до байтов, но сейчас я просто пытаюсь очистить цикл.

Кроме того, святая корова, этот сайт быстро реагирует. Спасибо, ребята.

EDIT2 :: Извините, для дальнейшего разъяснения: Я считаю, что часть обработки файла у меня достаточно приличная - сначала я сравниваю и сортирую по длине, затем по контрольной сумме, затем по байтам - проблема у меня заключается в как правильно справиться с необходимостью эффективного сравнения всех файлов в ArrayList, при условии, что все они должны сравниваться. Если для этого достаточно вложенного цикла, это круто, я просто хотел убедиться, что это подходящий метод, условно.

Answer 1

Мой ответ на ваш вопрос EDIT2 состоит из двух частей

Часть состоит в том, что если у вас есть небольшое количество файлов, то ваш подход с вложенным циклом должен быть в порядке. Производительность составляет O(N**2), а оптимальное решение - O(N). Однако, если N достаточно мало, это не будет иметь большого значения, какой подход вы используете. Вам нужно рассмотреть альтернативное решение, только если вы уверены, что N может быть большим.

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

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

2. Создание HashMap<FileHash, List<File>> экземпляра карты.

3. Для каждого File на вашем входе ArrayList:

   1. Рассчитать хеш для файла и создать для него объект FileHash.
   2. Поиск FileHash на карте:
   3. Если вы нашли запись, проведите побайтное сравнение вашего текущего файла с каждым из файлов в списке, который вы получили с карты. Если вы найдете дубликат файла в списке, BINGO! В противном случае добавьте текущий файл в список.
   4. Если вы не нашли запись, создайте новую запись карты с ключом FileHash и текущим файлом в качестве первого элемента списка значений.

(Обратите внимание, что приведенная выше карта на самом деле является многокарточной, и что доступны сторонние реализации; например, в коллекциях Apache Commons и Google. Я представил алгоритм в приведенной выше форме для простоты. )

Некоторые проблемы с производительностью:

• Если вы используете хорошую криптографическую хеш-функцию для генерации файловых хешей, то шансы найти запись в 3.3, содержащую более одного элемента в списке, ничтожно малы, а шансы, что побайтово Сравнение файлов не скажет, что файлы равны, также исчезающе мало. Однако стоимость вычисления крипто-хэша будет больше, чем стоимость вычисления хеш-функции низкого качества.

• Если вы используете хэш более низкого качества, вы можете уменьшить потенциальную стоимость сравнения большего количества файлов, посмотрев на размеры файлов перед выполнением побайтного сравнения. Если вы сделаете это, вы можете сделать тип карты HashMap<FileHash, List<FileTuple>>, где FileTuple - это класс, который содержит как File, так и его длину.

• Потенциально можно уменьшить стоимость хеширования, используя хэш, равный, скажем, первому блоку каждого файла. Но это увеличивает вероятность того, что два файла могут иметь один и тот же хэш, но все же различаться; например во 2-м блоке. Важность этого зависит от характера файлов. (Но, например, если вы просто проверили контрольную сумму первых 256 байтов коллекции файлов исходного кода, вы можете получить огромное количество коллизий ... из-за наличия идентичных заголовков авторских прав!)

Answer 2

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

Это в основном потому, что вам все равно придется проверять каждую пару файлов вашего списка, но это будет означать только 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, вы должны быть осторожныо производительности, так как, когда вы явно проверяете байты, вы останавливаетесь, как только вы найдете два разных байта, при вычислении хеша потребуется проверить весь файл.Это будет хорошо работать, когда у вас много файлов или файл довольно небольшой. Лучшее, что можно сделать, это сравнить оба подхода и посмотреть, есть ли заметные различия.

Answer 3

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

EDIT:

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

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

Answer 4

Одной крошечной очисткой будет удаление начального размера теста - если размер меньше 2, он просто выпадет без каких-либо сравнений. Лучшее следование соглашениям по Java-кодированию будет в циклах сравнивать i < tempList.size() вместо 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)));
    }

Answer 5

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