Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Java [игнор отключен] [закрыт для гостей] / Сравнение двух больших отсортированных файлов / 25 сообщений из 51, страница 1 из 3
16.04.2015, 19:52
    #38938661
kirill_a
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
Есть два уже отсортированных текстовых файла - один эталонный, другой новый, вида:
file1.txt :
строка1
строка2
строка3
...
file2.txt
строка1
строка2
строка4
...

Необходимо их сравнить и определить что в новом файле удалилась строка3 и добавилась строка4.
Файлы размером более гигабайта.

Есть ли готовые java библиотеки/алгоритмы для подобного сравнения?
...
Рейтинг: 0 / 0
16.04.2015, 20:00
    #38938664
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
...
Рейтинг: 0 / 0
16.04.2015, 20:11
    #38938668
kirill_a
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
Прежде чем задать вопрос сюда я, конечно, погуглил, даже ключевые слова big/large file использовал :)
Решений (достаточно оптимальных) не увидел, поэтому и спрашиваю.
...
Рейтинг: 0 / 0
16.04.2015, 20:46
    #38938676
kirill_a
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
авторI would try the following: for each file that you are comparing, create temporary files (i refer to it as partial file later) on disk representing each alphabetic letter and an additional file for all other characters. then read the whole file line by line. while doing so, insert the line into the relevant file that corresponds to the letter it starts with. since you have done that for both files, you can now limit the comparison for loading two smaller files at a time. a line starting with A for example can appear only in one partial file and there will not be a need to compare each partial file more than once. If the resulting files are still very large, you can apply the same methodology on the resulting partial files (letter specific files) that are being compared by creating files according to the second letter in them. the trade-of here would be usage of large disk space temporarily until the process is finished. in this process, approaches mentioned in other posts here can help in dealing with the partial files more efficiently.

Такой вот вариант есть.
Думаю вот как-то можно лучше найти...
...
Рейтинг: 0 / 0
17.04.2015, 14:34
    #38939282
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
kirill_aЕсть ли готовые java библиотеки/алгоритмы для подобного сравнения?
А без готовых библиотек написать десять строчек для построчного чтения из файла с последующим сравнением мешает что?.. Информация-то по условию задачи отсортирована...
...
Рейтинг: 0 / 0
17.04.2015, 15:35
    #38939374
Dogen
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
Более того, в такой постановке надо тупо сравнивать две строки .
...
Рейтинг: 0 / 0
17.04.2015, 16:51
    #38939500
kirill_a
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
Dimitry Sibiryakovkirill_aЕсть ли готовые java библиотеки/алгоритмы для подобного сравнения?
А без готовых библиотек написать десять строчек для построчного чтения из файла с последующим сравнением мешает что?.. Информация-то по условию задачи отсортирована...
Причем тут построчное сравнение?
В сравниваемый файл может добавится десяток миллионов строк. Покажи мне эти десять строчек.
Задачу решил разбивкой файла на несколько и последующее их сравнение.
...
Рейтинг: 0 / 0
17.04.2015, 17:22
    #38939541
wst
wst
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
Пока файлы заранее отсортированы - количество различий не имеет значения.
...
Рейтинг: 0 / 0
18.04.2015, 06:52
    #38939747
bochkov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
в какую нибудь embeded базу запихать файл да и запросом найти разницу
...
Рейтинг: 0 / 0
18.04.2015, 07:45
    #38939750
YamahaR1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
...
Рейтинг: 0 / 0
18.04.2015, 13:05
    #38939797
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
YamahaR1kirill_a,

https://code.google.com/p/java-diff-utils/
Думаю что diff-utils не подходит т.к. в задаче делается акцент
на размер файла. Безспорно количества оперативы у нас много
но решение должно быть экономным и изящным. Сомневаюсь
что diff-utils будет учитывать априорную инфу о сортированном
порядке rows. Да и вообще diff-utils предназначен для исходников
которые обычно невелики.
...
Рейтинг: 0 / 0
18.04.2015, 14:34
    #38939813
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
kirill_aПричем тут построчное сравнение?
В сравниваемый файл может добавится десяток миллионов строк. Покажи мне эти десять строчек.
Показываю:

1. Читаем строку1 из файла1
2. Читаем строку2 из файла2
3. Конец обоих файлов - выход
4. строка1 больше строки2 или конец файла1 - строка2 была добавлена в файла2, выводим её, читаем следующую строку2, переходим к п.3
5. строка1 меньше строки2 или конец файла2 - строка1 была удалена из файла2, выводим её, читаем следующую строку1, переходим к п.3
6. строка1 равна строке2 - ничего не делаем, переходим к п.1

Потребление памяти от размера файлов не зависит.
...
Рейтинг: 0 / 0
19.04.2015, 07:40
    #38939970
вадя
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
длина строк максимальная?
вариант с использованием базы на подходит?
закачивается файлы в базу - операция очень быстрая.
ну а показать разные строки для любой база нет проблем.
...
Рейтинг: 0 / 0
19.04.2015, 10:43
    #38940003
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
Разовью вариант с БД.

1. Поскольку БД уже есть - в ней обычно есть пользователи и схемы данных.
не будем их трогать и создадим юзера kirill специально для решения этой задчи.
Чтоб значить не было конфликтов с безопасностью.

2. Поскольку БД обычно не ужимает пустые tablespaces то желательно создать
отдельный tablespace для данной задачи kirill_tbs. После сравнения - грохнуть.

3. Надо написать скрипты для загрузки текстовых файлов в БД и котролироватьь
их код возврата. Не исключено что задачу надо будет автоматизировать.
...
Рейтинг: 0 / 0
19.04.2015, 13:10
    #38940044
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
kirill_a,

- Считываем при помощи BufferedReader
- Создаем LinkedHashMap < String , Integer >, где key - строка из эталонного файла, value - счетчик совпадений эталонной строки со строкой из второго файла
- Работаем только с map.get("строка из второго файла") , если NULL - значит такой строки нет в 1-м файле, иначе - увеличиваем счетчик совпадений
- В конце проверяем все значения на != 1

P.S.
Можно сделать за один проход
...
Рейтинг: 0 / 0
19.04.2015, 13:16
    #38940048
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
Usman,

По памяти не усрется такое решение?
...
Рейтинг: 0 / 0
19.04.2015, 13:20
    #38940050
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
Blazkowicz,

Там же хэшЫ. Думаю, что нет )
...
Рейтинг: 0 / 0
19.04.2015, 15:28
    #38940093
YamahaR1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
Usman,

Я правильно вас понимаю, вы предлагаете вычитать эталонный файл в коллекцию?
...
Рейтинг: 0 / 0
19.04.2015, 15:45
    #38940103
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
YamahaR1Usman,

Я правильно вас понимаю, вы предлагаете в Ы читать эталонный файл в коллекцию?Да
...
Рейтинг: 0 / 0
19.04.2015, 15:55
    #38940107
YamahaR1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
Usman,

Я ради интереса попробовал это сделать, возможно мой код не совсем правильный:

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
FileReader fr = new FileReader("/tmp/etalon.txt");
BufferedReader br = new BufferedReader(fr);
String str;
Map strMap = new LinkedHashMap<String, Integer>();

while ((str=br.readLine())!=null) {
   strMap.put(str, 0);
}



Сам процесс четиние занимает минут 20 после чего валится с таким исключением:
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at java.util.Arrays.copyOfRange(Arrays.java:2694)
	at java.lang.String.<init>(String.java:203)
	at java.io.BufferedReader.readLine(BufferedReader.java:349)
	at java.io.BufferedReader.readLine(BufferedReader.java:382)
	at recct.Appl.main(Appl.java:43)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:606)
	at com.intellij.rt.execution.application.AppMain.main(AppMain.java:120)



Перезапускал с Xmx6096M, но это особо не помогло. Размер файла ~1.5 Gb.
...
Рейтинг: 0 / 0
19.04.2015, 18:56
    #38940163
вадя
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
YamahaR1,
ну тогда однозначно надо в сторону базы смотреть.
...
Рейтинг: 0 / 0
19.04.2015, 19:05
    #38940166
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
YamahaR1,

Исключение по-видимому из-за использования BufferedReader'а... может слишком длинная строка ?
Проверил без использования BufferedReader : протестил чисто сам Map - полет нормальный )
...
Рейтинг: 0 / 0
19.04.2015, 20:03
    #38940171
YamahaR1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
Usman,

Строки сгенерил автоматом, т.е. они такие же как у автора:
Код: java
1.
2.
3.
4.
5.
String1
String2
String3
....
String100000000



Т.е. у меня получается около 100 млн записей в файле. Теперь попобовал в тупую загнать в цикле без считывания из файла -
все равно валится:
Код: java
1.
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space



Код:
Код: java
1.
2.
3.
4.
5.
Map strMap = new LinkedHashMap<String, Integer>();

for (int i = 0; i < 100000000; i++) {
    strMap.put("String" + i, 0);
}



Конечно у меня вроде как получается 200 млн объектов строк создается из-за ("String" + i), возможно в этом проблема...
А вы сколько записей инсертили?
...
Рейтинг: 0 / 0
20.04.2015, 04:09
    #38940254
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
YamahaR1А вы сколько записей инсертили?~21 000 000 ключей )... при -Xmx8G Но в какой-то момент все равно отвалится:
java.lang.OutOfMemoryError: Java heap space ... Несколько раз прогонял...
Падает на очередной операции со строкой (имхо)...
...
Рейтинг: 0 / 0
20.04.2015, 06:42
    #38940266
kirill_a
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение двух больших отсортированных файлов
БД не подходит, я думал еще задействовать bash diff, но в итоге остановился на разбивке файла и сравнение его по частям.
Изначально, кстати, стоял вопрос сортировки файла.
Нашел либу для сортировки com.google.code.externalsortinginjava:externalsortinginjava:0.1.9
...
Рейтинг: 0 / 0
Форумы / Java [игнор отключен] [закрыт для гостей] / Сравнение двух больших отсортированных файлов / 25 сообщений из 51, страница 1 из 3
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]