Bucketing

В тази секция ще разгледаме една не толкова честа (в сравнение с предните две), но пък хитра техника за разделяне на данните, която би могла да бъде ползвана както за ускоряване на алгоритми, така и за създаване на структура данни за специфични проблеми. Най-чистата версия вече трябва да сте срещнали в секцията за сортиране под формата на Counting Sort. Генерализация на този подход ще разгледаме и по-късно, когато говорим за хеширане и хештаблици.

Включените задачи в секцията са относително малко, но всяка от тях изисква важно наблюдение как точно да се разделят елементите в бъкети (какви да бъдат бъкетите, колко големи да бъдат и т.н.). За задачата Popcounts пробвайте да измислите сами решение с константна сложност (за питане) вместо да ползвате вградената в езика функция (която ползва процесорна инструкция за това).