Напишите построчную сортировку большого текстового файла не влезающего в оперативную память
В прошлый раз мы обсудили, как можно искусственно ограничить доступную программе память. В качестве бонуса я заполучил себе libmemrestrict – библиотеку с обёртками функций вроде malloc для отслеживания использования памяти, и ptrace-restrict — инструмент на базе ptrace, перехватывающий вызовы brk, sbrk и mmap с той же целью.
Так зачем нам пытаться организовывать ограничение памяти – так ли это часто встречается? Когда в последний раз ООМ прибил ваше приложение? Вы всегда думаете о потреблении памяти во время программирования? Память – штука дешёвая, и если вам не хватает памяти, добавьте ещё пару гигабайт.
И, тем не менее, невозможно бесконечно добавлять память – и не из-за того, что у вас нет бесконечного её источника. При обработке Больших данных просто невозможно вместить весь ввод в массив – необходимо распределять данные между оперативкой, носителями и сетью. Необходимы алгоритмы и техники для такой обработки данных.
И вот я занялся подобными задачами, начав с простой – как отсортировать миллион целых чисел (4 MiB данных) при наличии 2 MiB памяти? Эту задачу можно обобщить на тот случай, когда у вас недостаточно памяти, чтобы вместить все данные.
Необходимо написать программу сортировки набора целых чисел, хранящихся в файле. Для его создания я написал простейшие утилиты randints и rangeints
Программа должна выдавать отсортированный массив на stdout в виде текста
Она должна измерить время работы и вывести его на stderr. Нельзя просто запустить программу через утилиту time, потому что она посчитает время на чтение файла и время на его вывод.
Она должна работать, имея памяти как минимум в два раза меньше объёма файла. Для этого мы применим libmemrestrict или ptrace-restrict.
Для некоторых методов эти утилиты не пригодятся. Например, для mmap они не сработают – придётся физически ограничить использование памяти.
Они будут проверяться для решения оригинальной задачи (сортировки 4 MiB в 2 MiB). Также я запущу их на виртуалке со 128 MiB памяти для сортировки 500 Mb (125 миллионов четырёхбайтных целых).
Наивный подход
Попробуем отсортировать числа напрямую и подсчитаем использование памяти (и время). Просто считаем файл в массив целых, и вызовем qsort.
Попробуем файл с 4 Мб данных. Без ограничений всё работает:
но это неинтересно. Ограничим память 2 MiB:
Поднимем ограничение до 4 MiB – и вновь неудача. (libmemrestrict читает настройки из окружения).
Очевидно, для qsort требуется больше памяти. Посмотрим, сколько он хочет, при помощи massif от valgrind:
Вот вам красивый график:
Видно несколько размещений данных, удваивающих запросы в памяти до 4 MiB – это мой массив, и затем ещё четыре MiB для qsort. Статистика:
4 миллиона байт использую я, и ещё 4 миллиона — qsort_r. И ещё 1,2 MB дополнительно в куче использует massif.
Судя по всему, в этом случае qsort ведёт себя как O(n) по отношению к сложности по объёму. Что странно, поскольку qsort работает «на месте» и использует различные техники оптимизации, гарантирующие сложность по объёму в O(log n). Дополнительное чтение по реализации glibc qsort.
Ладно – а сможет ли он отсортировать 500 MB в 128 MiB RAM?
Конечно, нет. Быстродействие:
Значит, наивная сортировка неплохо работает без ограничений, вообще не работает с ограничениями, а qsort требует себе памяти O(n). Это странно. К примеру, если ограничить память 5,3 Мб, она заработает и не затребует памяти объёмом O(n). Я пока ещё разбираюсь с этим.
Файл и mmap
mmap – хакерский способ сортировки большого количества данных в условиях ограничения памяти. Он перекладывает груз распределения данных между памятью и свопом на плечи операционки.
- Через mmap мы отправляем весь файл в память
- Получаем от него указатель на данные
- Вызываем алгоритм сортировки данных по этому указателю
И всё! Теперь вы не получите переполнение памяти, даже сортируя файл по объёму больший, чем доступная память. Для понимания работы механизма нужно немного разобраться с управлением памятью в ОС.
Каждая программа представлена процессом, у которого есть своё личное, изолированное от других, виртуальное адресное пространство. Длина его ограничена шириной шины CPU, то есть для 32-битного CPU она равна 2 32 , то есть 4 GiB.
Всё размещение памяти, которым занимается процесс, происходит в виртуальной памяти. Эта виртуальная память отображается на физическую подсистемой ядра для работы с памятью — MMU. И обычно происходит в «ленивом» режиме – то есть, когда процесс просит памяти, ядро ему сразу её даёт, но при этом физически не размещает её мгновенно – то есть, страница виртуальной памяти не отображается сразу на физическую. Когда к такой странице происходит доступ (например, на запись), MMU создает исключение «page fault», которое ядро обрабатывает, отображая виртуальную страницу на физическую. Теперь она отображена, и запись в эту страницу будет транслироваться MMU как запись по определённому адресу в физической памяти.
С другой стороны, если помнить, что виртуальное адресное пространство ограничено лишь размером шины CPU, можно попасть в ситуацию, в которой программа захочет занять больше памяти, чем есть в наличии. К примеру, в 32-битной системе, имеющей 256 MiB RAM, процесс может разместить и использовать 1 GiB памяти. В таком случае страницы памяти попадут в своп – они вместо RAM попадут на накопитель, такой, как жёсткий диск. При доступе к такой странице ядро считает её с накопителя и отправит в память (заменяя другую страницу в памяти).
Ядро неплохо справляется с распределением данных между памятью и накопителем, поэтому естественно попытаться использовать это его свойство в нашей задаче. Когда мы вызовем mmap для нашего файла, ядро зарезервирует диапазон виртуальных адресов, который не будет сразу размещён. Когда мы попытаемся получить доступ к ним, ядро подгрузит его из входного файла в память. Когда у нас закончится физическая память, ядро уберёт страницы в своп. Таким образом мы будем балансировать данными между файлом на диске, памятью и свопом.
Ограничением является только виртуальное адресное пространство (4 GiB для 32bit системы и 256 TiB для 64bit), и своп – но накопители сегодня стоят недорого.
В связи с тем, что mmap грузит весь файл в виртуальную память, мы не сможем использовать libmemrestrict или ptrace-restrict, поскольку они ограничивают саму виртуальную память. Попытавшись ограничить сортировку данных объёмом в 100M в виртуальную память объёмом 10M, мы получим ошибку от mmap:
Ничего удивительного – файл грузится в виртуальную память, и ядро распределяет её между физической памятью и свопом. Так что нам нужно не менее 100М виртуальной памяти, плюс ещё немного места для qemu.
Поэтому для данного метода я использую виртуальную машину с 128 MiB памяти. Вот моя программа сортировки, использующая mmap. И всё работает!
Информация от top:
Мы используем 500 Мб виртуальной памяти, а реальная доступная память при этом составляет 90 MiB. Отметим, что MiB это 2 20 , а MB это 10 6 = 1 миллион. И 500 MB = 500 000 000 байт, а 500 000 000 >> 20 = 476 MiB.
Глянув на детали от vmstat во время сортировки 500 MB, мы увидим, как ядро балансирует между свопом, дисковым кэшем, буферами и свободной памятью:
Сначала у нас было ~70 MiB свободной памяти, пустой своп и немножко памяти было отдано под буферы I/O и кэш. Затем после mmap вся эта память ушла на кэш. Когда свободная память кончилась, ядро стало использовать своп, который увеличивается вместе с увеличением загрузки I/O. И мы приходим к тому, что почти вся память отдана под кэш диска – что нормально, поскольку страницы с дисковым кэшем, в случае, когда нам требуется память под приложение, уходят первыми.
Итак, сортировка через mmap – прикольный хак, требующий базовых представлений о работе с памятью, и дающий простое решение для обработки большого количества данных при маленьком количестве памяти.
Внешняя сортировка со слиянием
Допустим, mmap использовать нельзя — вы хотите отсортировать файл в 5 GiB на 32-битной системе.
Существует известный популярный способ под названием «внешняя сортировка со слиянием». Если у вас не хватает памяти, нужно использовать внешний накопитель — например, жёсткий диск. Придётся только работать с данными по кусочку, поскольку в память они все не влезут.
Отсортировали, имея 2 MiB памяти и используя буфер в 1 MiB.
Теперь отсортируем 500 Мб. Сначала отключим своп, поскольку мы управляем обменом кусков данных вручную.
Проверим доступную память:
Будем использовать буфер в 50 Мб – в 10 раз меньше размера файла.
Ничосий, две минуты! С чего бы это? Конечно, из-за операций I/O. Три вещи тормозят процесс. На фазе разделения данных мы последовательно читаем файл, используя маленький буфер. На фазе слияния мы открываем и закрываем файлы с кусками информации. А ещё есть и вывод – на фазе слияния мы выводим 50 Мб данных на stdout, что, несмотря на перенаправление в /dev/null, даёт нагрузочку. Если это отключить, мы получаем прирост быстродействия на 25%.
Использование памяти меня устраивает. Если запустить программу через massif, можно увидеть, что пик потребления – это размер буфера и небольшая куча.
Можно ограничить память и 50 Мб, плюс ещё 500 KB на временные строки, содержащие пути к файлам:
В общем, с памятью – ок, с быстродействием – не ок. mmap позволяла сделать эту операцию за 32 секунды. Давайте улучшать наш способ.
Проведём профилирование программы при помощи gprof. Создадим бинарник
И вызовем программу многократно для накопления статистики при помощи моего удобственного скрипта из статьи по gprof. Вот результат:
Большая часть времени ушла на сортировку и вывод. Но не забудьте, что gprof не показывает время, ушедшее на системные вызовы и I/O.
- добавить во внешнюю сортировку многопоточность и трюки с I/O
- взять другой алгоритм сортировки
Универсальная внешняя сортировка со слиянием – это простая идея для сортировки больших данных при малом количестве памяти, но без каких-либо улучшений она работает медленно.
Настраиваем сортировку
- readahead (только в Linux).
- posix_fadvise с POSIX_FADV_SEQUENTIAL.
Они сообщают подсистеме управления памятью о том, как мы будем читать данные. В нашем случае чтение последовательно, поэтому было бы неплохо увидеть содержимое файла в кэше страниц.
На фазе слияния мы можем не делать постоянные открытия и закрытия файлов, а создать выделенные потоки для каждого из файлов. Каждый поток будет держать открытым свой файлик, а мы будем заполнять для него буфер. Когда он заполняется, он сортируется и выводится. И ещё для каждого потока будет работать readahead.
Вот усовершенствованная многопоточная версия внешней сортировки со слиянием. Ну, как я и сказал, многопоточность – не очень хорошая идея. На одноядерном проце разницы никакой нет.
Это с выводом данных. А без вывода:
Ну ладно, давайте попробуем на четырёхъядерной машине (Intel Core i7-3612QM CPU @ 2.10GHz):
- исполнение потоков независимо
- ресурсы ввода и вывода могут работать параллельно – например, как RAID
У нас потоки взаимозависимы – главному потоку приходится ждать сортировки буфера, а уже потом начинать следующее чтение из файла. И чтение для разделения идёт быстрее, чем сортировка буфера, поэтому большую часть времени потоки ждут, пока основной поток закончит работу.
Нужны другие способы улучшения алгоритма.
Особые алгоритмы сортировки
- не используют сравнения
- не требуют загрузки всего массива в память
Они работают лучше, чем O(n log(n)) – нижняя граница для сравнивающих алгоритмов вроде QuickSort. Но не все они подойдут в случае ограничения памяти. Поэтому я остановился на использовании сортировки подсчётом
Сортировка подсчётом
Если у нас много данных с малым разбросом, можно использовать сортировку подсчётом. Идея проста – мы будем хранить в памяти не данные, а массив счётчиков. Мы последовательно читаем данные и увеличиваем соответствующие счётчики. Сложность алгоритма по времени линейна, а по объёму – пропорциональна диапазону данных.
Простая реализация работает с массивом от 0 до N. Целые числа соответствуют индексам массива. Вот мой вариант, который неплохо работает и без всякого тюнинга. Второй аргумент – размер буфера в элементах. Буферизация сильно ускоряет работу, поскольку программа читает из файла не по 4 байта.
Угумс. Полгига данных отсортировано за 3 с половиной секунды на 128 MiB памяти и одном CPU. Сравним с qsort или mmap:
В 23 раза быстрее!
Но не забывайте об ограничениях – только целые числа (или их эквивалент), и небольшой их последовательный промежуток. Я пытался делать вариант с непоследовательными промежутками через хэши и бинарный поиск – но быстродействие у него очень плохое.
А если мы предположим уникальность наших чисел, то счётчики могут быть только в двух состояниях – есть или нет, поэтому они могут быть однобитными. Тогда наш массив ужмётся. Да и массив нам не нужен – мы можем хранить числа в виде битов, то есть вместо массива у нас будет вектор. Читаем файл и устанавливаем N-ный бит, если там встретилось число N. После этого просто проходимся по вектору и выводим в файл те числа, для которых взведены биты.
Такие решения требуют внимательного подхода, поскольку всё равно можно выйти за пределы ограничений. К примеру, для сортировки всех чисел из промежутка целых (2 32 ), вам понадобится 1 бит на каждое число, а это 4294967296 бит = 536870912 байт = 512 MiB. А у нас есть только 128 MiB, чего вам не хватит. Но в некоторых случаях выигрыш будет колоссальным – вот история на эту тему из «Programming Pearls» by Jon Bentley.
Знание ваших данных очень полезно.
у меня есть несколько файлов, которые должны быть отсортированы по идентификатору в начале каждой строки. Файлы составляют около 2-3 Гб.
Я попытался прочитать все данные в ArrayList и сортировать их. Но памяти недостаточно, чтобы сохранить их все. Это не работает.
строки выглядят как
0052304 0000004000000000000000000000000000000041 John Teddy 000023
0022024 0000004000000000000000000000000000000041 George Clan 00013
как я могу сортировать файлы??
Это не совсем проблема Java. Вам нужно изучить эффективный алгоритм сортировки данных, который не полностью считывается в память. Несколько адаптаций к слиянию-сортировке могут достичь этого.
в основном идея здесь состоит в том, чтобы разбить файл на более мелкие части, отсортировать их (либо с помощью сортировки слияния, либо другой метод), а затем используйте слияние из merge-sort для создания нового отсортированного файла.
для этого вам нужна внешняя сортировка слияния. здесь - это реализация Java, которая сортирует очень большие файлы.
поскольку ваши записи уже находятся в текстовом формате плоского файла, вы можете передать их в UNIX sort(1) например sort -n -t' ' -k1,1 < input >output . Он автоматически разделит данные и выполнит сортировку слиянием, используя доступную память и /tmp . Если вам нужно больше места, чем у вас есть доступная память, добавьте -T /tmpdir команды.
вместо того, чтобы загружать все данные в память сразу, вы можете прочитать только ключи и индекс, где начинается строка (и, возможно, длина), например
Это будет использовать около 40 байт на строку.
после сортировки этого массива можно использовать RandomAccessFile для чтения строк в порядке их появления.
Примечание: поскольку вы будете случайно ударять по диску, вместо использования памяти это может быть очень медленно. Типичный диск принимает 8 мс для произвольного доступа к данным, и если у вас есть 10 миллионов строк, это займет около одного дня. (Это абсолютный худший случай) в памяти это займет около 10 секунд.
вы можете использовать SQL Lite file db, загрузить данные в БД, а затем позволить ему сортировать и возвращать результаты для вас.
Плюсы: Не нужно беспокоиться о написании лучшего алгоритма сортировки.
недостаток: вам понадобится дисковое пространство, более медленная обработка.
Что вам нужно сделать, это разделить файлы через поток и обработать их отдельно. Затем вы можете объединить файлы вместе, поскольку они уже будут отсортированы, это похоже на то, как работает сортировка слиянием.
ответ из этого вопроса SO будет иметь значение:большой поток файлов
операционные системы поставляются с мощной утилитой сортировки файлов. Простая функция, которая вызывает скрипт bash, должна помочь.
необходимо выполнить внешнюю сортировку. Это своего рода движущая идея Hadoop/MapReduce , просто она не учитывает распределенный кластер и работает на одном узле.
для лучшей производительности вы должны использовать Hadoop / Spark.
Измените эти строки в соответствии с вашей системой . fpath ваш один большой входной файл (протестирован с 20GB). shared путь-это место, где хранится журнал выполнения. fdir где промежуточные файлы будут сохранены и объединены. Измените эти пути в соответствии с вашей машиной.
также не забудьте изменить int totalLines = 200000000; на общую строки в вашем файле. и количество нитей ( int threadCount = 16 ) должен всегда иметь мощность 2 и достаточно большой, чтобы (общий размер * 2 / нет потока) объем данных мог находиться в памяти. Изменение количества потоков изменит имя конечного выходного файла. Как и для 16, это будет op401, для 32 это будет op501,для 8 это будет op301 и т. д.
у меня есть общий вопрос о вашем мнении о моей "технике".
есть 2 текстовых файлов ( file_1 и file_2 ), которые нужно сравнивать друг с другом. Оба очень огромные (3-4 гигабайта, от 30,000,000 до 45,000,000 строк каждый). Моя идея-прочитать несколько строк (как можно больше) из file_1 в память, затем сравните их с все строки file_2 . Если есть совпадение, строки из обоих файлов, которые совпадают, должны быть записаны в новый файл. Затем перейдите к следующей 1000 строкам file_1 а также сравните их с все строки file_2 пока я не прошел file_1 полностью.
но это звучит на самом деле очень, очень трудоемко и сложно для меня. Можете ли вы придумать какой-либо другой метод для сравнения этих двух файлов?
как вы думаете, может взять? Для моей программы Время не имеет большого значения. У меня нет опыта работы с такими огромными файлами, поэтому я понятия не имею, сколько времени это может занять. Но это не займет больше дня. ;- ) Но я боюсь, что моя техника может занять вечность.
Антуан вопрос, который только что пришел мне на ум: сколько строк вы бы прочитали в памяти? Как можно больше? Есть ли способ определить количество возможных строк, прежде чем фактически попробовать? Я хочу прочитать как можно больше (потому что я думаю, что это быстрее), но у меня часто заканчивалась память.
редактировать Думаю, я должен объяснить свою проблему немного подробнее.
цель состоит в том, чтобы не видеть, являются ли два файла в целом идентичными (они не являются). В каждом файле есть несколько строк, которые имеют одну и ту же"характеристику". Вот пример: file_1 выглядит так:
file_2 выглядит так:
TEXT относится к символам и цифрам, которые меня не интересуют, mat может идти от mat1 - mat50 и не в порядке; также может быть 1000x mat2 (но цифры в следующем столбце разные). Мне нужно найти подходящие линии таким образом, что: matX одинакова в обеих сравниваемых строках и число, указанное в file_2 вписывается в диапазон указанных в file_1 . Поэтому в моем примере я бы нашел одно совпадение: строка 3 из file_1 и в строке 1 file_2 (потому что оба mat3 и 10009 между 10000 и 10010). Я надеюсь, это прояснит для вас!
так мой вопрос: как бы вы искали соответствующие строки?
Да, я использую Java в качестве языка программирования.
редактировать Сначала я разделил огромные файлы, чтобы у меня не было проблем с нехваткой памяти. Я также думаю, что быстрее сравнивать (многие) меньшие файлы друг с другом, чем эти два огромных файла. После этого я могу сравнить их так, как я упоминал выше. Возможно, это не лучший способ, но я все еще учусь. ;-) Все Nonentheless ваш подходы были очень полезны для меня, спасибо за ваши ответы!
теперь, когда вы дали нам больше информации, подход, который я бы взял, основывается на предварительном разбиении и, возможно, сортировке перед поиском совпадений.
это должно исключить значительное количество сравнений, которые в противном случае не совпадали бы в наивном, грубом подходе. Для аргументации, позволяет привязать оба файла по 40 миллионов строк каждый.
это один проход через два файла в общей сложности 80 миллионов строк чтения, что дает два набора из 50 файлов по 800 000 строк каждый в среднем.
сортировка: для каждого раздела сортируйте только по числовому значению во втором столбце (нижняя граница от file_1 и фактическим номер от file_2 ). Даже если 800 000 строк не могут поместиться в память, я полагаю, мы можем адаптировать двустороннюю внешнюю сортировку слияния и выполнять это быстрее (меньше общих чтений), чем своего рода весь неразмеченное пространство.
для сравнения: теперь вам просто нужно повторить после через обе пары file_1_mat1 и file_2_mat1 , без необходимости хранить что-либо в памяти, вывод совпадений в выходной файл. Повторите для остальных разделов в очередь. Нет необходимости в последнем шаге "слияния" (если вы не обрабатываете разделы параллельно).
даже без этапа сортировки наивное сравнение, которое вы уже делаете, должно работать быстрее через 50 пар файлов с 800 000 строк каждый, а не с двумя файлами с 40 миллионами строк каждый.
Я думаю, ваш способ вполне разумные.
Я могу представить себе разные стратегии - например, вы можете сортировать оба файла перед сравнением (где эффективная реализация filesort, а утилита сортировки unix может сортировать несколько файлов Gbs в минутах), и при сортировке вы можете сравнивать файлы последовательно, читая строку за строкой.
но это довольно сложный способ-вам нужно запустить внешнюю программу (сортировку) или написать сопоставимую эффективную реализацию filesort в java самостоятельно - что само по себе непростая задача. Итак, для простоты, я думаю, что Вы способ chunked чтения очень многообещающий;
Что касается того, как найти разумный блок-прежде всего, может быть неправильно, что "чем больше-тем лучше" - я думаю, время всей работы будет расти асимптотически, до некоторой постоянной линии. Так что, может быть, вы будете ближе к этой линии быстрее, чем вы думаете - вам нужен ориентир для этого.
Далее -- вы можете прочитать линий буфер такой:
таким образом, Вы читаете столько строк, сколько можете-оставляя последний BLOCK_SIZE свободной памяти. BLOCK_SIZE должен быть большим enouth для остальных из вас программы для запуска без OOM
в идеальном мире вы сможете читать в каждой строке file_2 в память (возможно, используя объект быстрого поиска, такой как HashSet , в зависимости от ваших потребностей), затем прочитайте каждую строку из file_1 по одной и сравните ее со своей структурой данных, содержащей строки из file_2.
как вы сказали, у вас заканчивается память, однако, я думаю, что стратегия типа "разделяй и властвуй" была бы лучшей. Вы можете использовать тот же метод, что и я упоминал выше, но читать наполовину (или на треть, квартал. в зависимости от того, сколько памяти вы можете использовать) линий от file_2 и хранить их, а затем сравнить все строки в file_1. Затем прочтите следующую половину / третью / четверть / что угодно в память (заменив старые строки) и снова пройдите через file_1. Это означает, что вы должны пройти через file_1 больше, но вы должны работать с ограничениями памяти.
EDIT: в ответ на добавленную деталь в вашем вопросе, я бы изменил свой ответ частично. Вместо чтение во всех file_2 (или в кусках) и чтение в file_1 строки за раз, отмените это, поскольку file_1 содержит данные для проверки.
кроме того, что касается поиска совпадающих строк. Я думаю, что лучшим способом было бы сделать некоторую обработку на file_1. Создать HashMap> это сопоставляет строку ("mat1" - "mat50") со списком Range s (просто обертка для startOfRange int и endOfRange int ) и заполнить его данными из file_1. Затем напишите функцию like (ignoring проверка ошибок)
и вызовите его для каждой (проанализированной) строки file_2.
существует компромисс: если Вы читаете большой кусок файла, вы сохраняете диск искать времени, но вы, возможно, прочитали информацию, которая вам не понадобится, так как изменение было обнаружено в первых строках.
вы, вероятно, должны запустить некоторые эксперименты [бенчмарки] с различным размером куска, чтобы узнать, что является оптимальным куском для чтения в среднем случае.
действительно, это может занять некоторое время. Вы должны сделать 1,200.000,000 сравнение линии. Есть несколько возможностей, чтобы ускорить это на порядок magnitute:
одним из них было бы сортировать file2 и выполнять двоичный поиск на уровне файла. Другой подход: вычислите контрольную сумму каждой строки и найдите ее. В зависимости от средней длины строки рассматриваемый файл будет намного меньше, и вы действительно можете выполнить двоичный поиск, если вы храните контрольные суммы в фиксированном формате (т. е. долго)
количество строк, которые Вы читаете сразу из file_1 делает не материя, однако. Это микро-оптимизация перед лицом большой сложности.
Если вы хотите простой подход: вы можете хэшировать оба файла и сравнивать хэш. Но, вероятно, быстрее (особенно если файлы отличаются) использовать ваш подход. О потреблении памяти: просто убедитесь, что вы используете достаточно памяти, не используя буфер для такого рода вещь-плохая идея..
и все эти ответы о хэшах, контрольных суммах и т. д.: Они не быстрее. В обоих случаях вы должны прочитать весь файл. С хэшами / контрольными суммами вам даже нужно вычислить что-то.
что вы можете сделать, это сортировать каждый отдельный файл. например, UNIX sort или аналогичный в Java. Вы можете прочитать отсортированные файлы по одной строке за раз, чтобы выполнить сортировку слиянием.
Я никогда не работал с такими огромными файлами, но это моя идея и должна работать.
Вы можете посмотреть в хэш. Использование хэширования SHA-1.
Как только ваш текстовый файл и т. д. был загружен, он проходит через каждую строку и в конце распечатывает хэш. Приведенные ниже ссылки на примеры будут углублены.
отсюда вы можете получить разницу, рассказывая вам, какие строки отличаются. Если бы вы могли каким-то образом использовать эту разницу, чтобы определить, какие линии были одинаковыми, вы бы все набор.
Это просто идея, кто-то поправит меня, если я ошибаюсь.
Всем привет!
Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
Здравствуйте, makdak, Вы писали:
M>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки.
M>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
Дональд Кнут, том 3. Внешняя сортировка.
От: | kaa.python | РСДН профессионально мёртв и завален ватой. |
Дата: | 16.01.17 11:16 | |
Оценка: | 3 (1) |
Здравствуйте, makdak, Вы писали:
M>Всем привет!
M>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
В Яндекс собеседование проходишь? Я, когда-то давным давно, так делал эту задачку решал. Сейчас, правда смотрю на это и понимаю что сделал бы иначе. Вообще интересно на свой старый код смотреть
Здравствуйте, makdak, Вы писали:
M>Как отсортировать файл 2TB с числами, размером в 32 бита
лучше гномиков посчитайте
гораздо полезнее и писать код не надо
Здравствуйте, makdak, Вы писали:
M>Всем привет!
M>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
Даные в текстовом файле через перевод строки от 2 до 11 байт. Если есть еще 2Тб для результата или хотя бы 20Гб для промежуточных данных то
сортировка подсчетом (40бит счетчики) справится. Делишь 20Гб по 2Гб получаешь ~10 чтений по исходному файлу и одна запись результата.
Здравствуйте, kaa.python, Вы писали:
KP>В Яндекс собеседование проходишь?
почти, угадал. Бывшие работники Яндекса, как-то прислали вопросы, еще до собеседования, там вот этот вопрос и был. Для себя хочу знать.
А что, в Яндекс только сверхчеловеков берут только? вроде и студентов набирают.
Здравствуйте, uzhas, Вы писали:
U>лучше гномиков посчитайте
U>гораздо полезнее и писать код не надо
а если хочется код писать?
Здравствуйте, makdak, Вы писали:
M>А что, в Яндекс только сверхчеловеков берут только? вроде и студентов набирают.
Студентов, наверное, сперва через Академию Яндекса протаскивают.
От: | kaa.python | РСДН профессионально мёртв и завален ватой. |
Дата: | 16.01.17 14:09 | |
Оценка: |
Здравствуйте, makdak, Вы писали:
M>почти, угадал. Бывшие работники Яндекса, как-то прислали вопросы, еще до собеседования, там вот этот вопрос и был. Для себя хочу знать.
M>А что, в Яндекс только сверхчеловеков берут только? вроде и студентов набирают.
В этой задачке ничего сверхчеловеческого нет, но она требует опыта в определенной сфере или как минимум практики пусть даже в на учебных задачах в чем-то похожем. Сходу, если учесть все их требования (их больше было чем ты привел) человек без нужного опыта врядли корректно решит. Насколько им действительно нужен такой опыт вопрос отдельный, но, видимо, важен. Либо просто очень большой поток желающих достаточно высокого качества и его нужно как-то фильтровать.
Здравствуйте, kaa.python, Вы писали:
KP>Здравствуйте, makdak, Вы писали:
M>>почти, угадал. Бывшие работники Яндекса, как-то прислали вопросы, еще до собеседования, там вот этот вопрос и был. Для себя хочу знать.
M>>А что, в Яндекс только сверхчеловеков берут только? вроде и студентов набирают.
KP>(их больше было чем ты привел) человек без нужного опыта врядли корректно решит.
а остальные вопросы почти все были элементарные.
Здравствуйте, makdak, Вы писали:
M>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки.
Может, предполагается, что надо использовать что-то типа сортировки подсчётом?
Здравствуйте, makdak, Вы писали:
M>Всем привет!
M>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
Взять библиотеку STXXL и не выдрючиваться.
M>>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
Q>Может, предполагается, что надо использовать что-то типа сортировки подсчётом?
Это — само собой, ибо числа целые.
Но сортировка подсчетом работает только над отдельной порцией данных.
А потом все равно все порции — сливать.
А это внешняя сортировка (слиянием), о коих в 3 томе Кнута написано чуть ли не полкнижки.
Здравствуйте, LaptevVV, Вы писали:
M>>>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
Q>>Может, предполагается, что надо использовать что-то типа сортировки подсчётом?
LVV>Это — само собой, ибо числа целые.
больно разрядность большая. много Cache Miss будет.
Здравствуйте, kov_serg, Вы писали:
_>Даные в текстовом файле через перевод строки от 2 до 11 байт. Если есть еще 2Тб для результата или хотя бы 20Гб для промежуточных данных то
_>сортировка подсчетом (40бит счетчики) справится. Делишь 20Гб по 2Гб получаешь ~10 чтений по исходному файлу и одна запись результата.
Счётчики можно сделать более хитрыми.
Например размером в байт.
Тогда если старший бит сброшен — счётчик находится прямо в этом байте. (0-127)
Если выставлен — младшие 7 бит означают номер корзины, в которой лежит внешний счётчик большого размера (хоть 64 бита). Большие счётчики создаются динамически, при переполнении встроенного. Проход по корзине произвольный, для начала можно даже линейный.
Скорее всего уложишься в один проход, с выделением памяти чуть больше 2гб.
Можно несколько алгоритмов придумать, для разного характера распределений чисел. И обрывать проход с перевыбором алгоритма, если статистика говорит что есть более оптимальный способ.
Здравствуйте, Qbit86, Вы писали:
Q>Может, предполагается, что надо использовать что-то типа сортировки подсчётом?
Не выйдет.
Для гистограммы над двордами нам потребуется 4 гига счётчиков, причём 40-битных (2 терабайта поделить на 2..16 байт в каждой строке). То есть, 20 гектар, если выжимать биты, и 32 гектара, если не выжимать.
А в нашем распоряжении только 2 гектара, то есть, по полбайта на счётчик.
Здравствуйте, night beast, Вы писали:
NB>Здравствуйте, LaptevVV, Вы писали:
M>>>>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
Q>>>Может, предполагается, что надо использовать что-то типа сортировки подсчётом?
LVV>>Это — само собой, ибо числа целые.
NB>больно разрядность большая. много Cache Miss будет.
2 гига — это как раз для 32-битных знаковых целых подойдет.
Но есть еще поразрядная сортировка — прекрасно подойдет в данном слуучае
Здравствуйте, makdak, Вы писали:
M>А что, в Яндекс только сверхчеловеков берут только? вроде и студентов набирают.
Студенты у них должны уметь просыпаться среди ночи, и быстро поисковые запросы отрабатывать. Ну или там, такси искать, в зависимости от проекта. Тоже в своем роде сверхчеловеки.
Здравствуйте, makdak, Вы писали:
M>вот:
M>
что-то тут набросали ключевые слова и даже фамилии, а паззл лично у меня не сложился
давайте уточним задачу, а потом набросайте хоть примерную идею решения
1) есть текстовый файл размером 1TB (ну я бы сказал не более 1TB), в котором целые числа, умещающиеся в 32 бита перечислены в десятичном представлении. на каждой строке — одно число. между строками — newline (виндовый или линуксовый)
2) нужно в этом файле попереставлять строки так, чтобы числа были отсортированы (без ограничения общности, по возрастанию). то есть inplace
3) есть ограничение на рабочую память проги — 2GB. не забываем, что кроме огромного массива на 2GB могут быть еще рабочие переменные, так что огроменным массивом, который в точности занимает 2GB нам пользоваться нельзя. сколько там занимает рантайм нам побоку, считаем лишь рабочую память нашего алгоритма
не надо только отсылать к чтению томов Кнута, спасибо
Здравствуйте, uzhas, Вы писали:
U>2) нужно в этом файле попереставлять строки так, чтобы числа были отсортированы (без ограничения общности, по возрастанию). то есть inplace
react, A declarative, efficient, and flexible JavaScript library for building user interfaces.
From organization facebook
discountry / react
react, React docs in Chinese | React 中文文档翻译
From user discountry
facebook / react-native
react, A framework for building native applications using React
From organization facebook
werein / react
react, Extremely simple boilerplate, easiest you can find, for React application including all the necessary tools: Flow | React 16 | redux | babel 6 | webpack 3 | css-modules | jest | enzyme | express + optional: sass/scss
From organization werein
reactiveui / ReactiveUI
typescript-cheatsheets / react
react, Cheatsheets for experienced React developers getting started with TypeScript
From organization typescript-cheatsheets
ui-router / react
react, 🔼 UI-Router for React
From organization ui-router
Cathy0807 / react
From user Cathy0807
enaqx / awesome-react
react, A collection of awesome things regarding React ecosystem
From user enaqx
react, The React documentation website
From organization reactjs
remix-run / react-router
react, Declarative routing for React
From organization remix-run
streamich / react-use
react, React Hooks — 👍
From user streamich
omergulcicek / react
react, React JavaScript kütüphanesi Türkçe çeviri
From user omergulcicek
react-redux-antd-es6 / react
From organization react-redux-antd-es6
duxianwei520 / react
react, React+webpack+redux+ant design+axios+less全家桶后台管理框架
From user duxianwei520
react-boilerplate / react-boilerplate
From organization react-boilerplate
primer / react
react, An implementation of GitHub's Primer Design System using React
From organization primer
zf-huangxiao / react
react, demo of React.js
From user zf-huangxiao
vercel / next.js
react, The React Framework
From organization vercel
xzlaptt / React
From user xzlaptt
azat-co / react
react, Examples for the React Quickly book.
From user azat-co
facebook / create-react-app
react, Set up a modern web app by running one command.
From organization facebook
HackYourFuture / React
react, This repository contains all the material for the HackYourFuture module "React.js: Building dynamic UIs with modern JavaScript"
From organization HackYourFuture
formio / react
react, JSON powered forms for React.js
From organization formio
ReactiveCocoa / ReactiveCocoa
react, Cocoa framework and Obj-C dynamism bindings for ReactiveSwift.
From organization ReactiveCocoa
Читайте также: