Всем привет,
Дали тестовую задачу отсортировать текстовый файл построчно, размер 100ГБ и 10ГБ.
Раньше особо такие задачи никогда не решал. Стало интересно, сколько такая сортировка должна занимать времени для решения близкого к идеальному.
Здравствуйте, Nonmanual Worker, Вы писали:
NW>Всем привет, NW>Дали тестовую задачу отсортировать текстовый файл построчно, размер 100ГБ и 10ГБ. NW>Раньше особо такие задачи никогда не решал. Стало интересно, сколько такая сортировка должна занимать времени для решения близкого к идеальному.
Время зависит от параметров системы, в первую очередь диск наверное, так что как его назвать не понятно...
Главное, в память всё не грузи
Подсказки давать или сам сообразишь подходящий алгоритм сортировки?
Здравствуйте, SergH, Вы писали:
SH>Здравствуйте, Nonmanual Worker, Вы писали:
NW>>Всем привет, NW>>Дали тестовую задачу отсортировать текстовый файл построчно, размер 100ГБ и 10ГБ. NW>>Раньше особо такие задачи никогда не решал. Стало интересно, сколько такая сортировка должна занимать времени для решения близкого к идеальному.
SH>Время зависит от параметров системы, в первую очередь диск наверное, так что как его назвать не понятно... SH>Главное, в память всё не грузи
SH>Подсказки давать или сам сообразишь подходящий алгоритм сортировки?
Я уже сделал, сортировка слиянием. Мне интересно насколько быстро получилось..
Здравствуйте, Nonmanual Worker, Вы писали:
NW>Дали тестовую задачу отсортировать текстовый файл построчно, размер 100ГБ и 10ГБ. NW>Стало интересно, сколько такая сортировка должна занимать времени для решения близкого к идеальному.
Если подразумевается, что файл на относительно медленном диске (hdd, ssd, но не ram), то время работы будет определятся скоростью работы с этим самым диском.
Соответственно, если оперативной памяти на компьютере много (достаточно чтобы примерно засосать в себя весь файл), то это делается за время T=S/R+S/W (S — размер файла, R — скорость чтения с диска, W — скорость записи на диск).
Если же оперативной памяти не очень много, то придётся использовать внешнюю сортировку, что потребует сохранить на диске ещё до S промежуточных данных, то есть увеличит предыдущую оценку времени до 2T.
Если же памяти совсем мало (например есть 50МБ ОП при размере файла файла в 100ГБ), время работы будет дополнительно определятся временем seek по диску, чтобы этого избежать нужно использовать уже многопроходную внешнюю сортировку, что даст время 3T.
Да, это простые оценки времени, но они на самом деле не так уж далеки от реальности. Диск, действительно, тормозит.
Кстати, можно заметить, что размер промежуточных данных может быть меньше S, так как иногда отсортированные записи неплохо сжимаются. То есть на практике, конечно, они сжимаются плохо. Но на данных из задачах с собеседований они жмутся хорошо Особенно это характерно для совсем уж вырожденных случаях вроде "отсортировать 100ГБ чисел типа int64". В такой задаче использование простейшего кодирование разностей (с переменной длиной кода) даст огромный выигрыш в скорости.
Вот что у меня получилось:
Генерация тестового файла 100ГБ при записи на диск а один поток, и 3 генератора данных — 30мин на ноутбуке на обычный винт. Это дает представление о скорости винта.
Сортировка этого файла слиянием — 3часа. Думаю что если прогнать профайлером и поэкспериментировать то можно уложиться в 2 часа.
Здравствуйте, Nonmanual Worker, Вы писали:
NW>Всем привет, NW>Дали тестовую задачу отсортировать текстовый файл построчно, размер 100ГБ и 10ГБ. NW>Раньше особо такие задачи никогда не решал. Стало интересно, сколько такая сортировка должна занимать времени для решения близкого к идеальному.
Это смотря чего у тебя 100гб.
Если у тебя 100гб интов, то делается так: заводится массив размера maxint, во время чтения 100гб файла увеличиваешь на единицу ячейку массива, соответствующую текущему значению. Потом выводишь в файл в нужном порядке. Правда это требует 16гб памяти и имеет ограничения, зато отработает чуть дольше, чем генерация файла.
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, Nonmanual Worker, Вы писали:
NW>>Дали тестовую задачу отсортировать текстовый файл построчно, размер 100ГБ и 10ГБ. NW>>Стало интересно, сколько такая сортировка должна занимать времени для решения близкого к идеальному.
W>Если подразумевается, что файл на относительно медленном диске (hdd, ssd, но не ram), то время работы будет определятся скоростью работы с этим самым диском.
Существуют алгоритмы сортировки, работающие на небольшом диапазоне сортируемых элементов, расположенных последоватеольно в большом объёме сортируемых данных. При этом за счёт кэширования в памяти этого диапазона с медленного устройства удаётся серьёзно увеличить общую скорость сортировки, даже если размер ОЗУ незначителен, требуется произвольный дотуп на чтение с устройства и нет другого диска для записи отсортированных данных.
NW>Всем привет, NW>Дали тестовую задачу отсортировать текстовый файл построчно, размер 100ГБ и 10ГБ. NW>Раньше особо такие задачи никогда не решал. Стало интересно, сколько такая сортировка должна занимать времени для решения близкого к идеальному.
Здравствуйте, Nonmanual Worker, Вы писали:
NW>Всем привет, NW>Дали тестовую задачу отсортировать текстовый файл построчно, размер 100ГБ и 10ГБ. NW>Раньше особо такие задачи никогда не решал. Стало интересно, сколько такая сортировка должна занимать времени для решения близкого к идеальному.
Для чего такое нужно практически?
Почему не подходит SQL-база?
Здравствуйте, Osaka, Вы писали:
O>Для чего такое нужно практически?
Проверка навыков оптимизации и применения многопоточности.
O>Почему не подходит SQL-база?
В реале я бы тоже поискал субд движок, но см. выше.
Здравствуйте, Nonmanual Worker, Вы писали:
NW>Генерация тестового файла 100ГБ при записи на диск а один поток, и 3 генератора данных — 30мин на ноутбуке на обычный винт. Это дает представление о скорости винта.
Нормальные харды на последовательном чтении или записи дают порядка 50МБ в секунду, для 100ГБ получается 2000 секунд, примерно сходится.
NW>Сортировка этого файла слиянием — 3часа.
То бишь уложились в 6 проходов, значит на первом проходе внутренне сортировали куски примерно по 3 гига, для дохлого ноута — трпимо. А что за данные? Текстовое представление 32 или 64 битных интов? Тогда они должны в памяти жаться в 2.5 раза, примерно четверть миллиарда интов — наверное, можно увеличить. Или там были произвольные стринги? Тогда может и нельзя
А за сколько укладывается юниксовый sort (-n) ? Для начала можно потестить на 10-гиговом.
NW>Думаю что если прогнать профайлером и поэкспериментировать то можно уложиться в 2 часа.
Тут профилер вряд ли поможет, если нет совсем явных косяков, придётся думать
Навскидку, для промежуточных проходов, если там были инты, их можно записывать в бинарном виде, так они гораздо короче, а значит быстрее. Плюс ускорение чтения и записи, ручное чтение (интов) примерно на порядок быстрее scanf-а, запись тоже неплохо ускоряется, если упереться рогом. Но если промежуточное хранение бинарное, то это только для первого и последнего шага.
NW>Проверка навыков оптимизации и применения многопоточности.
А многопоточность тут как поможет? Всё же упирается в память, которая общая, и во ввод-вывод. Хотя, если есть массив винтов (отдельных, не рэйд), то можно попробовать лить на них параллельно. Но это явно не про ноутбук.
Здравствуйте, Osaka, Вы писали: O>Для чего такое нужно практически? O>Почему не подходит SQL-база?
Например есть у вас банеры рекламные и есть логи по переходу пользователей по страницам и какие при этом они банеры кликали. Вам нужно спрогнозировать какие банеры лучше всего показывать пользователю. На основе его кликов, на основе его страниц и т.д.
Американская контора Outbrain недавно выкладывала файлик на 100 Гб с такими логами за 1 неделю по американскому рынку. Я его заливал в Sql Server на машине с core i7, 24 Гб памяти через bulk insert. Было все это совсем не быстро, что-то около 8 часов. Запрос по сортировки тоже несколько часов работал. Так что удовольствия мало.
.Net реализация так совсем падала, не смотря на 64-битную реализацию, пришлось перезагрузиться — заработала.
Здравствуйте, Nonmanual Worker, Вы писали:
NW>Дали тестовую задачу отсортировать текстовый файл построчно, размер 100ГБ и 10ГБ. NW>Стало интересно, сколько такая сортировка должна занимать времени для решения близкого к идеальному.
Если кратко, то надо использовать ОЗУ максимально. В ОЗУ хранить индекс или их части. Т.е. в идеале менеджер памяти написать и активно кешировать. Сам алгоритм сортировки на таких объемах и длине элемента не сильно важен. Даже без многопоточности, это не уровень тестовой задачи.
Здравствуйте, iZEN, Вы писали:
ZEN>Существуют алгоритмы сортировки, работающие на небольшом диапазоне сортируемых элементов, расположенных последоватеольно в большом объёме сортируемых данных. При этом за счёт кэширования в памяти этого диапазона с медленного устройства удаётся серьёзно увеличить общую скорость сортировки, даже если размер ОЗУ незначителен, требуется произвольный доступ на чтение с устройства и нет другого диска для записи отсортированных данных.
И это всё явно уже реализовано в клиент-серверных базах данных, как и кластера, балансирование нагрузки и многое другое. Только готовыми решениями может воспользоваться даже школьник начитавшись нужной литературы, а написать подобный алгоритм с нуля будет не так чтобы просто для программиста со случайной специализацией. Да и дело не только во времени, это ещё и износ диска.
Здравствуйте, nen777w, Вы писали:
NW>>Всем привет, NW>>Дали тестовую задачу отсортировать текстовый файл построчно, размер 100ГБ и 10ГБ. NW>>Раньше особо такие задачи никогда не решал. Стало интересно, сколько такая сортировка должна занимать времени для решения близкого к идеальному.
N>А это случайно не в контору в Mountain View?
google вроде не дает домашниз заданий
мне эту задачу давали в москве, контора делает специиальное железо в том числе и материнки
Здравствуйте, Nonmanual Worker, Вы писали:
NW>Всем привет, NW>Дали тестовую задачу отсортировать текстовый файл построчно, размер 100ГБ и 10ГБ. NW>Раньше особо такие задачи никогда не решал. Стало интересно, сколько такая сортировка должна занимать времени для решения близкого к идеальному.
можно держать в памяти число корзин, равное числу ядер проца. Если подумать чуть больше, то можно обойтись без доп места на диске (перезаписывать файл in place). Одну корзину сортировать любым подходящим алгоритмом, по вкусу.
Сортировать небольшими кусками (размером с ОЗУ), результаты складывать в отдельные файлы.
Имеем 16 файлов по сколько-то немного гигов.
Берём merge sort и легко сливаем все 16 файлов в один выходной.
Профит.
