Здравствуйте, vsb, Вы писали:

vsb>По-моему задача бессмысленная в отрыве от конкретных характеристик. И процессор и диск могут работать со скоростью, отличающейся в разы.
Там нужно написать програмку и прлгнать её. Очевидно, amd64 и ssd. Про hdd не сказано.

vsb>PS а как ты хочешь сортировать чанки за линейное время? Что за count sort? Он для 32-битных чисел сработает на 256 MB?
Да, этот вопрос я упустил. Count sort (сортировка подсчётом) потребует 16гб памяти.

Можно попробовать считать по сегментам: нижние 0-7, 8-15, 16-24, 25-31 бит и сохранять их в bucket-ы. Потом по каждому bucket-у по очереди пробежать и вывести в результирующий файл по числу <<(8 * номер bucket-а) счётчик раз.

Здравствуйте, vsb, Вы писали:

vsb>По-моему задача бессмысленная в отрыве от конкретных характеристик. И процессор и диск могут работать со скоростью, отличающейся в разы.
Там нужно написать програмку и прлгнать её. Очевидно, amd64 и ssd. Про hdd не сказано.

vsb>PS а как ты хочешь сортировать чанки за линейное время? Что за count sort? Он для 32-битных чисел сработает на 256 MB?
Да, этот вопрос я упустил. Count sort (сортировка подсчётом) потребует 16гб памяти.

Можно попробовать считать по сегментам: нижние 0-7, 8-15, 16-24, 25-31 бит и сохранять их в bucket-ы. Потом по каждому bucket-у по очереди пробежать и вывести в результирующий файл по числу <<(8 * номер bucket-а) счётчик раз.
Т.е. сложность 5 * O(n), линейная.