Сравнивать два текстовых больших файла с URL в Java только с внешней памятью? - PullRequest
Новая
       13

Сравнивать два текстовых больших файла с URL в Java только с внешней памятью?

0 голосов
/ 03 декабря 2018

У меня есть следующий сценарий:

  • текстовый файл URL A
  • текстовый файл URL B

Размер каждого файла составляет около 4 ГБ.

Мне нужно вычислить:

  • все URL-адреса в A, которых нет в B
  • все URL-адреса в B, которых нет в A

Все примеры Java-diff, которые я нахожу в сети, загружают весь список в память (либо с помощью Map, либо с помощью решения MMap).Моя система не имеет подкачки и не хватает памяти, чтобы сделать это без внешней памяти.

Кто-нибудь знает решение для этого?

Этот проект может выполнять огромные сортировки файлов, не тратя тонны памяти https://github.com/lemire/externalsortinginjava

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

Ответы [ 2 ]

0 голосов
/ 03 декабря 2018

Вот суть решения, которое я придумал: https://gist.github.com/nddipiazza/16cb2a0d23ee60a07121893c26065de4

import com.google.common.collect.Sets;
import org.apache.commons.io.FileUtils;
import org.apache.commons.io.LineIterator;

import java.io.File;
import java.io.IOException;
import java.util.HashSet;
import java.util.Set;

public class DiffTextFilesUtil {
  static public int CHUNK_SIZE = 100000;

  static public class DiffResult {
    public Set<String> addedVals = new HashSet<>();
    public Set<String> removedVals = new HashSet<>();
  }

  /**
   * Gets diff result of two sorted files with each other.
   * @param lhs left hand file - sort this using com.google.code.externalsortinginjava:externalsortinginjava:0.2.5
   * @param rhs right hand file - sort this using com.google.code.externalsortinginjava:externalsortinginjava:0.2.5
   * @return DiffResult.addedVals were added from lhs to rhs. DiffResult.removedVals were removed from lhs to rhs.
   * @throws IOException
   */
  public static DiffResult diff(File lhs, File rhs) throws IOException {

    DiffResult diffResult = new DiffResult();

    LineIterator lhsIter = FileUtils.lineIterator(lhs);
    LineIterator rhsIter = FileUtils.lineIterator(rhs);

    String lhsTop = null;
    String rhsTop = null;
    while (lhsIter.hasNext()) {
      int ct = CHUNK_SIZE;

      Set<String> setLhs = Sets.newHashSet();
      Set<String> setRhs = Sets.newHashSet();
      while (lhsIter.hasNext() && --ct > 0) {
        lhsTop = lhsIter.nextLine();
        setLhs.add(lhsTop);
      }
      while (rhsIter.hasNext()) {
        if (rhsTop != null && rhsTop.compareTo(lhsTop) > 0) {
          break;
        } else if (rhsTop != null && rhsTop.compareTo(lhsTop) == 0) {
          setRhs.add(rhsTop);
          rhsTop = null;
          break;
        } else if (rhsTop != null) {
          setRhs.add(rhsTop);
        }
        rhsTop = rhsIter.next();
      }
      if (rhsTop != null) {
        setRhs.add(rhsTop);
      }
      Sets.difference(setLhs, setRhs).copyInto(diffResult.removedVals);
      Sets.difference(setRhs, setLhs).copyInto(diffResult.addedVals);
    }
    return diffResult;
  }
}
0 голосов
/ 03 декабря 2018

Если в системе достаточно памяти, вы можете сделать это через БД.Например:

Создать базу данных H2 или sqlite (данные хранятся на диске, выделите столько кеша, сколько может позволить система) Загрузить текстовый файл в таблицах A и B (создать индекс по столбцу 'url') 

select url from A where URL not in (select distinct url from B)
select url from B where URL not in (select distinct url from A)
...