Комментарии 30
Или ишак умрет, или эмир. Но формально задача решена
Так подумать, дьявол тут в том, что в лоб это все равно медленно, нужно видимо врубать трэды, думать о кэшах и блоках.
Тогда задача превращается в архивацию этого массива
Какая архивация? Это массив из 255 элементов, в котором каждый элемент — Int64 — сколько раз встретился i-й байт
Самая натуральная со словарем
Это профдеформация, имел в виду [0..255] :-D
Один байт можно не хранить, — он будет равен размеру исходного файла за минусом суммы остальных посчитанных байт.
Я всего лишь хотел сказать, что при некотором допущении (скажем, пусть это будет точно 8 терабайт из условия :) ), замечание alan008 не является ошибочным.
Нет же. Нужно перебирать перестановки массива, пока не обнаружим отсортированную.
В таком случае эффективнее сортировка Таноса: если массив не отсортирован, удаляем половину.
Напоминает квантовый bogosort. Случайно квантово перемешиваем массив так, чтобы невозможно было без наблюдения узнать новый порядок. Это расщепит вселенную на O(n!) новых вселенных, но это бесплатная операция. Далее, если список оказывается неотсортированным, уничтожаем вселенную.
Это была шутка про альтернативные, местами смешные, алгоритмы сортировки. Например delay sort отложить вывод элемента со sleep или setTimeout на указанное в значении число секунд. Stalin sort — выкидываем из массива элементы нарушающие порядок сортировки. Tanos sort — выкидываем случайным образом половину элементов массива до тех пор пока массив не станет упорчдоченным.
Пойду почитаю комменты к исходному посту. Неужто все остальные задачи были скучнее?
С другой стороны, выдать вот это вот очевидное решение у меня язык бы не повернулся — мол, не может быть на собеседовании задач с настолько тупыми решениями, тут наверняка подвох или надо спрашивать про какие-то опущенные допусловия…
Программисты делятся на две части: те, кому решение этой задачи очевидно, и те, кто никак не может до него дотумкать. Задача отсеять вторых, и довольно неплохо решается в результате.
Из уютненького мирка веба мне смутно кажется, что это даже теоретически невозможно. Единственное, что приходит в голову, это хитрые трюки с памятью, но не с восемью же терабайтами…
-читаем файл по одному байту и увеличиваем элемент в массиве равный считанному байту
-если eof то все. можно сказать байты отсортировнаны, можно записать их в файл по порядку нужное количество раз. индекс массива — это значение байта, значение в массиве — количество таких байт.
все за одно считывание файла.
Победитель конкурса заданий на собеседованиях