Быстрый способ сравнения входных потоков

У меня проблема, мне нужно быстро сравнить два входных потока.

Сегодня у меня есть такая функция:

private boolean isEqual(InputStream i1, InputStream i2) throws IOException {

    try {
        // do the compare
        while (true) {
            int fr = i1.read();
            int tr = i2.read();

            if (fr != tr)
                return false;

            if (fr == -1)
                return true;
        }

    } finally {
        if (i1 != null)
            i1.close();
        if (i2 != null)
            i2.close();
    }
}

Но это очень медленно. Я хочу использовать буферизованное чтение, но пока не нашел хорошего способа сделать это.

Некоторые дополнительные вещи, которые усложняют задачу:

  • Я не хочу читать один из входных потоков в память (весь)
  • Я не хочу использовать стороннюю библиотеку

Мне нужно практическое решение - код! :)


person dacwe    schedule 22.11.2010    source источник
comment
Не думаю, что можно что-то сравнивать, не читая в памяти. Вы действительно имеете в виду чтение всего входного потока в память, что означает чтение фиксированного количества байтов?   -  person Patrick    schedule 22.11.2010
comment
Я имел в виду, что чтение всего потока ввода в память не вариант   -  person dacwe    schedule 22.11.2010


Ответы (4)


Безусловно, я предпочитаю использовать вспомогательный класс org.apache.commons.io.IOUtils из библиотеки Apache Commons IO:

IOUtils.contentEquals( is1, is2 );
person Snicolas    schedule 15.12.2012

Что-то вроде этого может сделать:

private static boolean isEqual(InputStream i1, InputStream i2)
        throws IOException {

    ReadableByteChannel ch1 = Channels.newChannel(i1);
    ReadableByteChannel ch2 = Channels.newChannel(i2);

    ByteBuffer buf1 = ByteBuffer.allocateDirect(1024);
    ByteBuffer buf2 = ByteBuffer.allocateDirect(1024);

    try {
        while (true) {

            int n1 = ch1.read(buf1);
            int n2 = ch2.read(buf2);

            if (n1 == -1 || n2 == -1) return n1 == n2;

            buf1.flip();
            buf2.flip();

            for (int i = 0; i < Math.min(n1, n2); i++)
                if (buf1.get() != buf2.get())
                    return false;

            buf1.compact();
            buf2.compact();
        }

    } finally {
        if (i1 != null) i1.close();
        if (i2 != null) i2.close();
    }
}
person aioobe    schedule 22.11.2010
comment
@dacwe, я могу гарантировать, что он медленнее, чем решение, которое я предоставил. ;) - person Peter Lawrey; 22.11.2010
comment
allocateDirect должен предоставить вам прямой байтовый буфер (с собственной низкоуровневой реализацией), который должен быть быстрее, чем обычный байтовый буфер. - person aioobe; 22.11.2010
comment
@ Питер Лоури, ты уверен? Вы используете байтовый массив, управляемый JVM, с прямым байтовым буфером вы становитесь на шаг ближе к кремнию :-) - person aioobe; 22.11.2010
comment
Это делает read () быстрее, однако get () медленнее, чем обращение к byte [] в качестве вызова JNI. - person Peter Lawrey; 22.11.2010
comment
В любом случае для файла здесь важнее размер буфера. Примечание: буфер прямой памяти всегда будет использовать количество страниц памяти, кратное странице памяти, даже если вы не можете его использовать. (4KB на большинстве машин). - person Peter Lawrey; 22.11.2010
comment
Если это узкое место, он может легко slice() увеличить буфер и использовать compareTo метод. - person aioobe; 22.11.2010
comment
Вы также можете использовать буфер размером 64 КБ и сравнивать getLong () вместо одного байта за раз. - person Peter Lawrey; 22.11.2010
comment
Использование DirectByteBuffer добавит ценность только в том случае, если подчиненные InputStreams являются FileInputStreams и могут перемещать данные непосредственно из файла в DirectByteBuffer без необходимости перехода памяти в управляемую память jvm. Допустим, это обычный InputStream, поддерживаемый чем-то другим, кроме File. В этом случае вы перемещаете память из jvm (источник InputStream) в собственный (DirectByteBuffer), а затем обратно в jvm (при вызове buf.get ()) для целей сравнения. - person Brett Okken; 01.07.2013
comment
Этот код кажется неправильным. Если один канал передает байты очень быстро, а другой - очень медленно, один канал первым попадет в EOF, пока в другом канале еще есть символы, ожидающие чтения. Этот код, однако, предполагает, что буферы имеют неодинаковую длину. - person yiding; 15.03.2016
comment
О чем ты говоришь? Если медленный поток не будет фактически закрыт, операция чтения либо заблокирует, либо вернет ноль (никакие байты не могут быть прочитаны немедленно). Оба случая обрабатываются отлично. - person aioobe; 15.03.2016

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

private boolean isEqual(InputStream i1, InputStream i2) throws IOException {
    byte[] buf1 = new byte[64 *1024];
    byte[] buf2 = new byte[64 *1024];
    try {
        DataInputStream d2 = new DataInputStream(i2);
        int len;
        while ((len = i1.read(buf1)) > 0) {
            d2.readFully(buf2,0,len);
            for(int i=0;i<len;i++)
              if(buf1[i] != buf2[i]) return false;
        }
        return d2.read() < 0; // is the end of the second file also.
    } catch(EOFException ioe) {
        return false;
    } finally {
        i1.close();
        i2.close();
    }
}
person Peter Lawrey    schedule 22.11.2010
comment
Итак, как мне это сделать - например, практическое решение? - person dacwe; 22.11.2010
comment
@dacwe: выделите два байтовых буфера byte[] buf1 = new byte[BlockSize]; byte[] buf2 = new byte[BlockSize]; и сравните buf1 и buf2 после считывания данных в эти два буфера из i1 и i2. - person Patrick; 22.11.2010
comment
@patrick, Питер Лоури: Ну, это не так-то просто .. :) Сфуссенеггер думал, что у него это было, но он тоже ошибался. - person dacwe; 22.11.2010
comment
@dacwe, что не так просто? - person Peter Lawrey; 22.11.2010
comment
ReadFully гарантирует, что из обоих потоков считывается одинаковый объем данных, это упрощает сравнение и позволяет избежать необходимости упаковки / сжатия любых оставшихся данных. - person Peter Lawrey; 22.11.2010
comment
Вы можете захотеть вернуть false на EOFException (выдается, когда readFully попадает в EOF), но разрешить IOException выйти из метода (потому что произошла другая ошибка чтения). - person Jonathan; 22.11.2010
comment
@jonathan, я бы не стал, но OP мог бы, так как приведен пример. Спасибо. - person Peter Lawrey; 22.11.2010
comment
Вау, я использовал ваше решение и заменил цикл for на Arrays # equals. Для файла размером 200 МБ это в два раза быстрее. Я думаю, это потому, что это метод HotSpotIntrinsicCandidate. - person kai; 29.11.2019

почему бы просто не обернуть оба потока в самом начале вашего метода:

i1 = new BufferedInputStream(i1);
i2 = new BufferedInputStream(i2);

В качестве альтернативы вы можете просто попробовать прочитать оба потока в буфер:

public static boolean equals(InputStream i1, InputStream i2, int buf) throws IOException {
    try {
        // do the compare
        while (true) {
            byte[] b1 = new byte[buf];
            byte[] b2 = new byte[buf];

            int length = i1.read(b1);
            if (length == -1) {
                return i2.read(b2, 0, 1) == -1;
            }

            try {
                StreamUtils.readFully(i2, b2, 0, length);
            } catch (EOFException e) {
                // i2 is shorter than i1
                return false;
            }

            if (!ArrayUtils.equals(b1, b2, 0, length)) {
                return false;
            }
        }
    } finally {
        // simply close streams and ignore (log) exceptions
        StreamUtils.close(i1, i2);
    }
}

// StreamUtils.readFully(..) 
public static void readFully(InputStream in, byte[] b, int off, int len) throws EOFException, IOException {
    while (len > 0) {
        int read = in.read(b, off, len);
        if (read == -1) {
            throw new EOFException();
        }
        off += read;
        len -= read;
    }
}

// ArrayUtils.equals(..)
public static boolean equals(byte[] a, byte[] a2, int off, int len) {
    if (off < 0 || len < 0 || len > a.length - off || len > a2.length - off) {
        throw new IndexOutOfBoundsException();
    } else if (len == 0) {
        return true;
    }

    if (a == a2) {
        return true;
    }
    if (a == null || a2 == null) {
        return false;
    }

    for (int i = off; i < off + len; i++) {
        if (a[i] != a2[i]) {
            return false;
        }
    }

    return true;
}

РЕДАКТИРОВАТЬ: я исправил свою реализацию. Вот так это выглядит без DataInputStream или NIO. Код доступен на GitHub или на Репозиторий снимков OSS Sonatype Maven:

<dependency>
  <groupId>at.molindo</groupId>
  <artifactId>molindo-utils</artifactId>
  <version>1.0-SNAPSHOT</version>
</dependency>
person sfussenegger    schedule 22.11.2010
comment
read для этого не указан (может возвращать, не читая полный ввод!) - person dacwe; 22.11.2010
comment
Кроме того, можно ли предсказать, что содержит, скажем, b1[1023], если length=100? - person khachik; 22.11.2010
comment
Я не смог найти Arrays.equals (b1, b2, 0, length) - person Peter Lawrey; 22.11.2010
comment
@dacwe Я сам это заметил. Поэтому я добавил комментарий FIXME - работа продолжается;) @khachik Что вы имеете в виду под атомарным чтением? @peter Arrays.equals (..) на самом деле является частной библиотекой утилит, которую я использую, по моей вине, хотя она была в java.util.Arrays ... собираюсь добавить - person sfussenegger; 22.11.2010