эффективная функция равенства больших строк

Question

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

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

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

В моей программе строка представляет собой простую последовательность символов с файлом и размером менее 2 ГБ, но редко полностью в памяти сразу.

Затем, попробовав некоторое время, я предполагаю, что они равны, и просто повторяю по порядку.

Все мои варианты строкового класса имеют базовый интерфейс функций int length () и char charAt (), предполагая, чтоjava chars, которые обычно, но не всегда ascii.

Любые идеи, Энди

Answer 1

Создайте метаданные о ваших гигантских строках.

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

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

Это должно дать вам хороший баланс кеширования и избавит вас от необходимости доступа к диску, не создавая при этом лишних затрат.

Answer 2

Используйте вашу ОС

Вы пробовали сравнивать контрольные суммы, такие как md5sum, рассчитанные вашей операционной системой?

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

Файловые системы

Некоторые файловые системы (brtfs, ZFS,...) иметь контрольные суммы данных, хранящихся в каждом блоке.При наличии такой файловой системы вычисление контрольной суммы всего очень большого файла должно быть не сложным.

Я хотел бы знать о таких инструментах ...

Программно

• Использовать столько потоков, сколько процессоров доступно на платформеExecutorService e = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());

• В каждом потоке откройте оба файла как READ ONLY и отобразите непересекающиеся сегменты файлов в MappedByteBuffer s:

  FileChannel fc1 = new RandomAccessFile(new File("/path/to/file1"), "ro").getChannel(); MappedByteBuffer mem1 = fc1.map(FileChannel.MapMode.READ_ONLY, offset, BUFFER_SIZE); FileChannel fc2 = new RandomAccessFile(new File("/path/to/file2"), "ro").getChannel(); MappedByteBuffer mem2 = fc2.map(FileChannel.MapMode.READ_ONLY, offset, BUFFER_SIZE);

• Вызов Arrays.equals(mem1.array(), mem2.array())

Теперь вместо перехода к случайному байту в файлах сделайте переходы к последовательным смещениям файлов, сравнивая BUFFER_SIZE байтовых кусков за раз для каждого потока в number_of_available_cores одновременно.

Настройка BUFFER_SIZE на размер блока на диске, а размер страницы в Виртуальная память должен дать желаемое ускорение.Наибольшее замедление всего сравнения будет связано с Виртуальной памятью НЕИСПРАВНОСТЬЮ СТРАНИЦЫ , SWAPPING , и хуже всего THRASHING .

См. здесь для получения дополнительной информации о мониторинге производительности кода VirtMem в Linux .В Windows VMMap может помочь.См. Также эту статью TechNet о различных счетчиках, доступных в Windows и . Эта статья, объясняющая работу VirtMem в Windows

Выше также означает, что последовательная обработка вместо случайных переходов дает лучшие результаты.результатов, поскольку это приводит к уменьшению PAGE_FAULTS и минимизации страницы VirtMem THRASHING

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

Answer 3

1. Сравнить целые блоки . Стоимость сравнения целого блока в памяти ниже, чем стоимость чтения блоков. Поэтому я должен порекомендовать, если вы читаете блок, полностью сравнивайте его содержимое.
2. Вы должны читать блоки обязательно . Чтение из файла всегда означает чтение фрагментов диска. Так что, если вы читаете из файла, попробуйте прочитать полный блок. Если вы знаете (или можете сделать вывод), насколько велик прочитанный блок, гораздо лучше. Сделайте свой кусок такого размера.
3. Выберите ваши блоки . Поскольку вы сравниваете все блоки один раз в памяти, нет смысла читать каждый блок с самого начала. Таким образом, вы можете попробовать «расширяющуюся стратегию». Начните с блока 0, затем попробуйте с 1, если они остаются равными, попробуйте с 3, с 7 и так далее. То есть, увеличивайте «смещение блока» с каждым сравниваемым блоком. Он может быть экспоненциальным (умножая block_offset на 2 каждый раз), но учтите, что этот подход дает преимущество началу файла (возможно, вы можете уменьшить смещение, пройдя середину файла).

Metadata

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

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

Надеюсь, это поможет!

Answer 4

процессоров и жестких дисков, таких как последовательное чтение данных;кешировать и обрабатывать проще.

Итак, ваш основной алгоритм будет

Выберите размер CHUNK? 16KB?Выберите, сколько СРАВНЕНИЙ, символов / байтов, которые вы хотите сравнить на CHUNK? 128 ?, убедитесь, что CHUNK кратно СРАВНЕНИЯМ Последовательное чтение CHUNK из файла 1 Последовательное чтение CHUNK из файла 2 Случайное (но последовательное) сравнение этих двух блоковдо тех пор, пока EOF или сравнения не станут равными или пока не будет достигнут какой-либо другой показатель удовлетворенности

static int CHUNK = 4096 * 16;
static int COMPARES = 128;
static int CMP_STEP = CHUNK / COMPARES
static Random RND = new Random();
static boolean AreFilesProbablyEqual(FileReader readerA, FileReader readerB) { 
 char[] buffA = new char[CHUNK];
 char[] buffB = new char[CHUNK];
 int readA = 0;
 int readB = 0;
 while(readA != -1) { // read a CHUNK at a time
  readA = readA.read(buffA);
  readB = readB.read(buffB);
  if(readA != readB) return false; // size mismatch files are not equal
  if(readA > 0) { // work through the chunk and randomly but sequentially compare
   for(int i = 0; i < readA; i = i + CMP_STEP) {
    int range = Math.min(readA - i, CMP_STEP);
    int idx = RND.next(range) + i;
    if(buffA[idx] != buffB[idx]) return false;
   }
  }
 }
 return true; // they are PROBABLY be equal
}

note Этот код был написан в браузере и не был протестирован, в результате могут присутствовать синтаксические ошибки.

Answer 5

Вероятно, не существует простого и лучшего единственного решения для этого. Вот мои два цента:

Если вы можете выполнить некоторые предварительные расчеты и сохранить данные, используйте space-time tradeoff в качестве рекомендуемого свечения .

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

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