Как и обещал, подводим итоги нашего конкурса самых странных заданий на собеседованиях.
Приз победителя!
Итак, подведём результаты честного народного голосования. Забавно, что некоторые участники дали на конкурс несколько примеров, в результате победил пользователь, который прислал самый занимательный и единственный пример.
По результатам народного голосования, победил пользователь vadim_bv шуточной, но весьма занятной задачей.
Поздравляю vadim_bv с победой! Просьба связаться со мной в личных сообщениях, для того чтобы получить приз. Приз — это подушка для сна на рабочем месте.
Ну и нам конечно интересно узнать решение этой задачи, будем рады увидеть отдельную статью по этому поводу.
Приз победителя!
Итак, подведём результаты честного народного голосования. Забавно, что некоторые участники дали на конкурс несколько примеров, в результате победил пользователь, который прислал самый занимательный и единственный пример.
По результатам народного голосования, победил пользователь vadim_bv шуточной, но весьма занятной задачей.
Задача из физтеховской шутки «решала вся кафедра, но к экзамену решила»: Отсортировать 8-терабайтный массив байтов.
Поздравляю vadim_bv с победой! Просьба связаться со мной в личных сообщениях, для того чтобы получить приз. Приз — это подушка для сна на рабочем месте.
Ну и нам конечно интересно узнать решение этой задачи, будем рады увидеть отдельную статью по этому поводу.
dreesh
Можно отсортировать за один проход посчитав сколько раз встречается каждый байт, я правильно понимаю?
Dvlbug
Лучше считать файл на наличие байта, потом инкремент с последующим чтением и т.д :)
Или ишак умрет, или эмир. Но формально задача решена
Gorthauer87
Так подумать, дьявол тут в том, что в лоб это все равно медленно, нужно видимо врубать трэды, думать о кэшах и блоках.
adictive_max
Тут сильно зависит от оставленных за скобками условий, потому что в крайнем варианте, если данные нужны только в отсортированном виде, можно изначально не хранить весь массив, а хранить только счётчики.
romanshuvalov
«Только счётчики» это и есть весь массив, только в очень хорошо сжатом виде.
Gorthauer87
Тогда задача превращается в архивацию этого массива
alan008
Какая архивация? Это массив из 255 элементов, в котором каждый элемент — Int64 — сколько раз встретился i-й байт
Gorthauer87
Самая натуральная со словарем
Alew
архивация подразумевает возможность разархивации в первоначальный вид?
Gorthauer87
Да, понял в чем недопонимание, я имел в виду лишь хранение отсортированного массива.
crea7or
какой байт решили не считать и почему?
alan008
Это профдеформация, имел в виду [0..255] :-D
static_cast
Один байт можно не хранить, — он будет равен размеру исходного файла за минусом суммы остальных посчитанных байт.
crea7or
технически как обоснуете? надо размер файла сохранить и потом по таблице пройтись-посчитать и ещё if влепить, чтобы не считать один из байтов.
static_cast
Коллега, ну мы же рассматриваем сферическую задачу в вакууме.
Я всего лишь хотел сказать, что при некотором допущении (скажем, пусть это будет точно 8 терабайт из условия :) ), замечание alan008 не является ошибочным.
adictive_max
Это сжатие с потерями. Как если бы после сжатия картинки вам высыпали сначала все красные пиксели, потом все синие и т.д… Если вам нужна только гистограмма, то ОК, но если вам нужно восстановить исходный ряд, то придётся приделывать что-то посложнее.
aamonster
Нет же. Нужно перебирать перестановки массива, пока не обнаружим отсортированную.
deitry
В таком случае эффективнее сортировка Таноса: если массив не отсортирован, удаляем половину.
Chamie
Половину чего?
Напоминает квантовый bogosort. Случайно квантово перемешиваем массив так, чтобы невозможно было без наблюдения узнать новый порядок. Это расщепит вселенную на O(n!) новых вселенных, но это бесплатная операция. Далее, если список оказывается неотсортированным, уничтожаем вселенную.
alexxz
Это была шутка про альтернативные, местами смешные, алгоритмы сортировки. Например delay sort отложить вывод элемента со sleep или setTimeout на указанное в значении число секунд. Stalin sort — выкидываем из массива элементы нарушающие порядок сортировки. Tanos sort — выкидываем случайным образом половину элементов массива до тех пор пока массив не станет упорчдоченным.