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

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

Есть ли готовые java библиотеки/алгоритмы для подобного сравнения?
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38938664
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38938668
kirill_a
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Прежде чем задать вопрос сюда я, конечно, погуглил, даже ключевые слова big/large file использовал :)
Решений (достаточно оптимальных) не увидел, поэтому и спрашиваю.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #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
Сравнение двух больших отсортированных файлов
    #38939282
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kirill_aЕсть ли готовые java библиотеки/алгоритмы для подобного сравнения?
А без готовых библиотек написать десять строчек для построчного чтения из файла с последующим сравнением мешает что?.. Информация-то по условию задачи отсортирована...
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38939374
Фотография Dogen
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Более того, в такой постановке надо тупо сравнивать две строки .
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38939500
kirill_a
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dimitry Sibiryakovkirill_aЕсть ли готовые java библиотеки/алгоритмы для подобного сравнения?
А без готовых библиотек написать десять строчек для построчного чтения из файла с последующим сравнением мешает что?.. Информация-то по условию задачи отсортирована...
Причем тут построчное сравнение?
В сравниваемый файл может добавится десяток миллионов строк. Покажи мне эти десять строчек.
Задачу решил разбивкой файла на несколько и последующее их сравнение.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38939541
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пока файлы заранее отсортированы - количество различий не имеет значения.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38939747
bochkov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
в какую нибудь embeded базу запихать файл да и запросом найти разницу
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38939750
YamahaR1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38939797
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
YamahaR1kirill_a,

https://code.google.com/p/java-diff-utils/
Думаю что diff-utils не подходит т.к. в задаче делается акцент
на размер файла. Безспорно количества оперативы у нас много
но решение должно быть экономным и изящным. Сомневаюсь
что diff-utils будет учитывать априорную инфу о сортированном
порядке rows. Да и вообще diff-utils предназначен для исходников
которые обычно невелики.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #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
Сравнение двух больших отсортированных файлов
    #38939970
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
длина строк максимальная?
вариант с использованием базы на подходит?
закачивается файлы в базу - операция очень быстрая.
ну а показать разные строки для любой база нет проблем.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38940003
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Разовью вариант с БД.

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

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

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

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

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

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

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

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

Я правильно вас понимаю, вы предлагаете в Ы читать эталонный файл в коллекцию?Да
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #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
Сравнение двух больших отсортированных файлов
    #38940163
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
YamahaR1,
ну тогда однозначно надо в сторону базы смотреть.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38940166
Фотография Usman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
YamahaR1,

Исключение по-видимому из-за использования BufferedReader'а... может слишком длинная строка ?
Проверил без использования BufferedReader : протестил чисто сам Map - полет нормальный )
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #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
Сравнение двух больших отсортированных файлов
    #38940254
Фотография Usman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
YamahaR1А вы сколько записей инсертили?~21 000 000 ключей )... при -Xmx8G Но в какой-то момент все равно отвалится:
java.lang.OutOfMemoryError: Java heap space ... Несколько раз прогонял...
Падает на очередной операции со строкой (имхо)...
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38940266
kirill_a
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
БД не подходит, я думал еще задействовать bash diff, но в итоге остановился на разбивке файла и сравнение его по частям.
Изначально, кстати, стоял вопрос сортировки файла.
Нашел либу для сортировки com.google.code.externalsortinginjava:externalsortinginjava:0.1.9
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38940423
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kirill_a, сильно удивишся но любая операционка содержит встроенный сортировщик текстовых
файлов.

В винде.

Код: java
1.
2.
3.
4.
> sort /?
SORT [/R] [/+n] [/M kilobytes] [/L locale] [/REC recordbytes]
  [[drive1:][path1]filename1] [/T [drive2:][path2]]
  [/O [drive3:][path3]filename3]



В Linux формат команд будет другой но суть - та же.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38940516
kirill_a
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonkirill_a, сильно удивишся но любая операционка содержит встроенный сортировщик текстовых
файлов.

В винде.

Код: java
1.
2.
3.
4.
> sort /?
SORT [/R] [/+n] [/M kilobytes] [/L locale] [/REC recordbytes]
  [[drive1:][path1]filename1] [/T [drive2:][path2]]
  [/O [drive3:][path3]filename3]



В Linux формат команд будет другой но суть - та же.
Я это знаю, но время работы встроенного сортировщика не устраивает, он раз в 5 медленнее (в винде померял).
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38940622
yugl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вроде же указали уже, что сортированные файлы просто сравниваются в один проход построчным сравнением на больше-меньше. Какой в таком случае смысл терять сортировку, перекладывая данные в БД или HashMap?
Если бы сортировки не было, то хэш-таблица - видимо, самый быстрый способ решения.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38940747
kirill_a
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
yuglВроде же указали уже, что сортированные файлы просто сравниваются в один проход построчным сравнением на больше-меньше. Какой в таком случае смысл терять сортировку, перекладывая данные в БД или HashMap?
Если бы сортировки не было, то хэш-таблица - видимо, самый быстрый способ решения.
Не видел сравнения в один проход.
Пример:
file1.txt :
строка1
строка2
строка3
...
file2.txt
строка1
строка1.1
строка1.2
...добавилось сотпитсотмиллионов строк
строка1.1000000000000000
строка3

как итог - OutOfMemory
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38941658
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kirill_aНе видел сравнения в один проход.
17533307
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #38942098
kirill_a
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dimitry Sibiryakovkirill_aНе видел сравнения в один проход.
17533307
Да, что-то я протупил.
Спасибо большое! То, что нужно.
...
Рейтинг: 0 / 0
Период между сообщениями больше года.
Сравнение двух больших отсортированных файлов
    #39292460
Kenny Fartman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonkirill_a, сильно удивишся но любая операционка содержит встроенный сортировщик текстовых
файлов.

В винде.

Код: java
1.
2.
3.
4.
> sort /?
SORT [/R] [/+n] [/M kilobytes] [/L locale] [/REC recordbytes]
  [[drive1:][path1]filename1] [/T [drive2:][path2]]
  [/O [drive3:][path3]filename3]



В Linux формат команд будет другой но суть - та же.Встроенные сортировщики сосут у Java
Доказано в обсуждении сортировки гигабайтной таблицы паспортов
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39292532
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kenny Fartman,

ты имеешь в виду это сообщение?
На самом деле все эти утили безбожно устарели. Например sort. Казалось бы - написано бородатым прогером 30 лет назад, на ansi C. Значит всяко быстрее всех!
А на практике, скармливаешь ему гигабайтный файл (недействительные паспорта РФ, 100млн строк) и оно умирает на час с потреблением ОЗУ 8ГБ.

В то время как прога на java делает то же самое за 40 секунд и потреблением 4ГБ.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39292787
Kenny Fartman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonKenny Fartman,

ты имеешь в виду это сообщение?ага
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39292846
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот тезис

Код: sql
1.
В то время как прога на java делает то же самое за 40 секунд и потреблением 4ГБ.



Я считаю что здесь скрытые манипуляции темой.
Что за прога? Как она написана? Какие ограничения на исходные данные?
(Напоминаю в скобках что Java ограничивает строку длиной в 2Г.)

Означает ли это что прогу можно использовать и на 16 Гб и на 32 Гб ных файлах?
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39292866
Фотография Где-то в степи
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
как то баловался на работе со студией.
на дотнете делал анализ текстового файла ( количество слов, количество вхождений, сколько раз встречается, самое длинное слов
( без лекси. анализа) накидал войнов и миров до двух гигов, разбил на части ( самое оптимальное получилось 5 или шесть потоков) зf один проход as -sax
не помню... секунд вроде 20цать заняло.... забавы ради.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39292908
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Где-то в степи, чел. Это очень любопытный факт но я не вижу связи с обсуждаемой проблемой.
А именно - с сортировкой.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39292940
iPOJO
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Сделать элементарно за один проход по файлам без всяких хешей. Смотрите алгоритмы операций над сортированными множествами.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39293078
lleming
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
iPOJOСделать элементарно за один проход по файлам без всяких хешей. Смотрите алгоритмы операций над сортированными множествами.

если это элементарно то КО подсказывает что ненужно никуда смотреть а воспользоваться обыкновенной юникс утилитой sort и все будет хорошо.

а если хорошо не будет то вряд просмотры алгоритмов помогут.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39293106
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
llemingесли это элементарно то КО подсказывает что ненужно никуда смотреть а воспользоваться обыкновенной юникс утилитой sort и все будет хорошо.
Для начала следует хотя бы посмотреть на вопрос топика. Утилита sort слаба в плане сравнения файлов. :)
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39293139
lleming
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сергей Арсеньевllemingесли это элементарно то КО подсказывает что ненужно никуда смотреть а воспользоваться обыкновенной юникс утилитой sort и все будет хорошо.
Для начала следует хотя бы посмотреть на вопрос топика. Утилита sort слаба в плане сравнения файлов. :)

Kenny Fartman Встроенные сортировщики сосут у Java
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39293142
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
lleming,

iPOJO
это не
Kenny Fartman

И он отвечал, поди, на первый вопрос первой страницы. Про то, что sort сливает java он еще и не вкурил. :)
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39293248
Kenny Fartman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
там даже дают ссылку на исходный файл на котором они сравнивают утилиту GNU с java

и там 2 подзадачи обсуждают, тупо сортировку и выделение diff-а с изменениями за последнюю неделю
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39293450
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну ОК. Я на самом деле вовсе не против сабжа. Я просто акцентирую внимание на том
что задача полна ограничений. И не стоит бросаться громкими прокламациями на тему
того что грузовик лучше гоночного болида. Можно влететь в исключительные случаи
которые отменят результат.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39293473
Kenny Fartman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonНу ОК. Я на самом деле вовсе не против сабжа. Я просто акцентирую внимание на том
что задача полна ограничений. И не стоит бросаться громкими прокламациями на тему
того что грузовик лучше гоночного болидаmaytonkirill_a, сильно удивишся но любая операционка содержит встроенный сортировщик текстовых
файлов.

В винде

В Linux формат команд будет другой но суть - та же.А я к тому что гигабайтные файлы сортировать-вычитать встроенными в ОС утилитами на сегодняшний день кажется нет смысла. Эти утилиты тоже были рассчитаны на компы с 32-256Мб оперативки и файлы 5-10. При увеличившемся на 2 порядка объемах RAM и на 2 порядка размерах исходных файлов уже стоит пользоваться самописками
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39293492
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kenny FartmanВ Linux формат команд будет другой но суть - та же.А я к тому что гигабайтные файлы сортировать-вычитать встроенными в ОС утилитами на сегодняшний день кажется нет смысла. Эти утилиты тоже были рассчитаны на компы с 32-256Мб оперативки и файлы 5-10. При увеличившемся на 2 порядка объемах RAM и на 2 порядка размерах исходных файлов уже стоит пользоваться самописками[/quot]
Надо посмотреть issues tracker по поводу sort. Я думаю что такие реквесты давно
существовали. Просто их никто не хотел делать за ненадобностью.

Но ситуация осложняется тем что существует как минимум несколько штук КАНОНИЧНЫХ
Unix-ов и каждый из них ведет свою политику целесообразности improovemens. Кому-то
такое улучшение покажется полезным. А кто-то отклонит. И по своему будет прав.
Сортировка толстых текстовиков - нетипичная задача и ее надо решать через БД.

Ну а я-бы предложил сортировку Хоара + merge в /tmp. В две фазы. Так я лет 10
назад сортировал XML-файлы на Win2003 с ограниченным набором memory.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39294282
Mad_Head
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
YamahaR1Код:
Код: 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), возможно в этом проблема...
А вы сколько записей инсертили?

Разве JVM может упасть по heap из за мусора? По идее должен тормозить GC, но не падать

Думаю, что файлы делить не обязательно, просто результат надо на диск сбрасывать периодически
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39294325
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Mad_HeadРазве JVM может упасть по heap из за мусора? По идее должен тормозить GC, но не падать
Ну если предположить, что если на хранение ста миллионов строк по 80 байт нужно около 8G, а на все про все отводилось только 6 (это мы еще всякие обертки от Map не считали) то вопрос не только в мусоре. :)
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39294381
lleming
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kenny FartmanА я к тому что гигабайтные файлы сортировать-вычитать встроенными в ОС утилитами на сегодняшний день кажется нет смысла. Эти утилиты тоже были рассчитаны на компы с 32-256Мб оперативки и файлы 5-10. При увеличившемся на 2 порядка объемах RAM и на 2 порядка размерах исходных файлов уже стоит пользоваться самописками

32-256Мб тут уже разброс практически на порядок. Получается что утилита под 32Мб не будет так же эффективна как на рядом стоящей машине с 256Мb. Не пересобирать же sort для каждой новой машины. Добавил памяти пересобирай все.

Тут само собой напрашивается вычислить доступную память и воспользоваться ей.
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39294384
lleming
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonНу а я-бы предложил сортировку Хоара + merge в /tmp. В две фазы. Так я лет 10
назад сортировал XML-файлы на Win2003 с ограниченным набором memory.

Практически попал только алгоритм External R-Way merge
http://vkundeti.blogspot.ru/2008/03/tech-algorithmic-details-of-unix-sort.html
...
Рейтинг: 0 / 0
Сравнение двух больших отсортированных файлов
    #39294391
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
llemingТут само собой напрашивается вычислить доступную память и воспользоваться ей.
Да вопрос же не в этом.
Алгоритм который предполагает, что все влезет в память будет быстрее аналогичного, но считающего, что все данные в память не влезут.
Тот в свою очередь будет быстрее, чем аналогичный, но рассчитанный на то, что и две строки в памяти могут не поместиться.
А еще медленнее будет тот, который предполагает, что и ссылки то на все строки исходного файла могут не поместиться в память.
И наконец здравствуй пузырек, который сможет отсортировать строки даже если у нас на диске нет свободного места под хотя бы еще одну строку.
...
Рейтинг: 0 / 0
51 сообщений из 51, показаны все 3 страниц
Форумы / Java [игнор отключен] [закрыт для гостей] / Сравнение двух больших отсортированных файлов
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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