Сортировка 10 миллионов целых чисел с 1 МБ свободного пространства Объяснение решения - программирование жемчужин

Question

Я читал «Программирование жемчужин», и я действительно запутался в одном из объяснений решения.

Вопрос был: «Файл, содержащий не более n положительных целых чисел, каждое из которых меньше n, где n = 10 ^ 7. Каждое положительное целое число может появляться не более десяти раз. Как бы вы отсортировали файл?»

Приведенное решение в кн .: «Если каждое целое число встречается не более десяти раз, то мы можем посчитать его вхождение в четырехбитовую половину байта. Используя решение задачи 5 (ниже), мы можем отсортировать весь файл за один проход с 10 000 000/2 байтов, или в k проходов с 10 000 000 / 2k байтов "

Решение проблемы 5: : алгоритм с двумя проходами сначала сортирует целые числа от 0 до 4 999 999, используя 5 000 000/8 = 625 000 слов памяти, а затем сортирует от 5 000 000 до 9 999 999 за второй проход. Алгоритм k-прохода сортирует не более n неповторяемых натуральных чисел, меньших, чем n, по времени kn и пространству n / k.)

Я не понимаю, как автор подходит к 10 000 000 / 2k места для сортировки. Я имею в виду, основываясь на решении проблемы 5, сначала нам нужно 625 Кбайт пространства для сортировки в первом проходе и дополнительные 1/2 байта на целое число для хранения правильного счета?

Может ли кто-нибудь помочь мне понять это?

Большое спасибо.

Answer 1

Each positive integer could appear at most ten times.

Для этого вы можете использовать 4 бита на счетчик, а не 2 байта.Если вы группируете счетчики, вы можете даже уменьшить это значение, например, если вы сгруппировали 3 счетчика, то это 10 * 10 * 10 = 1000 комбинаций, и вам нужно 10 бит (= 1024 значения) для этого.

Answer 2

10 000 000 - потому что есть 10 000 000 возможных значений.

2 - потому что каждый байт состоит из двух полубайт.