ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Java [игнор отключен] [закрыт для гостей] / Сравнение двух больших отсортированных файлов
25 сообщений из 51, страница 2 из 3
  2  все
Сравнение двух больших отсортированных файлов
    #38940423
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
20.04.2015, 11:17
| Ответить | Цитировать | Написать  
Сравнение двух больших отсортированных файлов
    #38940516
kirill_a
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
20.04.2015, 12:54
| Ответить | Цитировать | Написать  
Сравнение двух больших отсортированных файлов
    #38940622
yugl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
yugl
Участник
Вроде же указали уже, что сортированные файлы просто сравниваются в один проход построчным сравнением на больше-меньше. Какой в таком случае смысл терять сортировку, перекладывая данные в БД или HashMap?
Если бы сортировки не было, то хэш-таблица - видимо, самый быстрый способ решения.
...
Рейтинг: 0 / 0
20.04.2015, 14:17
| Ответить | Цитировать | Написать  
Сравнение двух больших отсортированных файлов
    #38940747
kirill_a
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kirill_a
Гость
yuglВроде же указали уже, что сортированные файлы просто сравниваются в один проход построчным сравнением на больше-меньше. Какой в таком случае смысл терять сортировку, перекладывая данные в БД или HashMap?
Если бы сортировки не было, то хэш-таблица - видимо, самый быстрый способ решения.
Не видел сравнения в один проход.
Пример:
file1.txt :
строка1
строка2
строка3
...
file2.txt
строка1
строка1.1
строка1.2
...добавилось сотпитсотмиллионов строк
строка1.1000000000000000
строка3

как итог - OutOfMemory
...
Рейтинг: 0 / 0
20.04.2015, 15:48
| Ответить | Цитировать | Написать  
Сравнение двух больших отсортированных файлов
    #38941658
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
kirill_aНе видел сравнения в один проход.
17533307
...
Рейтинг: 0 / 0
21.04.2015, 15:10
| Ответить | Цитировать | Написать  
Сравнение двух больших отсортированных файлов
    #38942098
kirill_a
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kirill_a
Гость
Dimitry Sibiryakovkirill_aНе видел сравнения в один проход.
17533307
Да, что-то я протупил.
Спасибо большое! То, что нужно.
...
Рейтинг: 0 / 0
22.04.2015, 07:24
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
Сравнение двух больших отсортированных файлов
    #39292460
Kenny Fartman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
16.08.2016, 11:45
| Ответить | Цитировать | Написать  
Сравнение двух больших отсортированных файлов
    #39292532
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Kenny Fartman,

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

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

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

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



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

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

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

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

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

iPOJO
это не
Kenny Fartman

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

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

В винде

В Linux формат команд будет другой но суть - та же.А я к тому что гигабайтные файлы сортировать-вычитать встроенными в ОС утилитами на сегодняшний день кажется нет смысла. Эти утилиты тоже были рассчитаны на компы с 32-256Мб оперативки и файлы 5-10. При увеличившемся на 2 порядка объемах RAM и на 2 порядка размерах исходных файлов уже стоит пользоваться самописками
...
Рейтинг: 0 / 0
17.08.2016, 17:38
| Ответить | Цитировать | Написать  
Сравнение двух больших отсортированных файлов
    #39293492
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
17.08.2016, 18:06
| Ответить | Цитировать | Написать  
Сравнение двух больших отсортированных файлов
    #39294282
Mad_Head
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
18.08.2016, 23:32
| Ответить | Цитировать | Написать  
Сравнение двух больших отсортированных файлов
    #39294325
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
Mad_HeadРазве JVM может упасть по heap из за мусора? По идее должен тормозить GC, но не падать
Ну если предположить, что если на хранение ста миллионов строк по 80 байт нужно около 8G, а на все про все отводилось только 6 (это мы еще всякие обертки от Map не считали) то вопрос не только в мусоре. :)
...
Рейтинг: 0 / 0
19.08.2016, 08:20
| Ответить | Цитировать | Написать  
Сравнение двух больших отсортированных файлов
    #39294381
lleming
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
lleming
Участник
Kenny FartmanА я к тому что гигабайтные файлы сортировать-вычитать встроенными в ОС утилитами на сегодняшний день кажется нет смысла. Эти утилиты тоже были рассчитаны на компы с 32-256Мб оперативки и файлы 5-10. При увеличившемся на 2 порядка объемах RAM и на 2 порядка размерах исходных файлов уже стоит пользоваться самописками

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

Тут само собой напрашивается вычислить доступную память и воспользоваться ей.
...
Рейтинг: 0 / 0
19.08.2016, 10:10
| Ответить | Цитировать | Написать  
Сравнение двух больших отсортированных файлов
    #39294384
lleming
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
19.08.2016, 10:11
| Ответить | Цитировать | Написать  
25 сообщений из 51, страница 2 из 3
  2  все
Форумы / Java [игнор отключен] [закрыт для гостей] / Сравнение двух больших отсортированных файлов
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=59&msg=39292460&tid=2123804]:
 0ms
get settings:
 9ms
get forum list:
 13ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 57ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 80ms
get tp. blocked users:
 1ms
others: 226ms
total:  406ms
созд. / загр.: 406ms
x
x
Закрыть


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