|
|
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Есть два уже отсортированных текстовых файла - один эталонный, другой новый, вида: file1.txt : строка1 строка2 строка3 ... file2.txt строка1 строка2 строка4 ... Необходимо их сравнить и определить что в новом файле удалилась строка3 и добавилась строка4. Файлы размером более гигабайта. Есть ли готовые java библиотеки/алгоритмы для подобного сравнения? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.04.2015, 19:52 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.04.2015, 20:00 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Прежде чем задать вопрос сюда я, конечно, погуглил, даже ключевые слова big/large file использовал :) Решений (достаточно оптимальных) не увидел, поэтому и спрашиваю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.04.2015, 20:11 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
автор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. Такой вот вариант есть. Думаю вот как-то можно лучше найти... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.04.2015, 20:46 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
kirill_aЕсть ли готовые java библиотеки/алгоритмы для подобного сравнения? А без готовых библиотек написать десять строчек для построчного чтения из файла с последующим сравнением мешает что?.. Информация-то по условию задачи отсортирована... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.04.2015, 14:34 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Более того, в такой постановке надо тупо сравнивать две строки . ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.04.2015, 15:35 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Dimitry Sibiryakovkirill_aЕсть ли готовые java библиотеки/алгоритмы для подобного сравнения? А без готовых библиотек написать десять строчек для построчного чтения из файла с последующим сравнением мешает что?.. Информация-то по условию задачи отсортирована... Причем тут построчное сравнение? В сравниваемый файл может добавится десяток миллионов строк. Покажи мне эти десять строчек. Задачу решил разбивкой файла на несколько и последующее их сравнение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.04.2015, 16:51 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Пока файлы заранее отсортированы - количество различий не имеет значения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.04.2015, 17:22 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
в какую нибудь embeded базу запихать файл да и запросом найти разницу ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.04.2015, 06:52 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.04.2015, 07:45 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
YamahaR1kirill_a, https://code.google.com/p/java-diff-utils/ Думаю что diff-utils не подходит т.к. в задаче делается акцент на размер файла. Безспорно количества оперативы у нас много но решение должно быть экономным и изящным. Сомневаюсь что diff-utils будет учитывать априорную инфу о сортированном порядке rows. Да и вообще diff-utils предназначен для исходников которые обычно невелики. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.04.2015, 13:05 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
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 Потребление памяти от размера файлов не зависит. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.04.2015, 14:34 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
длина строк максимальная? вариант с использованием базы на подходит? закачивается файлы в базу - операция очень быстрая. ну а показать разные строки для любой база нет проблем. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.04.2015, 07:40 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Разовью вариант с БД. 1. Поскольку БД уже есть - в ней обычно есть пользователи и схемы данных. не будем их трогать и создадим юзера kirill специально для решения этой задчи. Чтоб значить не было конфликтов с безопасностью. 2. Поскольку БД обычно не ужимает пустые tablespaces то желательно создать отдельный tablespace для данной задачи kirill_tbs. После сравнения - грохнуть. 3. Надо написать скрипты для загрузки текстовых файлов в БД и котролироватьь их код возврата. Не исключено что задачу надо будет автоматизировать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.04.2015, 10:43 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
kirill_a, - Считываем при помощи BufferedReader 'а - Создаем LinkedHashMap < String , Integer >, где key - строка из эталонного файла, value - счетчик совпадений эталонной строки со строкой из второго файла - Работаем только с map.get("строка из второго файла") , если NULL - значит такой строки нет в 1-м файле, иначе - увеличиваем счетчик совпадений - В конце проверяем все значения на != 1 P.S. Можно сделать за один проход ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.04.2015, 13:10 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Usman, По памяти не усрется такое решение? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.04.2015, 13:16 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Blazkowicz, Там же хэшЫ. Думаю, что нет ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.04.2015, 13:20 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Usman, Я правильно вас понимаю, вы предлагаете вычитать эталонный файл в коллекцию? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.04.2015, 15:28 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
YamahaR1Usman, Я правильно вас понимаю, вы предлагаете в Ы читать эталонный файл в коллекцию?Да ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.04.2015, 15:45 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Usman, Я ради интереса попробовал это сделать, возможно мой код не совсем правильный: Код: java 1. 2. 3. 4. 5. 6. 7. 8. Сам процесс четиние занимает минут 20 после чего валится с таким исключением: Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Перезапускал с Xmx6096M, но это особо не помогло. Размер файла ~1.5 Gb. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.04.2015, 15:55 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
YamahaR1, ну тогда однозначно надо в сторону базы смотреть. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.04.2015, 18:56 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
YamahaR1, Исключение по-видимому из-за использования BufferedReader'а... может слишком длинная строка ? Проверил без использования BufferedReader : протестил чисто сам Map - полет нормальный ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.04.2015, 19:05 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Usman, Строки сгенерил автоматом, т.е. они такие же как у автора: Код: java 1. 2. 3. 4. 5. Т.е. у меня получается около 100 млн записей в файле. Теперь попобовал в тупую загнать в цикле без считывания из файла - все равно валится: Код: java 1. Код: Код: java 1. 2. 3. 4. 5. Конечно у меня вроде как получается 200 млн объектов строк создается из-за ("String" + i), возможно в этом проблема... А вы сколько записей инсертили? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.04.2015, 20:03 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
YamahaR1А вы сколько записей инсертили?~21 000 000 ключей )... при -Xmx8G Но в какой-то момент все равно отвалится: java.lang.OutOfMemoryError: Java heap space ... Несколько раз прогонял... Падает на очередной операции со строкой (имхо)... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.04.2015, 04:09 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
БД не подходит, я думал еще задействовать bash diff, но в итоге остановился на разбивке файла и сравнение его по частям. Изначально, кстати, стоял вопрос сортировки файла. Нашел либу для сортировки com.google.code.externalsortinginjava:externalsortinginjava:0.1.9 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.04.2015, 06:42 |
|
||
|
|

start [/forum/topic.php?fid=59&msg=38940048&tid=2123804]: |
0ms |
get settings: |
9ms |
get forum list: |
19ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
107ms |
get topic data: |
12ms |
get forum data: |
3ms |
get page messages: |
87ms |
get tp. blocked users: |
2ms |
| others: | 235ms |
| total: | 480ms |

| 0 / 0 |
