Победитель конкурса заданий на собеседованиях

[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 — выкидываем случайным образом половину элементов массива до тех пор пока массив не станет упорчдоченным.

[Sirion]

Задача-победитель не скажу, что прям оригинальная. И решение придумалось секунд за 10. Хотя это хороший повод поговорить про распараллеливание и всё такое.

Пойду почитаю комменты к исходному посту. Неужто все остальные задачи были скучнее?

[warhamster]

Есть у меня подозрения, что если кандидат в ответ на такую задачку начнет говорить про распараллеливание и всё такое — его выставят сразу же.

С другой стороны, выдать вот это вот очевидное решение у меня язык бы не повернулся — мол, не может быть на собеседовании задач с настолько тупыми решениями, тут наверняка подвох или надо спрашивать про какие-то опущенные допусловия…

[vesper-bot]

Программисты делятся на две части: те, кому решение этой задачи очевидно, и те, кто никак не может до него дотумкать. Задача отсеять вторых, и довольно неплохо решается в результате.

[Sirion]

А почему не поговорить про распараллеливание?

[warhamster]

Для этого надо, чтобы накладные расходы на организацию распараллеливания были как минимум ниже, чем на один обход массива.

Из уютненького мирка веба мне смутно кажется, что это даже теоретически невозможно. Единственное, что приходит в голову, это хитрые трюки с памятью, но не с восемью же терабайтами…

[Sirion]

Так ничего же не сказано о том, как эти восемь терабайт хранятся)

[dreesh]

Не вижу ограничений в условии) Даже если мы читаем с диска по 50 МБ в секунду то на вычитку и сортировку уйдет 2 дня максимум (учитывая размер нам должны дать времени предостаточно, иначе заказчик полоумный и работать там не стоит)

[dreesh]

Я аспи и если от меня нужно еще и выуживать у людей пограничные условия то работа явно не для меня (soft skils ~= 0)

[Alexus819]

-создаем массив [0..255] из unsigned long long (вдруг там всего один байт)
-читаем файл по одному байту и увеличиваем элемент в массиве равный считанному байту
-если eof то все. можно сказать байты отсортировнаны, можно записать их в файл по порядку нужное количество раз. индекс массива — это значение байта, значение в массиве — количество таких байт.
все за одно считывание файла.