|
|
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#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 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
kirill_a, сильно удивишся но любая операционка содержит встроенный сортировщик текстовых файлов. В винде. Код: java 1. 2. 3. 4. В Linux формат команд будет другой но суть - та же. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.04.2015, 11:17 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
maytonkirill_a, сильно удивишся но любая операционка содержит встроенный сортировщик текстовых файлов. В винде. Код: java 1. 2. 3. 4. В Linux формат команд будет другой но суть - та же. Я это знаю, но время работы встроенного сортировщика не устраивает, он раз в 5 медленнее (в винде померял). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.04.2015, 12:54 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Вроде же указали уже, что сортированные файлы просто сравниваются в один проход построчным сравнением на больше-меньше. Какой в таком случае смысл терять сортировку, перекладывая данные в БД или HashMap? Если бы сортировки не было, то хэш-таблица - видимо, самый быстрый способ решения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.04.2015, 14:17 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
yuglВроде же указали уже, что сортированные файлы просто сравниваются в один проход построчным сравнением на больше-меньше. Какой в таком случае смысл терять сортировку, перекладывая данные в БД или HashMap? Если бы сортировки не было, то хэш-таблица - видимо, самый быстрый способ решения. Не видел сравнения в один проход. Пример: file1.txt : строка1 строка2 строка3 ... file2.txt строка1 строка1.1 строка1.2 ...добавилось сотпитсотмиллионов строк строка1.1000000000000000 строка3 как итог - OutOfMemory ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.04.2015, 15:48 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
kirill_aНе видел сравнения в один проход. 17533307 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.04.2015, 15:10 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Dimitry Sibiryakovkirill_aНе видел сравнения в один проход. 17533307 Да, что-то я протупил. Спасибо большое! То, что нужно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.04.2015, 07:24 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
maytonkirill_a, сильно удивишся но любая операционка содержит встроенный сортировщик текстовых файлов. В винде. Код: java 1. 2. 3. 4. В Linux формат команд будет другой но суть - та же.Встроенные сортировщики сосут у Java Доказано в обсуждении сортировки гигабайтной таблицы паспортов ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.08.2016, 11:45 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Kenny Fartman, ты имеешь в виду это сообщение? На самом деле все эти утили безбожно устарели. Например sort. Казалось бы - написано бородатым прогером 30 лет назад, на ansi C. Значит всяко быстрее всех! А на практике, скармливаешь ему гигабайтный файл (недействительные паспорта РФ, 100млн строк) и оно умирает на час с потреблением ОЗУ 8ГБ. В то время как прога на java делает то же самое за 40 секунд и потреблением 4ГБ. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.08.2016, 12:55 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
maytonKenny Fartman, ты имеешь в виду это сообщение?ага ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.08.2016, 17:48 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Вот тезис Код: sql 1. Я считаю что здесь скрытые манипуляции темой. Что за прога? Как она написана? Какие ограничения на исходные данные? (Напоминаю в скобках что Java ограничивает строку длиной в 2Г.) Означает ли это что прогу можно использовать и на 16 Гб и на 32 Гб ных файлах? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.08.2016, 19:30 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
mayton, как то баловался на работе со студией. на дотнете делал анализ текстового файла ( количество слов, количество вхождений, сколько раз встречается, самое длинное слов ( без лекси. анализа) накидал войнов и миров до двух гигов, разбил на части ( самое оптимальное получилось 5 или шесть потоков) зf один проход as -sax не помню... секунд вроде 20цать заняло.... забавы ради. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.08.2016, 20:20 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Где-то в степи, чел. Это очень любопытный факт но я не вижу связи с обсуждаемой проблемой. А именно - с сортировкой. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.08.2016, 22:32 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Сделать элементарно за один проход по файлам без всяких хешей. Смотрите алгоритмы операций над сортированными множествами. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.08.2016, 02:51 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
iPOJOСделать элементарно за один проход по файлам без всяких хешей. Смотрите алгоритмы операций над сортированными множествами. если это элементарно то КО подсказывает что ненужно никуда смотреть а воспользоваться обыкновенной юникс утилитой sort и все будет хорошо. а если хорошо не будет то вряд просмотры алгоритмов помогут. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.08.2016, 10:39 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
llemingесли это элементарно то КО подсказывает что ненужно никуда смотреть а воспользоваться обыкновенной юникс утилитой sort и все будет хорошо. Для начала следует хотя бы посмотреть на вопрос топика. Утилита sort слаба в плане сравнения файлов. :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.08.2016, 11:11 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Сергей Арсеньевllemingесли это элементарно то КО подсказывает что ненужно никуда смотреть а воспользоваться обыкновенной юникс утилитой sort и все будет хорошо. Для начала следует хотя бы посмотреть на вопрос топика. Утилита sort слаба в плане сравнения файлов. :) Kenny Fartman Встроенные сортировщики сосут у Java ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.08.2016, 11:42 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
lleming, iPOJO это не Kenny Fartman И он отвечал, поди, на первый вопрос первой страницы. Про то, что sort сливает java он еще и не вкурил. :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.08.2016, 11:44 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
там даже дают ссылку на исходный файл на котором они сравнивают утилиту GNU с java и там 2 подзадачи обсуждают, тупо сортировку и выделение diff-а с изменениями за последнюю неделю ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.08.2016, 13:12 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Ну ОК. Я на самом деле вовсе не против сабжа. Я просто акцентирую внимание на том что задача полна ограничений. И не стоит бросаться громкими прокламациями на тему того что грузовик лучше гоночного болида. Можно влететь в исключительные случаи которые отменят результат. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.08.2016, 17:17 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
maytonНу ОК. Я на самом деле вовсе не против сабжа. Я просто акцентирую внимание на том что задача полна ограничений. И не стоит бросаться громкими прокламациями на тему того что грузовик лучше гоночного болидаmaytonkirill_a, сильно удивишся но любая операционка содержит встроенный сортировщик текстовых файлов. В винде В Linux формат команд будет другой но суть - та же.А я к тому что гигабайтные файлы сортировать-вычитать встроенными в ОС утилитами на сегодняшний день кажется нет смысла. Эти утилиты тоже были рассчитаны на компы с 32-256Мб оперативки и файлы 5-10. При увеличившемся на 2 порядка объемах RAM и на 2 порядка размерах исходных файлов уже стоит пользоваться самописками ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.08.2016, 17:38 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Kenny FartmanВ Linux формат команд будет другой но суть - та же.А я к тому что гигабайтные файлы сортировать-вычитать встроенными в ОС утилитами на сегодняшний день кажется нет смысла. Эти утилиты тоже были рассчитаны на компы с 32-256Мб оперативки и файлы 5-10. При увеличившемся на 2 порядка объемах RAM и на 2 порядка размерах исходных файлов уже стоит пользоваться самописками[/quot] Надо посмотреть issues tracker по поводу sort. Я думаю что такие реквесты давно существовали. Просто их никто не хотел делать за ненадобностью. Но ситуация осложняется тем что существует как минимум несколько штук КАНОНИЧНЫХ Unix-ов и каждый из них ведет свою политику целесообразности improovemens. Кому-то такое улучшение покажется полезным. А кто-то отклонит. И по своему будет прав. Сортировка толстых текстовиков - нетипичная задача и ее надо решать через БД. Ну а я-бы предложил сортировку Хоара + merge в /tmp. В две фазы. Так я лет 10 назад сортировал XML-файлы на Win2003 с ограниченным набором memory. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.08.2016, 18:06 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
YamahaR1Код: Код: java 1. 2. 3. 4. 5. Конечно у меня вроде как получается 200 млн объектов строк создается из-за ("String" + i), возможно в этом проблема... А вы сколько записей инсертили? Разве JVM может упасть по heap из за мусора? По идее должен тормозить GC, но не падать Думаю, что файлы делить не обязательно, просто результат надо на диск сбрасывать периодически ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.08.2016, 23:32 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Mad_HeadРазве JVM может упасть по heap из за мусора? По идее должен тормозить GC, но не падать Ну если предположить, что если на хранение ста миллионов строк по 80 байт нужно около 8G, а на все про все отводилось только 6 (это мы еще всякие обертки от Map не считали) то вопрос не только в мусоре. :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.08.2016, 08:20 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
Kenny FartmanА я к тому что гигабайтные файлы сортировать-вычитать встроенными в ОС утилитами на сегодняшний день кажется нет смысла. Эти утилиты тоже были рассчитаны на компы с 32-256Мб оперативки и файлы 5-10. При увеличившемся на 2 порядка объемах RAM и на 2 порядка размерах исходных файлов уже стоит пользоваться самописками 32-256Мб тут уже разброс практически на порядок. Получается что утилита под 32Мб не будет так же эффективна как на рядом стоящей машине с 256Мb. Не пересобирать же sort для каждой новой машины. Добавил памяти пересобирай все. Тут само собой напрашивается вычислить доступную память и воспользоваться ей. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.08.2016, 10:10 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
maytonНу а я-бы предложил сортировку Хоара + merge в /tmp. В две фазы. Так я лет 10 назад сортировал XML-файлы на Win2003 с ограниченным набором memory. Практически попал только алгоритм External R-Way merge http://vkundeti.blogspot.ru/2008/03/tech-algorithmic-details-of-unix-sort.html ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.08.2016, 10:11 |
|
||
|
Сравнение двух больших отсортированных файлов
|
|||
|---|---|---|---|
|
#18+
llemingТут само собой напрашивается вычислить доступную память и воспользоваться ей. Да вопрос же не в этом. Алгоритм который предполагает, что все влезет в память будет быстрее аналогичного, но считающего, что все данные в память не влезут. Тот в свою очередь будет быстрее, чем аналогичный, но рассчитанный на то, что и две строки в памяти могут не поместиться. А еще медленнее будет тот, который предполагает, что и ссылки то на все строки исходного файла могут не поместиться в память. И наконец здравствуй пузырек, который сможет отсортировать строки даже если у нас на диске нет свободного места под хотя бы еще одну строку. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.08.2016, 10:21 |
|
||
|
|

start [/forum/topic.php?all=1&fid=59&tid=2123804]: |
0ms |
get settings: |
11ms |
get forum list: |
18ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
88ms |
get topic data: |
10ms |
get forum data: |
3ms |
get page messages: |
52ms |
get tp. blocked users: |
2ms |
| others: | 239ms |
| total: | 431ms |

| 0 / 0 |
